Dictionary.net

(Or "sum of products type") In functionalprogramming, new types can be defined, each of which has oneor more constructors. Such a type is known as an algebraicdata type. E.g. in Haskell we can define a new type,"Tree":data Tree = Empty | Leaf Int | Node Tree Treewith constructors "Empty", "Leaf" and "Node". Theconstructors can be used much like functions in that they canbe (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 afunction application though since it is already in normalform. Functions which operate on algebraic data types can bedefined using pattern matching:depth :: Tree -> Intdepth Empty = 0depth (Leaf n) = 1depth (Node l r) = 1 + max (depth l) (depth r)The most common algebraic data type is the list which hasconstructors Nil and Cons, written in Haskell using thespecial syntax "[]" for Nil and infix ":" for Cons.Special cases of algebraic types are product types (only oneconstructor) and enumeration types (many constructors withno arguments). Algebraic types are one kind of constructedtype (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 itsconstructors. Objects of such a type can only be manipulatedusing functions defined in the same module as the typeitself.In set theory the equivalent of an algebraic data type is adiscriminated union - a set whose elements consist of a tag(equivalent to a constructor) and an object of a typecorresponding to the tag (equivalent to the constructorarguments).