The algebraic data type system of Haskell and other functional languages is an elegant data structuring mechanism to combine the concept of discriminated unions with that of cartesian products.

Definition of Algebraic Data Types

A user-defined algebraic data types is defined as a union of "constructors". Each constructor is a tagged cartesian product.

<user-type-definition> ::= "data" <algebraic-type-name> "=" <constructor> { "|" <constructor>}
<constructor> ::= <tag> { <type> }

Examples

• Binary trees.

data IntTree = Empty | Binary Int IntTree IntTree

• Enumerations

data Weekday = Mon | Tues | Wed | Thurs | Fri

Construction

Values of an algebraic data type are constructed by specifying the tag and the values of all components of one constructor.

t0 = Empty

t1 = Binary 3 Empty Empty

t2 = Binary 26 (Binary 10 Empty Empty) (Binary 37 Empty Empty)

t3 = Binary 15 t1 t2

Access

Discrimination between subtypes of the union and accessing their components is by means of pattern matching. One case or equation is defined for each of the alternative subtypes of the union.

weight :: IntTree -> Int

weight Empty = 0

weight (Binary x t1 t2) = weight t1 + weight t2 + x

When weight is called, the appropriate case is selected by pattern matching. This process might use a switch statement in other languages. But, in addition to selecting the case, the pattern matching also sets up the local variables for the components defined in the particular case. For example, the last equation for the Binary case, defines the three local variables x, t1, t2 to stand for the three components (weight, left subtree, right subtree) of the Binary node.

• Wikipedia: Algebraic Data Type