View source for Algebraic data type

{{Short description|Data type defined by combining other types}}
{{Distinguish|Abstract data type}}
{{More citations needed|date=October 2015}}



In [[computer programming]], especially in [[functional programming]] and [[type theory]], an '''algebraic data type''' ('''ADT''') is a [[composite data type]]—a type formed by combining other types.

An algebraic data type is defined by two key constructions: a ''sum'' and a ''product''. These are sometimes referred to as "OR" and "AND" types.

A '''[[sum type]]''' is a choice between possibilities. The value of a sum type can match one of several defined ''variants''. For example, a type representing the state of a traffic light could be either <code>Red</code>, <code>Amber</code>, or <code>Green</code>. A shape type could be either a <code>Circle</code> (which stores a radius) ''or'' a <code>Square</code> (which stores a width). In formal terms, these variants are known as [[Tagged union|tagged unions]] or [[Disjoint union|disjoint unions]]. Each variant has a name, called a '''constructor''', which can also carry data. [[Enumerated type|Enumerated types]] are a simple form of sum type where the constructors carry no data.

A '''[[product type]]''' combines types together. A value of a product type will contain a value for each of its component types. For example, a <code>Point</code> type might be defined to contain an <code>x</code> coordinate (an integer) ''and'' a <code>y</code> coordinate (also an integer). Formal examples of product types include [[Tuple|tuples]] and [[Record (computer science)|records]]. The set of all possible values of a product type is the [[Cartesian product]] of the sets of its component types.

Values of algebraic data types are typically handled using [[pattern matching]]. This feature allows a programmer to check which constructor a value was made with and extract the data it contains in a convenient and type-safe way.

