What's the meaning of algebraic data type?
I'm reading a book about Haskell, a programming language
Sonia Ayers
Answered question
2022-07-03
What's the meaning of algebraic data type? I'm reading a book about Haskell, a programming language, and I came across a construct defined "algebraic data type" that looks like data WeekDay = Mon | Tue | Wed | Thu | Fri | Sat | SunThat simply declares what are the possible values for the type WeekDay. My question is what is the meaning of algebraic data type (for a mathematician) and how that maps to the programming language construct?
Answer & Explanation
Jayvion Mclaughlin
Beginner2022-07-04Added 14 answers
Think of an algebraic data type as a type composed of simpler types, where the allowable compositions operators are AND (written ⋅, often referred to as product types) and OR (written +, referred to as union types or sum types). We also have the unit type 1 (representing a null type) and the basic type X (representing a type holding one piece of data - this could be of a primitive type, or another algebraic type). We also tend to use 2X to mean X+X and to mean X⋅X, etc. For example, the Haskell type data List a = Nil | Cons a (List a) tells you that the data type List a (a list of elements of type a) is either Nil, or it is the Cons of a basic type and another lists. Algebraically, we could write
This isn't just pretty notation - it encodes useful information. We can rearrange to get
and hence
which tells us that a list is either empty (1), or it contains 1 element (X), or it contains 2 elements , or it contains 3 elements, or... For a more complicated example, consider the binary tree data type: data Tree a = Nil | Branch a (Tree a) (Tree a) Here a tree T is either nil, or it is a Branch consisting of a piece of data and two other trees. Algebraically
which we can rearrange to give
where I have chosen the negative square root so that the equation makes sense (i.e. so that there are no negative powers of X, which are meaningless in this theory). This tells us that a binary tree can be nil (1), that there is one binary tree with one datum (i.e. the tree which is a branch containing two empty trees), that there are two binary trees with two datums (the second datum is either in the left or the right branch), that there are 5 trees containing three datums (you might like to draw them all) etc.