ADT isn't ADT

-

The first one is Algebraic Data Type. It's like tuples and enums on steroids (and heroine). As a mnemonic device, note that you construct your types/data-structures via algebra-like operators:

  • Aggregation (tuple-like, product-like).
  • Alternatives (enum-like, sum-like). For instance, in haskell,
data BookId = Isbn Int | Doi String
data BookRef = Book String BookId

BookRef embeds a name (encoded as a string) followed by an ISBN number or a DOI reference (but not both). Some better examples follow, but an interesting observation is that this type could be written almost equivalently:

data BookRef = BookIsbn String Int | BookDoi String String

You saw it right, distributivity of multiplication over addition! We usually go the other way around, though: literal (or algebraic, for that matter) factorisation.
The analogy doesn't stop here, and that's a good exercice to imagine how division, power and formal derivative would translate back in terms of type operations.

On top of that, each constructor accepts parameters, and implicitly specifies a... deconstructor, allowing to easily extract the (nested) components into variables. Look how simple it becomes to define a binary tree, and evaluate its size or depth.

data Tree a = Nil | Node a (Tree a) (Tree a)

size Nil = 0
size (Node _ l r) = 1 + (size l) + (size r)
depth Nil = 0
depth (Node _ l r) = 1 + max (depth l) (depth r)

TODO: runnable code!

The second one is Abstract Data Type, when we are just given the signature of the functions (or methods) than can operate on the type. Aka an interface (although the functionality can be achieved via duck typing). For instance, pop giving the top element of a stack, the first element of a list or an array.

It leverages generic programming, where you can apply the same algorithm on different data-structures.

A contrario, our Algebraic Data Types didn't abstract much, since the definition of the type is its underlying structure. In Standard ML, it is called Concrete Data Type! [(chapter 10)][1].

Rejoice, a neat way to reconcile ADT with ADT exists for more than 34 years: Views allows to powerfully pattern-match on abstract data type. You may get that with Java XX in 20 years.

Ref: http://wiki.haskell.org/Algebraic_data_type [1]: http://www.cs.cmu.edu/~rwh/isml/book.pdf

view raw adt_vs_adt.md hosted with ❤ by GitHub

Comments

Post a Comment