Sonia Ayers

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?

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?

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 ${X}^{2}$ 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

$L=1+X\cdot L$

This isn't just pretty notation - it encodes useful information. We can rearrange to get

$L\cdot (1-X)=1$

and hence

$L=\frac{1}{1-X}=1+X+{X}^{2}+{X}^{3}+\cdot $

which tells us that a list is either empty (1), or it contains 1 element (X), or it contains 2 elements ${X}^{2}$, 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

$T=1+X\cdot {T}^{2}$

which we can rearrange to give

$T=\frac{1}{2X}(1-\sqrt{1-4X})=1+X+2{X}^{2}+5{X}^{3}+14{X}^{4}+42{X}^{5}+\cdots $

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.

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 ${X}^{2}$ 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

$L=1+X\cdot L$

This isn't just pretty notation - it encodes useful information. We can rearrange to get

$L\cdot (1-X)=1$

and hence

$L=\frac{1}{1-X}=1+X+{X}^{2}+{X}^{3}+\cdot $

which tells us that a list is either empty (1), or it contains 1 element (X), or it contains 2 elements ${X}^{2}$, 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

$T=1+X\cdot {T}^{2}$

which we can rearrange to give

$T=\frac{1}{2X}(1-\sqrt{1-4X})=1+X+2{X}^{2}+5{X}^{3}+14{X}^{4}+42{X}^{5}+\cdots $

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.

Which expression has both 8 and n as factors???

One number is 2 more than 3 times another. Their sum is 22. Find the numbers

8, 14

5, 17

2, 20

4, 18

10, 12Perform the indicated operation and simplify the result. Leave your answer in factored form

$\left[\frac{(4x-8)}{(-3x)}\right].\left[\frac{12}{(12-6x)}\right]$ An ordered pair set is referred to as a ___?

Please, can u convert 3.16 (6 repeating) to fraction.

Write an algebraic expression for the statement '6 less than the quotient of x divided by 3 equals 2'.

A) $6-\frac{x}{3}=2$

B) $\frac{x}{3}-6=2$

C) 3x−6=2

D) $\frac{3}{x}-6=2$Find: $2.48\xf74$.

Multiplication $999\times 999$ equals.

Solve: (128÷32)÷(−4)=

A) -1

B) 2

C) -4

D) -3What is $0.78888.....$ converted into a fraction? $\left(0.7\overline{8}\right)$

The mixed fraction representation of 7/3 is...

How to write the algebraic expression given: the quotient of 5 plus d and 12 minus w?

Express 200+30+5+4100+71000 as a decimal number and find its hundredths digit.

A)235.47,7

B)235.047,4

C)235.47,4

D)234.057,7Find four equivalent fractions of the given fraction:$\frac{6}{12}$

How to find the greatest common factor of $80{x}^{3},30y{x}^{2}$?