← Back to context

Comment by ithkuil

12 years ago

I don't see the irony. Data structures and data types are two different axis.

You can argue that advanced language constructs will make it easier to write correct code to implement data structures, but it's not a magic bullet.

The Go authors argue that a simple programming language with loops, pointers and arrays is all you need to implement any data structure you need.

I find this a good example of a data structure for which I see little or no benefit in being modeled as an ADTs:

http://research.swtch.com/sparse

Even simple things like doubly linked lists are complicated with ADTs. On the other hand I don't know about good examples of ADTs used outside of the context of functional programming, do you have some pointers?

6 comments

ithkuil

Reply
friendly_chap  12 years ago

"You can argue that advanced language constructs will make it easier to write correct code to implement data structures, but it's not a magic bullet."

There is nothing advanced about ADTs.

"The Go authors argue that a simple programming language with loops, pointers and arrays is all you need to implement any data structure you need."

It's all about increasing the level of abstraction. There is a reason we don't code in assembly anymore. Of course machine code is all you need to implement any data structure, but how convenient is it?

"I find this a good example of a data structure for which I see little or no benefit in being modeled as an ADTs:"

So you found a single counterexample which (according to you) would not benefit from ADTs.

" On the other hand I don't know about good examples of ADTs used outside of the context of functional programming, do you have some pointers?"

I dislike pointers (a necessary evil if you have mutation I guess...), but here is one example:

data Gender = Male | Female vs type Gender int; const ( Male Gender = iota; Female )

Combine the first with pattern matching and you find yourself in awesomenessland (ie. code becomes readable, type safe).

  • ithkuil  12 years ago

    >> On the other hand I don't know about good examples of ADTs used outside of the context of functional programming, do you have some pointers? > I dislike pointers (a necessary evil if you have mutation I guess...), but here is one example

    Perhaps there was a misunderstanding. I asked you if you had some links to some interesting examples of ADT outside the context of functional programming. Because I was assuming that this wasn't a discussion about Go vs purely functional data structures.

    Your example clearly shows the benefits of strong typing with fully described types. My point that this is orthogonal with Rob Pike's position about the importance of data structures.

    Data structures exist independently on how we represent them. I don't see any irony or conflict in highlighting the importance of data structure vs. implementing language features that make it easier to write correct implementation of them.

wcarss  12 years ago

I was totally unfamiliar with any linking between functional programming and Abstract Data Types before reading your post. They are certainly present outside of that world.

Back in my university data structures class, an Abstract Data Type was just the collection of "a data structure and its operations". For example, a tree ADT could be a struct of two pointers and some value, along with operations like addNode, removeNode, findNode, copy, create, destroy, etc... We wrote lists, stacks, trees, hashes, and graphs in C as self-contained ADT libraries. This wikipedia page [1] explains the differences in approach.

The concept of data+operations was a lead in to objects for us, and seems very simple. Is the ADT idea in functional programming inherently more complex? I see from that page that it is intended to be immutable, which is certainly a difference.

1. http://en.wikipedia.org/wiki/Abstract_data_type#Imperative_v...

  • ithkuil  12 years ago

    Unfortunately both abstract data types and algebraic data types share the acronym; I was replying to a comment mentioning the latter.