==History==
Algebraic data types were introduced in [[Hope (programming language)|Hope]], a small [[Functional programming|functional]] [[programming language]] developed in the 1970s at the [[University of Edinburgh]].<ref>{{cite conference |last1=Hudak |first1=Paul |author1-link=Paul Hudak |last2=Hughes |first2=John |author2-link=John Hughes (computer scientist) |last3=Peyton Jones |first3=Simon |author3-link=Simon Peyton Jones |last4=Wadler |first4=Philip |author4-link=Philip Wadler |date=9 June 2007 |chapter=A history of Haskell: being lazy with class |url=http://dl.acm.org/citation.cfm?id=1238856 |title=Proceedings of the third ACM SIGPLAN conference on History of programming languages |isbn=978-1-59593-766-7 |quote=Presentations included Rod Burstall, Dave MacQueen, and Don Sannella on Hope, the language that introduced algebraic data types}}</ref>

==Examples==
===Singly linked list===
One of the most common examples of an algebraic data type is the [[singly linked list]]. A list type is a sum type with two variants, <code>Nil</code> for an empty list and <code>[[Cons]] ''x'' ''xs''</code> for the combination of a new element ''x'' with a list ''xs'' to create a new list. Here is an example of how a singly linked list would be declared in [[Haskell]]:
<syntaxhighlight lang="haskell">
data List a = Nil | Cons a (List a)
</syntaxhighlight>
or
<syntaxhighlight lang="haskell">
data [] a = [] | a : [a]
</syntaxhighlight>
<code>Cons</code> is an abbreviation of ''cons''truct. Many languages have special syntax for lists defined in this way. For example, Haskell and [[ML (programming language)|ML]] use <code>[]</code> for <code>Nil</code>, <code>:</code> or <code>::</code> for <code>Cons</code>, respectively, and square brackets for entire lists. So <code>Cons 1 (Cons 2 (Cons 3 Nil))</code> would normally be written as <code>1:2:3:[]</code> or <code>[1,2,3]</code> in Haskell, or as <code>1::2::3::[]</code> or <code>[1,2,3]</code> in ML.

===Binary tree===
For a slightly more complex example, [[binary tree]]s may be implemented in Haskell as follows:
<syntaxhighlight lang="haskell">
data Tree = Empty
          | Leaf Int
          | Node Int Tree Tree
</syntaxhighlight>
or
<syntaxhighlight lang="haskell">
data BinaryTree a = BTNil
                  | BTNode a (BinaryTree a) (BinaryTree a)
</syntaxhighlight>

Here, <code>Empty</code> represents an empty tree, <code>Leaf</code> represents a leaf node, and <code>Node</code> organizes the data into branches.

In most languages that support algebraic data types, it is possible to define [[parametric polymorphism|parametric]] types. Examples are given later in this article.

Somewhat similar to a function, a data constructor is applied to arguments of an appropriate type, yielding an instance of the data type to which the type constructor belongs. For example, the data constructor <code>Leaf</code> is logically a function <code>Int -> Tree</code>, meaning that giving an integer as an argument to <code>Leaf</code> produces a value of the type <code>Tree</code>. As <code>Node</code> takes two arguments of the type <code>Tree</code> itself, the datatype is [[recursive type|recursive]].

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 <code>Tree</code>, given here in Haskell:

<syntaxhighlight lang="haskell">
depth :: Tree -> Int
depth Empty = 0
depth (Leaf n) = 1
depth (Node n l r) = 1 + max (depth l) (depth r)
</syntaxhighlight>

Thus, a <code>Tree</code> given to <code>depth</code> can be constructed using any of <code>Empty</code>, <code>Leaf</code>, or <code>Node</code> and must be matched for any of them respectively to deal with all cases. In case of <code>Node</code>, the pattern extracts the subtrees <code>l</code> and <code>r</code> for further processing.

===Abstract syntax===
Algebraic data types are highly suited to implementing [[abstract syntax]]. For example, the following algebraic data type describes a simple language representing numerical expressions:

<syntaxhighlight lang="haskell">
data Expression = Number Int
                | Add Expression Expression
                | Minus Expression Expression
                | Mult Expression Expression
                | Divide Expression Expression
</syntaxhighlight>

An element of such a data type would have a form such as <code>Mult (Add (Number 4) (Minus (Number 0) (Number 1))) (Number 2)</code>.

Writing an evaluation function for this language is a simple exercise; however, more complex transformations also become feasible. For example, an optimization pass in a compiler might be written as a function taking an abstract expression as input and returning an optimized form.

==Pattern matching==
{{Further|Pattern matching}}
Algebraic data types are used to represent values that can be one of several ''types of things''. Each type of thing is associated with an identifier called a ''constructor'', which can be considered a tag for that kind of data. Each constructor can carry with it a different type of data.

For example, considering the binary <code>Tree</code> example shown above, a constructor could carry no data (e.g., <code>Empty</code>), or one piece of data (e.g., <code>Leaf</code> has one Int value), or multiple pieces of data (e.g., <code>Node</code> has one <code>Int</code> value and two <code>Tree</code> values).

To do something with a value of this <code>Tree</code> algebraic data type, it is ''deconstructed'' using a process called [[pattern matching]]. This involves matching the data with a series of ''patterns''. The example function <code>depth</code> above pattern-matches its argument with three patterns. When the function is called, it finds the first pattern that matches its argument, performs any variable bindings that are found in the pattern, and evaluates the expression corresponding to the pattern.

Each pattern above has a form that resembles the structure of some possible value of this datatype. The first pattern simply matches values of the constructor <code>Empty</code>. The second pattern matches values of the constructor <code>Leaf</code>. Patterns are recursive, so then the data that is associated with that constructor is matched with the pattern "n". In this case, a lowercase identifier represents a pattern that matches any value, which then is bound to a variable of that name — in this case, a variable "<code>n</code>" is bound to the integer value stored in the data type — to be used in the expression to evaluate.

The recursion in patterns in this example are trivial, but a possible more complex recursive pattern would be something like:

<code><syntaxhighlight lang="lisp" inline="">Node i (Node j (Leaf 4) x) (Node k y (Node Empty z))</syntaxhighlight></code>

Recursive patterns several layers deep are used for example in balancing [[red–black tree]]s, which involve cases that require looking at colors several layers deep.

The example above is operationally equivalent to the following [[pseudocode]]:
<syntaxhighlight lang="swift">
switch on (data.constructor)
  case Empty:
    return 0
  case Leaf:
    let n = data.field1
    return 1
  case Node:
    let l = data.field2
    let r = data.field3
    return 1 + max (depth l) (depth r)
</syntaxhighlight>

The advantages of algebraic data types can be highlighted by comparison of the above pseudocode with a pattern matching equivalent.

Firstly, there is [[type safety]]. In the pseudocode example above, programmer diligence is required to not access {{samp|field2}} when the constructor is a <code>Leaf</code>.  The type system would have difficulties assigning a static type in a safe way for traditional [[record (computer science)|record]] data structures. However, in pattern matching such problems are not faced. The type of each extracted value is based on the types declared by the relevant constructor. The number of values that can be extracted is known based on the constructor.

Secondly, in pattern matching, the compiler performs exhaustiveness checking to ensure all cases are handled. If one of the cases of the ''depth'' function above were missing, the compiler would issue a warning. Exhaustiveness checking may seem easy for simple patterns, but with many complex recursive patterns, the task soon becomes difficult for the average human (or compiler, if it must check arbitrary nested if-else constructs). Similarly, there may be patterns which never match (i.e., are already covered by prior patterns). The compiler can also check and issue warnings for these, as they may indicate an error in reasoning.

Algebraic data type pattern matching should not be confused with [[regular expression]] string pattern matching. The purpose of both is similar (to extract parts from a piece of data matching certain constraints) however, the implementation is very different. Pattern matching on algebraic data types matches on the structural properties of an object rather than on the character sequence of strings.

==Theory==
{{Further|Recursive data type}}
A general algebraic data type is a possibly recursive [[sum type]] of [[product type]]s. 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.

For example, the Haskell datatype:

<syntaxhighlight lang="haskell">
data List a = Nil | Cons a (List a)
</syntaxhighlight>

is represented in [[type theory]] as
<math>\lambda \alpha. \mu \beta. 1 + \alpha \times \beta</math>
with constructors <math>\mathrm{nil}_\alpha = \mathrm{roll}\ (\mathrm{inl}\ \langle\rangle)</math> and <math>\mathrm{cons}_\alpha\ x\ l = \mathrm{roll}\ (\mathrm{inr}\ \langle x, l\rangle)</math>.

The Haskell List datatype can also be represented in type theory in a slightly different form, thus:
<math>\mu \phi. \lambda \alpha. 1 + \alpha \times \phi\ \alpha</math>.
(Note how the <math>\mu</math> and <math>\lambda</math> 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. (The type variable <math>\phi</math> is used to suggest a function rather than a ''base type'' like <math>\beta</math>, since <math>\phi</math> is like a Greek ''f''.) The function must also now be applied <math>\phi</math> to its argument type <math>\alpha</math> 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 expressing so-called [[nested data type]]s, 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 (computer scientist)|Richard Bird]], [[Lambert Meertens]], and Ross Paterson.)

