programming (Or "sum of products type") In
functionalprogramming, new types can be defined, each of which has one
or more
constructors. Such a type is known as an algebraic
data type. E.g. in
Haskell we can define a new type,
"Tree":
data Tree = Empty | Leaf Int | Node Tree Tree
with constructors "Empty", "Leaf" and "Node". The
constructors can be used much like functions in that they can
be (partially) applied to arguments of the appropriate type.
For example, the Leaf constructor has the functional type Int
-@# Tree.
A constructor application cannot be reduced (evaluated) like a
function application though since it is already in
normalform. Functions which operate on algebraic data types can be
depth :: Tree -@# Int
depth Empty = 0
depth (Leaf n) = 1
depth (Node l r) = 1 + max (depth l) (depth r)
The most common algebraic data type is the list which has
constructors Nil and Cons, written in Haskell using the
special syntax "[]" for Nil and infix ":" for Cons.
Special cases of algebraic types are
product types (only one
no arguments). Algebraic types are one kind of
constructedtype (i.e. a type formed by combining other types).
(ADT) if it is exported from a
module without its
constructors. Objects 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
(equivalent to a constructor) and an object of a type
corresponding to the tag (equivalent to the constructor
arguments).
(1994-11-23)