data structures - real - ¿Qué son las estructuras de datos de "sumas y productos"?

datatype c#

Question

Una reciente publicación de blog sobre Fusings de William Cook menciona:

El punto clave es que las estructuras en Ensō se ven de manera holística como gráficos, no como valores individuales o como estructuras de datos de sumas y productos tradicionales.

¿A qué se refieren las estructuras de datos tradicionales de sumas y productos?

Answer 1

¿A qué se refieren las estructuras de datos tradicionales de sumas y productos?

En teoría de tipos, las estructuras de datos regulares se pueden describir en términos de sumas, productos y tipos recursivos. Esto lleva a un álgebra para describir las estructuras de datos (y los llamados tipos de datos algebraicos ). Dichos tipos de datos son comunes en los lenguajes funcionales tipados estáticamente, como ML o Haskell.

Productos

Los productos pueden considerarse como la vista de tipo teórico de "estructuras" o "tuplas".

Formalmente, PFPL, canal 14:

El producto binario de dos tipos consiste en pares de valores ordenados, uno de cada tipo en el orden especificado. Las formas de eliminación asociadas son proyecciones, que seleccionan el primer y el segundo componente de un par. El producto nulary, o unidad, tipo consiste únicamente en la única "nupla nula" de ningún valor, y no tiene una forma asociada eliminatoria.

Sumas

Los tipos de suma expresan la elección entre variantes de una estructura de datos. Algunas veces se llaman "tipos de unión" (como en C). Muchos idiomas no tienen noción de tipos de suma.

PFPL, ch 15:

La mayoría de las estructuras de datos involucran alternativas tales como la distinción entre una hoja y un nodo interior en un árbol, o una elección en la forma más externa de una pieza de sintaxis abstracta. Es importante destacar que la elección determina la estructura del valor. Por ejemplo, los nodos tienen hijos, pero las hojas no, y así sucesivamente. Estos conceptos se expresan por tipos de suma, específicamente la suma binaria, que ofrece una opción de dos cosas, y la suma nullary, que ofrece una opción de no cosas.

Tipos recursivos

Junto con los productos y las sumas, podemos introducir la recursión, por lo que un tipo puede definirse (parcialmente) en términos de sí mismo. Buenos ejemplos incluyen árboles y listas.

 data List a = Empty | a : List a
data Tree a = Nil | Node a (Tree a) (Tree a)

Álgebra de sumas, productos y recursión

Da un tipo, digamos Int , podemos comenzar a construir una notación para expresiones algebraicas que describan estructuras de datos:

Una variable solitaria:

Int

Un producto de dos tipos (que denota un par):

Int * Bool

Una suma de dos tipos (que denota una elección entre dos tipos):

Int + Bool

Y algunas constantes:

1 + Int

donde 1 es el tipo de unidad, () .

Una vez que puedas describir los tipos de esta manera, obtienes energía de forma gratuita. En primer lugar, una notación muy concisa para describir los tipos de datos, en segundo lugar, algunos resultados de transferencia de otras álgebras (por ejemplo, la diferenciación funciona en las estructuras de datos ).

Ejemplos

El tipo de unidad, data () = ()

Una tupla, el tipo de producto más simple: data (a,b) = (a,b)

Un tipo de suma simple, data Maybe a = Nothing | Just a data Maybe a = Nothing | Just a

y su alternativa,

y un tipo recursivo , el tipo de listas enlazadas: data [a] = [] | a : [a] data [a] = [] | a : [a]

Teniendo esto en cuenta, puede construir estructuras bastante complicadas combinando sumas, productos y tipos recursivos. Por ejemplo, la notación simple para una lista de productos de sumas de productos: [(Maybe ([Char], Double), Integer)] da lugar a algunos árboles bastante complicados:

Referencias

• Fundamentos prácticos para el lenguaje de programación, Robert Harper, 2011, http://www.cs.cmu.edu/~rwh/plbook/book.pdf
• Introducción rápida al álgebra de tipos de datos, http://blog.lab49.com/archives/3011 (El enlace parece estar muerto)
• Species and Functors and Types, ¡Oh, mi !, Brent Yorgey, http://www.cis.upenn.edu/~byorgey/papers/species-pearl.pdf - tiene una muy buena visión general del álgebra, los tipos de datos de Haskell, y la conexión con especies combinatorias de las matemáticas.

Answer 2

Él se está refiriendo a los tipos de datos algebraicos estándar de los lenguajes de programación funcionales.

Ejemplos:

• Si a es de tipo A y b es de tipo B entonces (a, b) es de tipo A x B , que es un tipo de producto .

• Un tipo de lista con valores de la forma Nil o Cons x xs es un tipo de suma .

Aparentemente, Ensō tiene un mayor énfasis en los gráficos que estos tipos algebraicos arbóreos.

Answer 3

De las notas de la clase para el curso Coursera, "Lenguajes de programación", ofrecido por Univ. de Washington:

"¿Por qué producto y suma? Se relaciona con el hecho de que en el álgebra de Boole, donde 0 es falso y 1 es verdadero, y funciona como multiplicar y funciona como suma".

Answer 4

Ya se han dado respuestas muy detalladas, pero de alguna manera no mencionan este simple hecho.

Los tipos de suma se llaman así porque el número de valores posibles de un tipo de suma es la suma del número de valores de los dos tipos subyacentes. De manera similar para los tipos de productos, la cantidad de valores posibles es el producto.

Esto se deriva de la teoría de tipos que define un tipo como un conjunto de valores.

data MySumType = Foo Bool | Bar Char
data MyProductType = Baz (Bool, Char)

• Bool es un conjunto de 2 valores.
• Char es un conjunto de 256 valores.
• MySumType es un conjunto de 2 + 256 valores.
• MyProductType es un conjunto de 2 * 256 valores.

Ahora nunca olvidarás cuál es cuál.