|
In computer programming, an algebraic data type is a datatype each of whose values is data from other datatypes wrapped in one of the constructors of the datatype. Any wrapped data is an argument to the constructor. In contrast to other datatypes, the constructor is not executed and the only way to operate on the data is to unwrap the constructor using pattern matching. Programming redirects here. ...
In computer science, a datatype or data type (often simply a type) is a name or label for a set of values and some operations which one can perform on that set of values. ...
In computer science, a value is a sequence of bits that is interpreted according to some data type. ...
In computer science, pattern matching is the act of checking for the presence of the constituents of a given pattern. ...
The most common algebraic data type is a list with two constructors: Nil or [] for an empty list, and Cons (an abbreviation of constructor), ::, or : for the combination of a new element with a shorter list (for example (Cons 1 '(2 3 4)) or 1:[2,3,4]).
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. Values of such a type can only be manipulated using functions defined in the same module as the type itself. In computing, an abstract data type (ADT) is a specification of a set of data and the set of operations that can be performed on the data. ...
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). Set theory is the mathematical theory of sets, which represent collections of abstract objects. ...
In set theory, a disjoint union or discriminated union is a set union in which each element of the resulting union is disjoint from each of the others; the intersection over a disjoint union is the empty set. ...
An example
For example, in Haskell we can define a new algebraic data type, Tree: Haskell is a standardized purely functional programming language with non-strict semantics, named after the logician Haskell Curry. ...
data Tree = Empty | Leaf Int | Node Tree Tree or in OCaml syntax: Objective Caml (OCaml) is a general-purpose programming language descended from the ML family, created by Xavier Leroy, Jérôme Vouillon, Damien Doligez, Didier Rémy and others in 1996. ...
type tree = Empty | Leaf of int | Node of tree * tree or in Visual Prolog syntax: Visual Prolog, also formerly known as PDC Prolog and Turbo Prolog, is a strongly typed object-oriented extension of Prolog. ...
domains tree = empty(); leaf(integer Leaf); node(tree Left, tree Right). Here, Empty, Leaf and Node are the constructors. Somewhat similar to a function, a constructor is applied to arguments of an appropriate type, then yielding an instance of the data type to which the constructor belongs. For instance, Leaf has the something like a “functional type” Int -> Tree meaning that giving an integer as an argument to Leaf produces a value of the type Tree. As Node takes two arguments of the type Tree itself, the datatype is recursive. In computer programming languages, a recursive type is a data type for values that may contain other values of the same type. ...
Operations on algebraic data types can be defined by using pattern matching to retrieve the arguments. For example, consider a function to find the depth of a Tree, given here in Haskell: In computer science, pattern matching is the act of checking for the presence of the constituents of a given pattern. ...
depth :: Tree -> Int depth Empty = 0 depth (Leaf n) = 1 depth (Node l r) = 1 + max (depth l) (depth r) Thus, a Tree given to depth can be constructed using any of Empty, Leaf or Node and we must match for any of them respectively to deal with all cases. In case of Node, the pattern extracts the subtrees l and r for further processing.
Theory A general algebraic data type is a (possibly recursive) sum type of product types. Each constructor tags a product type to separate it from others, or if there is only one constructor, the data type is a product type. Further, the parameter types of a constructor are the factors of the product type. A parameterless constructor corresponds to the empty product. If a datatype is recursive, the entire sum of products is wrapped in a recursive type, and each constructor also rolls the datatype into the recursive type. In computer programming languages, a recursive type is a data type for values that may contain other values of the same type. ...
For example, the Haskell datatype:
data List a = Nil | Cons a (List a) is represented in type theory as  with constructors  and  . At the broadest level, type theory is the branch of mathematics and logic that first creates a hierarchy of types, then assigns each mathematical (and possibly other) entity to a type. ...
The Haskell List datatype can also be represented in type theory in a slightly different form, as follows:  . (Note how the μ and λ constructs are reversed relative to the original.) The original formation specified a type function whose body was a recursive type; the revised version specifies a recursive function on types. (We use the type variable φ to suggest a function rather than a "base type" like β, since φ is like a Greek "f".) Note that we must also now apply the function φ to its argument type α in the body of the type.
For the purposes of the List example, these two formulations are not significantly different; but the second form allows one to express so-called nested data types, i.e., those where the recursive type differs parametrically from the original. (For more information on nested data types, see the works of Richard Bird, Lambert Meertens and Ross Paterson.)
See also In computer science, a tagged union, also called a variant, variant record, discriminated union, or disjoint union, is a data structure used to hold a value that could take on several different, but fixed types. ...
In set theory, a disjoint union (or discriminated union) is a union of a collection of sets whose members are pairwise disjoint. ...
At the broadest level, type theory is the branch of mathematics and logic that first creates a hierarchy of types, then assigns each mathematical (and possibly other) entity to a type. ...
In mathematics, an initial algebra is an initial object in the category of F-algebras for a given endofunctor F. Consider the endofunctor sending to . ...
References - Algebraic data type in The Free On-line Dictionary of Computing, Editor Denis Howe.
This article was originally based on material from the Free On-line Dictionary of Computing, which is licensed under the GFDL. This article does not cite any references or sources. ...
“GFDL†redirects here. ...
| 
Feeds |
Contact