algebraic data type

(redirected from Algebraic type)

algebraic data type

(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).
This article is provided by FOLDOC - Free Online Dictionary of Computing (
References in periodicals archive ?
Step 4: Clearly, [{[a.sub.[rho]]}.sub.[rho]< [kappa]] is of algebraic type. By Theorem 3 in [2], if [a.sub.[infinity]] is a root of P, we get an immediate extension (L',v') = (K([a.sub.[infinity]]),v').
In the next section, motivated by the analytical solutions (3) and (5), we propose another algebraic type approximate analytical solution for the velocity profile as given by (6) and explore its properties with a method to determine the parameters therein.
To approximate the velocity profile f'(x) directly we suggest an algebraic type analytical function as
Furthermore, the singular behavior of [f.sub.j](z) around [[rho].sub.j] is either of algebraic type
We shall say that a function F(x, y) is of algebraic type for y in a compact subset S of (0, + [infinity]) if there exist [delta] > 0 and 0 < [theta] 6 < [pi]/2 such that
Functions of the algebraic type are commonly encountered in modern analytic combinatorics, and the above assumptions, although quite technical, are needed to unfold the full power of the available machinery.
The following statement says that the egf enumerating a nice class is also of algebraic type. We will use it without any further reference.
Then x [partial derivative] / [partial derivative]x C (x, y) is of algebraic type in SC.
In the proposition above we show that [partial derivative] / [partial derivative]x C (x, y), which is the exponential generating function enumerating vertex-rooted graphs from C, is of algebraic type. We do this solely for technical convenience (instead of making a similar statement for C(x, y)): in what follows, we will study asymptotic properties of random graphs from [C.sub.n], which do not depend on the root label.
Let C be a nice graph class such that [C.sup.*] (x, y) is of algebraic type in a compact set S [subset or equal to] (0, + [infinity]).