What's the meaning of algebraic data type? I'm reading a book about Haskell, a programming language

Sonia Ayers 2022-07-03 Answered
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?
You can still ask an expert for help

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (1)

Jayvion Mclaughlin
Answered 2022-07-04 Author has 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 L
This isn't just pretty notation - it encodes useful information. We can rearrange to get
L ( 1 X ) = 1
and hence
L = 1 1 X = 1 + X + X 2 + X 3 +
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 T 2
which we can rearrange to give
T = 1 2 X ( 1 1 4 X ) = 1 + X + 2 X 2 + 5 X 3 + 14 X 4 + 42 X 5 +
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.
Not exactly what you’re looking for?
Ask My Question

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

asked 2021-02-23
Interpreting z-scores: Complete the following statements using your knowledge about z-scores.
a. If the data is weight, the z-score for someone who is overweight would be
-positive
-negative
-zero
b. If the data is IQ test scores, an individual with a negative z-score would have a
-high IQ
-low IQ
-average IQ
c. If the data is time spent watching TV, an individual with a z-score of zero would
-watch very little TV
-watch a lot of TV
-watch the average amount of TV
d. If the data is annual salary in the U.S and the population is all legally employed people in the U.S., the z-scores of people who make minimum wage would be
-positive
-negative
-zero
asked 2022-06-23
Interpolation and approximation from Numerical Methods
I was reading about interpolation and approximation in Numerical Methods and came across this statement in my course material, "for n data points, there is one and only one polynomial of order (n − 1) that passes through all the points" for example, we have 3 data points on a straight line then how can a second order polynomial satisfy it?
asked 2021-03-07
Dani says she is thinking of a secret number. As a clue, she says the number is the least whole number that has three different prime factors. What is Dani's secret number? What is its prime factorization?
asked 2022-05-16
Relating factors of a polynomial over GF(q) and G F ( q m )
I am reading Richard Blahut's book "Algebraic Codes for Data Transmission" and have come to an impasse in my understanding in section 5.3. In this section, the author wants to relate the factors of a polynomial over GF(q) and the factors of that same polynomial over a GF-extension field G F ( q m ).
There is a good example in the book that I will use here to ask my question. Specifically the GF fields in this example use q=2 and m=4, so there is the prime field GF(2) and the extension field G F ( 2 4 ). The polynomial to be factored over both of these fields is one with particularly special properties, of the form x q m 1 1. So, the polynomial for this example is x 15 1.
The author first factors x 15 1 over GF(2). The prime factors are:
x 15 1 = ( x + 1 ) ( x 2 + x + 1 ) ( x 4 + x + 1 ) ( x 4 + x 3 + 1 ) ( x 4 + x 3 + x 2 + x + 1 )
This factorization over GF(2) makes sense to me and I can easily verify it in MATLAB.
The author then chooses two of the above prime factors and forms a new polynomial:
g ( x ) = ( x 4 + x 3 + 1 ) ( x 4 + x 3 + x 2 + x + 1 ) = x 8 + x 4 + x 2 + x + 1
The above multiplication over GF(2) also makes sense to me and I can easily verify it in MATLAB.
However, the author then changes to analyzing the same polynomial g ( x ) = x 8 + x 4 + x 2 + x + 1 in the extension field G F ( 2 4 ). It seems to be implied that because G F ( 2 4 ) in an extension field of GF(2), and because the polynomial in question is comprised of prime factors (over GF(2)) of the special composite polynomial x15−1, that this switch to the extension field G F ( 2 4 ) is justified.
To analyze g ( x ) in the extension field, we agree to represent the 16 elements of the extension field as the usual powers of the primitive field element alpha:
0 , 1 , α , α 2 , α 3 , α 4 , α 5 , α 6 , α 7 , α 8 , α 9 , α 10 , α 11 , α 12 , α 13 , α 14
The author claims that the aforementioned polynomial g ( x ) = x 8 + x 4 + x 2 + x + 1 has roots/zeroes over
g ( α 3 ) = 0
I am completely unable to make sense of this claim. It raises numerous questions in my mind, and the most basic of these questions is, how can I verify that g ( α ) = 0 and that g ( α 3 ) = 0?
To show how I've tried to verify that g ( α ) = 0 for g ( x ) = x 8 + x 4 + x 2 + x + 1, the author uses the following detailed representation of the elements of extension field G F ( 2 4 ). Of course to describe the elements of any GF extension field, we must choose an irreducible polynomial for the reducing modulus, and throughout the book the author uses the modulus α 4 + α + 1, yielding the 16 field elements:
0 = α 1 = α 0 α 1 = α α 2 = α 2 α 3 = α 3 α 4 = α + 1 α 5 = α 2 + α α 6 = α 3 + α 2 α 7 = α 3 + α + 1 α 8 = α 2 + 1 α 9 = α 3 + α α 10 = α 2 + α + 1 α 11 = α 3 + α 2 + α α 12 = α 3 + α 2 + α + 1 α 13 = α 3 + α 2 + 1 α 14 = α 3 + 1
Given the above element representation of G F ( 2 4 ), we return to the enigmatic claim that for g(x)=x8+x4+x2+x+1, there is the root g(α)=0 over GF(24). We have:
g ( x ) = x 8 + x 4 + x 2 + x + 1
So it seems that for g(x)=x8+x4+x2+x+1 polynomial, g ( α ) 0.
Can anyone show me how to demonstrate that α (as a GF(16) element) is a root of a polynomial that was computed over GF(2)?
If it would be helpful, I can scan the 3 pages of the book and you can see the author's own words for the above ideas. He throws this information at you very quickly, so it's fairly difficult for me (as a non-mathematician) to follow.
asked 2022-05-22
Inconsistency in two-sided hypothesis testing
Suppose you have two sets of data with known population variances and want to test the null hypothesis that two means are equal, ie. H 0 : μ 1 = μ 2 against H 1 : μ 1 > μ 2 . There's a certain way I want to think about it, which is the following:
P ( μ 1 > μ 2 ) = P ( ( μ 1 μ 2 ) < 0 ) = P ( x ¯ 1 x ¯ 2 ( μ 1 μ 2 ) σ δ x ¯ < x ¯ 1 x ¯ 2 σ δ x ¯ ) = P ( z < x ¯ 1 x ¯ 2 σ δ x ¯ )
To me, this 'derivation' makes it perfectly clear what's actually going on. You're actually calculating the probability that H1 is true and not just blindly looking up some z-score.
However, now suppose that H 1 : μ 1 μ 2 . The problem with this is that the method I just described doesn't seem to work. If I write
P ( μ 1 μ 2 ) = P ( μ 1 < μ 2 ) + P ( μ 1 > μ 2 )
Then all that happens is P ( μ 1 μ 2 ) = 1. I think I'm probably not interpreting the above equation correctly.
asked 2022-07-14
What makes a theorem "fundamental"?
I've studied three so-called "fundamental" theorems so far (FT of Algebra, Arithmetic and Calculus) and I'm still unsure about what precisely makes them fundamental (or moreso than other theorems).
Wikipedia claims:
The fundamental theorem of a field of mathematics is the theorem considered central to that field. The naming of such a theorem is not necessarily based on how often it is used or the difficulty of its proofs.
So I am left wondering: what is the main criterion for a theorem to be considered fundamental?
Why, for instance, is there no "Fundamental Theorem of Complex Analysis" (say, de Moivre's formula, for example), or "Fundamental Theorem of Euclidean Geometry" (e.g. Pythagoras' theorem)?
Does anyone have a source of a more-rigourous definition of "fundamental", in this context?
asked 2022-07-04
I was reading about limits of data compression and I had this question that kept me thinking.
Alphabet set: Set of all the unique symbols in the input data
Q. If the distribution over the alphabet set is uniform then is it possible to compress data theoretically ? Standard compression methods (like Huffman codes) exploit the bias in the frequency distribution to obtain codes that have a lower average length of the input text. Is it possible to work without frequency?
Idea 1: One idea is that since the distribution is uniform over the symbols, then any assignment of codes would result in the same number of symbols in the range of the mapping, thus we would require the same number of bits to store that information. Hence the average length of compressed data should be greater than or equal to the original average length.
Idea 2: Another idea that pops up in my head is that if the distribution of symbols is uniform, why not create a new symbol set S' that is essentially a set of all the bi-grams of symbols. But, this distribution also needs to be uniform as the probability of a pair of symbols is same for all the possible cases.
These ideas force me to conclude that it is not possible to compress data if the distribution is uniform.
Please correct me if I am wrong at any point, also I would like to know your views on the problem.
Edit: If you can also provide a formal proof or a book for reference then it would be great.