What does algebraic in algebraic data types mean in functional languages?

1
votes

I'm just starting to learn about functional programming and one of the things that I still don't get is the adjective "algebraic" in the expression algebraic data types.

Reading the first few sections of the Wikipedia article on the subject, I see that linked lists are one example of such ADT. Another example that is given are trees and, to be honest, I can't see much more algebra in them than I can see in a "vanilla" hierarchy of classes like toy examples like the familiar Animal class with, say, a subclass Cat and another one being Dog. I can, for instance, pattern match on all these types with, say, Scala.

So, what is the secret sauce that I am certainly missing here?

1
functional-programmingpattern-matchingalgebraic-data-types
ADT stands for Abstract Data Type, not Algebraic Data Type. – Barmar
Hmm, it seems that I may be wrong. In FP, ADT does indeed stand for Algebraic. – Barmar
This question appears to be off-topic because it would be more appropriate for cs.stackexchange.com. – Barmar
@Barmar, I would definitely love to see non-technical non-technical explanations to this question. I feel that it is elementary for people who program in functional languages. – funcprogrammingnewbie
Basically, I think it means that new types are built up from simpler types using algebra similar to set theory. – Barmar

1 Answers

0
votes

I have answered this question before[1]. Nevertheless, I'll briefly reiterate why we describe data types as being "algebraic" in this answer.

First, let's understand what the word "algebra" means. The word "algebra" is derived from the Arabic phrase "al-jabr" which means "reunion of broken parts"[2]. The theme of breaking down problems into simpler problems (decomposition) and then reintegrating the solutions to these problems into the final solution (recomposition) is central to several fields including programming[3].

The phrase "al-jabr" was a part of the title of a famous paper on equations[4] written by the Persian mathematician Muhammad al-Khwarizmi, better known as Algoritmi in Latin. The word "algorithm" was derived from his name. The title of the paper was "Kitab al-Jabr w'al-Muqabala" which translates to "Rules of Reintegration and Reduction". It was this paper that introduced Arabic numerals to the West.

Algebra is all about reintegration (i.e. combining parts of an object into the whole). Hence, algebraic data types are about combining simpler data types into more complex data types. You can think of a data type as a set. For example, the data type Int is the set of all integers. We can combine simpler types into more complex types using the cartesian product operation and the disjoint union operation.

The cartesian product operation produces product types[5]. For example, if we have two data types, Int and Char, then the cartesian product Int × Char is the set of all the possible pairs of integers and characters. A value of the type Int × Char is the pair (0, 'a').

The disjoint union operation produces sum types[6]. For example, if we have two data types, Int and Char, then the disjoint union Int + Char is the set of all integers tagged with Int or characters tagged with Char. Values of the type Int + Char are the pairs (0, Int) and ('a', Char).

Algebraic data types allow you to define data types algebraically. For example, the following Shape data type is a disjoint union of the Circle and Rectangle types which are both cartesian products of the Double type:

data Shape = Circle    { x  :: Double, y  :: Double, r  :: Double }
           | Rectangle { x1 :: Double, y1 :: Double, x2 :: Double, y2 :: Double }

This is the reason why they are called "algebraic" data types.