Difference between revisions of "Algebraic data type"

From HaskellWiki
Jump to: navigation, search
(added introduction and reference to wikipedia)
(formatting only)
 
Line 47: Line 47:
 
data Rose a = Rose a [Rose a]
 
data Rose a = Rose a [Rose a]
 
</haskell>
 
</haskell>
  +
 
In this case, the example tree would be:
 
In this case, the example tree would be:
  +
 
<haskell>
 
<haskell>
 
retree = Rose 5 [Rose 3 [Rose 1 [], Rose 4[]], Rose 7 []]
 
retree = Rose 5 [Rose 3 [Rose 1 [], Rose 4[]], Rose 7 []]

Latest revision as of 13:31, 27 June 2014

This is a type where we specify the shape of each of the elements. Wikipedia has a thorough discussion. "Algebraic" refers to the property that an Algebraic Data Type is created by "algebraic" operations. The "algebra" here is "sums" and "products":

  • "sum" is alternation (A | B, meaning A or B but not both)
  • "product" is combination (A B, meaning A and B together)

Examples:

  • data Pair = P Int Double is a pair of numbers, an Int and a Double together. The tag P is used (in constructors and pattern matching) to combine the contained values into a single structure that can be assigned to a variable.
  • data Pair = I Int | D Double is just one number, either an Int or else a Double. In this case, the tags I and D are used (in constructors and pattern matching) to distinguish between the two alternatives.


Sums and products can be repeatedly combined into an arbitrarily large structures.

Algebraic Data Type is not to be confused with *Abstract* Data Type, which (ironically) is its opposite, in some sense. The initialism "ADT" usually means *Abstract* Data Type, but GADT usually means Generalized *Algebraic* Data Type.

Tree examples

Suppose we want to represent the following tree:

              5
             / \
            3   7
           / \
          1   4

We may actually use a variety of Haskell data declarations that will handle this. The choice of algebraic data types determines its structural/shape properties.

Binary search tree

In this example, values are stored at each node, with smaller values to the left, greater to the right.

data Stree a = Tip | Node (Stree a) a (Stree a)

and then our example tree would be:

  etree = Node (Node (Node Tip 1 Tip) 3 (Node Tip 4 Tip)) 5 (Node Tip 7 Tip)

To maintain the order, such a tree structure is usually paired with a smart constructor.

Rose tree

Alternatively, it may be represented in what appears to be a totally different stucture.

data Rose a = Rose a [Rose a]

In this case, the example tree would be:

retree = Rose 5 [Rose 3 [Rose 1 [], Rose 4[]], Rose 7 []]

The differences between the two are that the (empty) binary search tree Tip is not representable as a Rose tree, and a Rose tree can have an arbitrary and internally varying branching factor (0,1,2, or more).

See also