sum of products type

algebraic data type
sum of products type

   <programming> (Or "sum of products type") In {functional
   programming}, 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 {normal
   form}.  Functions which operate on algebraic data types can be
   defined using {pattern matching}:

   	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
   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.  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
   {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).

   (1994-11-23)