algebraic data 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)
Nearby terms:
algebra « ALGEBRAIC « algebraic « algebraic data
type
» Algebraic Interpretive Dialogue » Algebraic Logic
Functional language » Algebraic Manipulation Package
|