¿Cuál es el significado algebraico de tipo de datos?

Question

Estoy leyendo un libro sobre Haskell, un lenguaje de programación, y me llegó a través de un constructo definido "algebraico" tipo de datos" que se parece a

data WeekDay = Mon | Tue | Wed | Thu | Fri | Sat | Sun

Que simplemente declara cuáles son los valores posibles para el tipo de día de la Semana.

Mi pregunta es ¿cuál es el significado de expresiones algebraicas (tipo de datos para un matemático) y la forma en que se asigna para el lenguaje de programación construir?

Answer 1

Pensar de una expresión algebraica tipo de datos como un tipo de compuesto más simple de tipos, donde el margen de composiciones operadores Y (escrito $\cdot$, a menudo referido como tipos de producto) y O (escrito $+$, que se conoce como tipos de unión o suma de los tipos).

También tenemos el tipo de unidad de $1$ (lo que representa un null tipo) y el tipo básico $X$ (que representa a un tipo de la celebración de una pieza de datos que puede ser de un tipo primitivo, o de otro tipo algebraico).

También tendemos a utilizar $2X$ a la media de $X+X$ $X^2$ a la media de $X\cdot X$, etc.

---

Por ejemplo, el tipo de Haskell

data List a = Nil | Cons a (List a)

dice usted que el tipo de datos List a (una lista de elementos de tipo a) Nilo es Cons de un tipo básico y otro listas. Algebraicamente, podríamos escribir

$$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} \left( 1 - \sqrt{1-4X} \right) = 1 + X + 2X^2 + 5X^3 + 14X^4 + 42X^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$), que no es un árbol binario con un dato (es decir, el árbol que es una rama que contiene dos vacío árboles), que hay dos árboles binarios con dos datums (el segundo dato es ya sea en la izquierda o a la derecha de la rama), de que hay 5 árboles que contiene tres referencias (usted puede dibujar todos ellos) etc.

Answer 2

No sé quien acuñó el término, pero hasta donde yo sé el nombre de "algebraico" tipo de datos" viene del hecho de que tales tipos son soluciones de una ecuación algebraica (o un conjunto de ellos):

$$ \begin{gather*} T_1 = P_1(T_1,\dots,T_n) \\ \dots \\ T_n = P_n(T_1,\dots,T_n) \\ \end{reunir*} $$

The $P_k$ are polynomials, built upon the disjoint union operation (addition) and the cross product operation (multiplication).

For example, given a type of integers int, the type int_list of lists of integers is given by the equation

$$\verb|int_list| = 1 + \verb|int| \times \verb|int_list|$$

Los lenguajes de programación se introducen algunos conceptos que complican la matemática subyacente.

• Estas operaciones sólo tienen buenas propiedades (asociatividad, conmutatividad, el elemento neutro) cuando se consideran los tipos hasta isomorphisms. Por ejemplo, los lenguajes de programación suelen distinguir un producto de un elemento (un 1-tupla) de ese elemento (bajo el capó, el producto de un elemento se representa como un puntero a ese elemento).

• La mayoría de los lenguajes de programación de dar nombres distintos a los operandos en una discontinuo de la unión. La mayoría de los lenguajes de programación también se ofrecen a dar nombres distintos a los operandos en una cruzada de productos, aunque no necesariamente en el mismo tipo de declaración. Matemáticamente, una forma de modelo denominado sindicatos en un conjunto teórico-semántica es incluir el constructor nombre como parte de la estructura matemática:

  $$\verb|left|(A) + \verb|right|(B) = (\{\verb|left|\} \times A) \cup (\{\verb|right|\} \times B)$$

• La mayoría de los lenguajes de programación tienen alguna forma de tipo de generatividad: si se declara dos tipos de soluciones de la ecuación, que son distintos tipos. Esto se refiere a una preocupación común en la programación, donde por lo general no quieren que dos tipos se consideran idénticos sólo porque los datos subyacentes se representan de la misma manera. (Sin embargo, hay casos en los que la generatividad es no deseado. La mayoría de los lenguajes funcionales no-generativo de las definiciones de los tipos de producto; un par de no-generativo definiciones de suma tipos así.)

El ejemplo que das es caso especial sin recursividad ($P_1$ es constante) y donde todos los productos son triviales:

$$\verb|WeekDay| = 1 + 1 + 1 + 1 + 1 + 1 + 1$$

Además, los términos de esta suma se dan nombres, de Mon a Sun.