Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I'm reading about Algebraic Data Types (thanks to Richard Minerich I found this excellent explanation of the concept). While I think I understand the notion of sum types and product types etc., what I'm not quite understanding is how Algebraic Data Types are useful beyond specifying pattern matching. What other things can one do with ADT's beyond pattern matching?


EDIT: I'm not asking what can a developer do with ADT's that can't be done with objects. I'm asking if there are other operations that ADT's allow; for example, can one do additional reasoning about the types involved if ADT's are employed? Do ADT's facilitate some sort of type analysis that wouldn't be possible without them?

share|improve this question
2  
What can you do with objects except calling methods? –  delnan May 5 '11 at 14:23
1  
ADT actually refers to "abstract data type", not algebraic data types. –  Rein Henrichs May 5 '11 at 15:37
3  
@Rein: It can refer to either depending on the context. –  sepp2k May 5 '11 at 17:13
3  
@Rein: It does indeed (which I find quite surprising to be honest): However the wikipedia article for ADT lists both Abstract Data Type and Algebraic Data Type as possible meanings. And ADT is very commonly used as an abbreviation for algebraic data types on for example the Haskell mailing list and IRC channel. –  sepp2k May 5 '11 at 17:17
1  
@Rein, I know--just got tired of typing "Algebraic Data Type" over and over and I figured people would be able to understand what I was referring to given the context. –  Onorio Catenacci May 5 '11 at 17:18

2 Answers 2

up vote 4 down vote accepted

Algebraic Data Types are distinct in that they can be constructed from several types of "things". For instance, a Tree can contain either nothing (Empty), a Leaf, or a Node.

data Tree = Empty
          | Leaf Int
          | Node Tree Tree

Since a Node is composed of two Trees, algebraic data types can be recursive.

Pattern matching allows algebraic data types to be deconstructed in a way that maintains type safety. Consider the following implementation of depth and its pseudocode equivalent:

depth :: Tree -> Int
depth Empty = 0
depth (Leaf n) = 1
depth (Node l r) = 1 + max (depth l) (depth r)

compared to:

switch on (data.constructor)
  case Empty:
    return 0
  case Leaf:
    return 1
  case Node:
    let l = data.field1
    let r = data.field2
    return 1 + max (depth l) (depth r)

This has the disadvantage that the programmer must remember to case Empty before Leaf so that field1 is not accessed on an Empty tree. Likewise, the Leaf case must be declared before the Node case so that field2 is not accessed on Leaf. Thus type safety is thus not maintained by the language but rather imposes additional cognitive load on the programmer. By the way, I'm grabbing these examples directly from the wikipedia pages.

Of course, a duck-typing langauge could do something like this:

class Empty
  def depth
    0
  end
end

class Leaf
  def depth
    1
  end
end

class Node
  attr_accessor :field1, :field2

  def depth
    1 + [field1.depth, field2.depth].max
  end
end

So algebraic data types may not be strictly better than their OOP equivalent, but they do provide a different set of tensions to work with when constructing software.

share|improve this answer

I am not so sure the explanation is all that excellent.

Algebraic Data Types are used to create data structures, such as lists and trees.

For example parse trees are easily represented with algebraic data structures.

data BinOperator = Add
                 | Subtr
                 | Div
                 | Mult
                 | Mod
                 | Eq
                 | NotEq
                 | GreaterThan
                 | LogicAnd
                 | LogicOr
                 | BitAnd
                 | BitOr
                 | ...

data UnOperator = Negate
                | Not
                | Increment
                | Decrement
                | Complement
                | Ref
                | DeRef


data Expression = Empty
                | IntConst Int
                | FloatConst Float
                | StringConst String
                | Ident String
                | BinOp BinOperator Expression Expression
                | UnOp UnOperator Expression Bool //prefix or not
                | If Expression Expression Expression
                | While Expression Expression Bool //while vs. do while
                | Block List<Expression>
                | Call Expression List<Expression>
                | ...

It wouldn't actually take awfully much more to represent the C language.

But really, you can do about EVERYTHING with algebraic data types. Lisp proves, you can do everything with pairs and ADTs simply provide a more granular and type safe way to this approach.

Of course, if you ask, "What can you do with ADTs, that you can't do with objects?", the answer is "nothing". Only sometimes (mostly) you will find the solutions on ADTs are significantly less verbose, while those based on objects are arguably more flexible. So to put it in a parse tree represented with ADTs:

If(Call(Ident('likes_ADTs'),[Ident('you')]),
   Call(Ident('use_ADTs'),[Ident('you')]),
   Call(Ident('use_no_ADTs'),[Ident('you')]))
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.