Algebraic data type
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)
Read Also:
- Algebraic equation
an equation in the form of a polynomial having a finite number of terms and equated to zero, as 2 x 3 + 4 x 2 − x + 7 = 0. Historical Examples He felt as he had when puzzling over the unknown quantity in an algebraic equation. Jerome, A Poor Man Mary E. […]
- Algebraic extension
a field containing a given field such that every element in the first field is algebraic over the given field.
- Algebraic expression
a symbol or a combination of symbols used in algebra, containing one or more numbers, variables, and arithmetic operations: how to solve algebraic expressions. Historical Examples An equation admits of description in two ways:— It may be regarded purely as an algebraic expression, or as a geometrical locus. Encyclopaedia Britannica, 11th Edition, Volume 9, Slice […]
- Algebraic function
a function that can be expressed as a root of an equation in which a polynomial, in the independent and dependent variables, is set equal to zero. noun (maths) any function which can be constructed in a finite number of steps from the elementary operations and the inverses of any function already constructed Compare transcendental […]
- Algebraic geometry
the study of sets that are defined by algebraic equations.