An algebraic data type is a Datatype whose each value (computer science) is data from other datatypes wrapped in one of the constructors of the datatype. Any wrapped data is arguments to the constructor. In contrast to other datatypes, the constructor is not executed and the only way to operate on the data is to unwrap the constructor using pattern matching.

The most common algebraic data type is a list which has constructors Nil and Cons (Cons, the list cons truction constructor), written in Haskell using the special syntax [] for Nil and infix : for Cons.

Special cases of algebraic types are product types (only one constructor) and enumeration types (many constructors with no arguments). Algebraic types are one kind of constructed type (i.e. a type formed by combining other types).

An algebraic data type may also be an abstract data type (ADT) if it is exported from a module without its constructors. Values of such a type can only be manipulated using functions defined in the same module as the type itself.

In set theory the equivalent of an algebraic data type is a discriminated union - a set whose elements consist of a tag (equivalent to a constructor) and an object of a type corresponding to the tag (equivalent to the constructor arguments).

= An example =

For example, in Haskell_programming_language we can define a new algebraic data type, Tree: data Tree = Empty | Leaf Int | Node Tree Tree or in Ocaml syntax: type tree = Empty | Leaf of int | Node of tree * tree

Here, Empty, Leaf and Node are the constructors. They are used much like functions in that they can be (partially) applied to arguments of the appropriate type. For instance, Leaf has the functional type Int -> Tree meaning that giving an integer as an argument to Leaf produces a value of the type Tree. As Node takes two arguments of the type Tree itself, the datatype is recursive type.

A constructor application cannot be reduced (evaluated) like a function application though since it is already in normal form (there is no function definition for it). Operations on algebraic data types can be defined by using pattern matching to retrieve the arguments, for example, concider a function to find the depth of a Tree:

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

Thus, a Tree given to depth can be constructed using any of Empty, Leaf or Node and we must match for any of them respectively to deal with all cases. In case of Node, the pattern extracts the subtrees l and r for further processing.

= Theory =

A general algebraic data type is a sum type of product types. Each constructor tags a product type to separate it from others, or if there is only one constructor, the data type is a product type. Further, the parameter types of a constructor are the factors of the product type. A parameterless constructor corresponds to the empty product.

= See also =

= References =