Difference between revisions of "Algebraic data type"
BrettGiles (talk  contribs) (Converting / changing old HaWiki page) 
Jpmarinier (talk  contribs) m (Typo fix: « stucture » ⇒ « structure ») 

(11 intermediate revisions by 8 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 = 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. 

+  * <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. 

+  
+  
+  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 39:  
</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> 

⚫  
+  
⚫  
+  
<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 two representations are almost equivalent, with the exception that the 

+  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). 

−  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 12:07, 6 May 2020
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 = 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. 
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.
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).