In [[set theory]] the equivalent of a sum type is a [[disjoint union]], a set whose elements are pairs consisting of a tag (equivalent to a constructor) and an object of a type corresponding to the tag (equivalent to the constructor arguments).<ref>{{FOLDOC|Algebraic+data+type}}</ref>

==Programming languages with algebraic data types==
{{Further|Comparison of programming languages (algebraic data type)}}
Many programming languages incorporate algebraic data types as a first class notion, including:
{{Columns-list|colwidth=30em|
* [[ATS (programming language)|ATS]]
* [[Ceylon (programming language)|Ceylon]]
* [[Clean (programming language)|Clean]]
* [[C++]]<ref>{{Cite web|url=https://www.youtube.com/watch?v=ojZbFIQSdl8 |archive-url=https://ghostarchive.org/varchive/youtube/20211212/ojZbFIQSdl8| archive-date=2021-12-12 |url-status=live|title=CppCon 2016: Ben Deane "Using Types Effectively"|via=www.youtube.com}}{{cbignore}}</ref> 
* [[Elm (programming language)|Elm]]
* [[Dart (programming language)|Dart]]<ref>{{Cite web|url=https://dart.dev/language/class-modifiers#sealed|title=Sealed class modifier|website=Dart}}</ref>
* [https://flow.org/ Flow]
* [[F Sharp (programming language)|F#]]
* [[F* (programming language)|F*]]
* [[Free Pascal]]
* [[Haskell]]<ref>{{Cite web|url=https://serokell.io/blog/algebraic-data-types-in-haskell|title=Algebraic Data Types in Haskell|website=Serokell}}</ref>
* [[Haxe]]<ref>{{Cite web|url=https://haxe.org/manual/types-enum-instance.html|title=Enum Instance|website=Haxe - The Cross-platform Toolkit}}</ref>
* [[Hope (programming language)|Hope]]
* [[Idris (programming language)|Idris]]
* [[Java (programming language)|Java]] (16 for product types,<ref>{{Cite web|url=https://openjdk.org/jeps/395|title=JEP 395: Records|website=OpenJDK}}</ref> 17 for sum types<ref>{{Cite web|url=https://openjdk.org/jeps/409|title=JEP 409: Sealed Classes|website=OpenJDK}}</ref>)
* [[Kotlin (programming language)|Kotlin]]<ref>{{Cite web|url=https://kotlinlang.org/docs/reference/sealed-classes.html|title=Sealed Classes - Kotlin Programming Language|website=Kotlin}}</ref>
* [[Limbo (programming language)|Limbo]]
* [[Language Of Temporal Ordering Specification]] (LOTOS)
* [[Mercury (programming language)|Mercury]]
* [[Miranda (programming language)|Miranda]]
* [[Nemerle]]
* [[Nim (programming language)|Nim]]
* [[OCaml]]
* [[Opa (programming language)|Opa]]
* [[OpenCog]]
* [[Perl]]
* [[PureScript]]
* [[Python (programming language)|Python]]
* [[Racket (programming language)|Racket]]
* [[Reason (programming language)|Reason]]<ref>{{Cite web|title=Variants · Reason|url=https://reasonml.github.io/docs/en/variant|access-date=2021-11-30|website=Reason Programming Language|language=en}}</ref>
* [[ReScript (programming language)|ReScript]]<ref>{{Cite web|title=Variant {{!}} ReScript Language Manual|url=https://rescript-lang.org/docs/manual/variant|access-date=2025-12-21|website=ReScript Documentation}}</ref>
* [[Rocq]]<ref>[https://coq.inria.fr/distrib/current/refman/language/cic.html Calculus of Inductive Constructions], and basic standard libraries : [https://coq.inria.fr/distrib/current/stdlib/Coq.Init.Datatypes.html <code>Datatypes</code>] and [https://coq.inria.fr/distrib/current/stdlib/Coq.Init.Logic.html <code>Logic</code>].</ref>
* [[Rust (programming language)|Rust]]<ref>{{cite web |title=Enums and Pattern Matching - The Rust Programming Language |url=https://doc.rust-lang.org/book/ch06-00-enums.html |website=doc.rust-lang.org |access-date=31 August 2021}}</ref>
* [[Scala (programming language)|Scala]]
* [[Standard ML]]
* [[Swift (programming language)|Swift]]
* [[Tom (programming language)|Tom]]
* [[TypeScript]]
* [[Visual Prolog]]
}}

==See also==
* [[Disjoint union]]
* [[Generalized algebraic data type]]
* [[Initial algebra]]
* [[Quotient type]]
* [[Tagged union]]
* [[Type theory]]
* [[Visitor pattern]]

==References==
{{Reflist}}

{{Data types}}

[[Category:Functional programming]]
[[Category:Type theory]]
[[Category:Data types]]
[[Category:Composite data types]]
<!-- Hidden categories below -->
[[Category:Articles with example Haskell code]]