Difference between revisions of "Algebraic data type"
BrettGiles (talk | contribs) (Converting / changing old HaWiki page) |
m (Consistency) Tag: visualeditor-switched |
||
(12 intermediate revisions by 9 users not shown) | |||
Line 1: | Line 1: | ||
This is a [[type]] where we specify the shape of each of the elements. |
This is a [[type]] where we specify the shape of each of the elements. |
||
+ | [http://en.wikipedia.org/wiki/Algebraic_data_type Wikipedia has a thorough discussion.] |
||
+ | "Algebraic" refers to the property that an Algebraic Data Type is created by "algebraic" operations. The "algebra" here is "sums" and "products": |
||
+ | |||
+ | * "sum" is alternation (<hask>A | B</hask>, meaning <hask>A</hask> or <hask>B</hask> but not both) |
||
+ | * "product" is combination (<hask>A B</hask>, meaning <hask>A</hask> and <hask>B</hask> together) |
||
+ | |||
+ | Examples: |
||
+ | |||
+ | * <hask>data Pair = I Int | D Double</hask> is just one number, either an <hask>Int</hask> or else a <hask>Double</hask>. In this case, the tags <hask>I</hask> and <hask>D</hask> are used (in constructors and pattern matching) to distinguish between the two alternatives. |
||
+ | * <hask>data Pair = P Int Double</hask> is a pair of numbers, an <hask>Int</hask> and a <hask>Double</hask> together. The tag <hask>P</hask> is used (in constructors and pattern matching) to combine the contained values into a single structure that can be assigned to a variable. |
||
+ | |||
+ | |||
+ | Sums and products can be repeatedly combined into an arbitrarily large structures. |
||
+ | |||
+ | Algebraic Data Type is not to be confused with [[Abstract_data_type | *Abstract* Data Type]], which (ironically) is its opposite, in some sense. The initialism "ADT" usually means *Abstract* Data Type, but [[GADT]] usually means Generalized *Algebraic* Data Type. |
||
==Tree examples== |
==Tree examples== |
||
Line 11: | Line 26: | ||
1 4 |
1 4 |
||
− | We may |
+ | We may actually use a variety of Haskell data declarations that will handle this. The choice of algebraic data types determines its structural/shape properties. |
+ | |||
===Binary search tree=== |
===Binary search tree=== |
||
Line 24: | Line 40: | ||
</haskell> |
</haskell> |
||
− | To maintain the order, such a tree structure is usually paired with a [[Smart constructor]]. |
+ | To maintain the order, such a tree structure is usually paired with a [[Smart constructors | smart constructor]]. |
===Rose tree=== |
===Rose tree=== |
||
− | + | Alternatively, it may be represented in what appears to be a totally different structure. |
|
<haskell> |
<haskell> |
||
data Rose a = Rose a [Rose a] |
data Rose a = Rose a [Rose a] |
||
</haskell> |
</haskell> |
||
+ | |||
− | In this case, the |
+ | In this case, the example tree would be: |
+ | |||
<haskell> |
<haskell> |
||
retree = Rose 5 [Rose 3 [Rose 1 [], Rose 4[]], Rose 7 []] |
retree = Rose 5 [Rose 3 [Rose 1 [], Rose 4[]], Rose 7 []] |
||
</haskell> |
</haskell> |
||
+ | The differences between the two are that the (empty) binary search tree <hask>Tip</hask> is not representable as a <hask>Rose</hask> tree, and a Rose tree can have an arbitrary and internally varying branching factor (0,1,2, or more). |
||
− | The two representations are almost equivalent, with the exception that the |
||
+ | |||
− | binary search tree <hask>Tip</hask> is not representable in this <hask>Rose</hask> type declaration. Also, due to laziness, I believe we could represent infinite trees with the above declaration. |
||
+ | ==See also== |
||
+ | *[[Abstract data type]] |
||
+ | *[[Concrete data type]] |
||
+ | *[[Concrete view]] |
||
+ | *[[Indirect composite]] |
||
+ | [[Category:Language]] [[Category:Glossary]] |
Latest revision as of 08:47, 22 May 2023
This is a type where we specify the shape of each of the elements. Wikipedia has a thorough discussion. "Algebraic" refers to the property that an Algebraic Data Type is created by "algebraic" operations. The "algebra" here is "sums" and "products":
- "sum" is alternation (
A | B
, meaningA
orB
but not both) - "product" is combination (
A B
, meaningA
andB
together)
Examples:
data Pair = I Int | D Double
is just one number, either anInt
or else aDouble
. In this case, the tagsI
andD
are used (in constructors and pattern matching) to distinguish between the two alternatives.data Pair = P Int Double
is a pair of numbers, anInt
and aDouble
together. The tagP
is used (in constructors and pattern matching) to combine the contained values into a single structure that can be assigned to a variable.
Sums and products can be repeatedly combined into an arbitrarily large structures.
Algebraic Data Type is not to be confused with *Abstract* Data Type, which (ironically) is its opposite, in some sense. The initialism "ADT" usually means *Abstract* Data Type, but GADT usually means Generalized *Algebraic* Data Type.
Tree examples
Suppose we want to represent the following tree:
5 / \ 3 7 / \ 1 4
We may actually use a variety of Haskell data declarations that will handle this. The choice of algebraic data types determines its structural/shape properties.
Binary search tree
In this example, values are stored at each node, with smaller values to the left, greater to the right.
data Stree a = Tip | Node (Stree a) a (Stree a)
and then our example tree would be:
etree = Node (Node (Node Tip 1 Tip) 3 (Node Tip 4 Tip)) 5 (Node Tip 7 Tip)
To maintain the order, such a tree structure is usually paired with a smart constructor.
Rose tree
Alternatively, it may be represented in what appears to be a totally different structure.
data Rose a = Rose a [Rose a]
In this case, the example tree would be:
retree = Rose 5 [Rose 3 [Rose 1 [], Rose 4[]], Rose 7 []]
The differences between the two are that the (empty) binary search tree Tip
is not representable as a Rose
tree, and a Rose tree can have an arbitrary and internally varying branching factor (0,1,2, or more).