Tipos de datos algebraicos de Haskell

StackOverflow https://stackoverflow.com/questions/16770

Pregunta

Estoy tratando de comprender completamente todos los conceptos de Haskell.

¿En qué se parecen los tipos de datos algebraicos a los tipos genéricos, por ejemplo, en C# y Java?¿Y en qué se diferencian?¿Qué tienen de algebraico?

Estoy familiarizado con el álgebra universal y sus anillos y campos, pero sólo tengo una vaga idea de cómo funcionan los tipos de Haskell.

¿Fue útil?

Solución

"Tipos de datos algebraicos" en soporte de Haskell polimorfismo paramétrico completo, que es el nombre técnicamente más correcto para los genéricos, como ejemplo simple el tipo de datos de lista:

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

Es equivalente (en la medida de lo posible e ignorando evaluaciones no estrictas, etc.) a

 class List<a> {
     class Cons : List<a> {
         a head;
         List<a> tail;
     }
     class Nil : List<a> {}
 }

Por supuesto, el sistema de tipos de Haskell permite más...Uso interesante de parámetros de tipo, pero este es solo un ejemplo simple.Con respecto al nombre "Tipo algebraico", honestamente, nunca he estado completamente seguro de la razón exacta por la que se les llama así, pero he asumido que se debe a los fundamentos matemáticos del sistema de tipos.I creer que la razón se reduce a la definición teórica de que un ADT es el "producto de un conjunto de constructores", sin embargo, han pasado un par de años desde que escapé de la universidad, así que ya no puedo recordar los detalles.

[Editar:Gracias a Chris Conway por señalar mi tonto error, los ADT son, por supuesto, tipos de suma, los constructores proporcionan el producto/tupla de campos]

Otros consejos

Haskell tipos de datos algebraicos se denominan así porque corresponden a una álgebra inicial en teoría de categorías, dándonos algunas leyes, algunas operaciones y algunos símbolos para manipular.Incluso podemos usar notación algebraica para describir estructuras de datos regulares, donde:

  • + representa tipos de suma (uniones disjuntas, p. ej. Either).
  • • representa tipos de productos (p. ej.estructuras o tuplas)
  • X para el tipo singleton (p. ej. data X a = X a)
  • 1 para el tipo de unidad ()
  • y μ para el punto menos fijo (p. ej.tipos recursivos), generalmente implícitos.

con alguna notación adicional:

  • X² para X•X

De hecho, se podría decir (siguiendo a Brent Yorgey) que un tipo de datos de Haskell es regular si se puede expresar en términos de 1, X, +, •, y un punto mínimo fijo.

Con esta notación, podemos describir de manera concisa muchas estructuras de datos regulares:

  • Unidades: data () = ()

    1

  • Opciones: data Maybe a = Nothing | Just a

    1 + X

  • Liza: data [a] = [] | a : [a]

    L = 1+X•L

  • Árboles binarios: data BTree a = Empty | Node a (BTree a) (BTree a)

    B = 1 + X•B²

Se mantienen otras operaciones (tomado del artículo de Brent Yorgey, enumerado en las referencias):

  • Expansión:Desplegar el punto fijo puede resultar útil para pensar en listas. L = 1 + X + X² + X³ + ... (es decir, las listas están vacías, o tienen un elemento, dos elementos, tres o...)

  • Composición, ◦, tipos dados F y G, la composición F ◦ G es un tipo que construye “estructuras F hechas de estructuras G” (p. ej. R = X • (L ◦ R) ,dónde L Está lista, es un rosal.

  • Diferenciación, la derivada de un tipo de datos D (dado como D') es el tipo de estructuras D con un solo "agujero", es decir, una ubicación distinguida que no contiene ningún dato.Eso sorprendentemente satisface las mismas reglas que para la diferenciación en cálculo:

    1′ = 0

    X′ = 1

    (F + G)′ = F' + G′

    (F • G)′ = F • G′ + F′ • G

    (F ◦ G)′ = (F′ ◦ G) • G′

Referencias:

En álgebra universal un álgebra Consiste en algunos conjuntos de elementos (piense en cada conjunto como el conjunto de valores de un tipo) y algunas operaciones, que mapean elementos a los elementos.

Por ejemplo, suponga que tiene un tipo de "elementos de lista" y un tipo de "listas".Como operaciones, tiene la "lista vacía", que es una función de 0 argumento que devuelve una "lista" y una función de "contras" que toma dos argumentos, un "elemento de lista" y una "lista", y produce una "lista ".

En este punto, hay muchas álgebras que se ajustan a la descripción, ya que pueden suceder dos cosas indeseables:

  • Podría haber elementos en el conjunto de "lista" que no se pueden construir a partir de la "lista vacía" y la "operación de contras", la llamada "basura".Esto podría ser listas que comienzan desde algún elemento que cayó del cielo, o bucles sin un comienzo, o listas infinitas.

  • Los resultados de "contras" aplicados a diferentes argumentos podrían ser iguales, por ejemplo,Consultar un elemento para una lista no vacía podría ser igual a la lista vacía.A esto a veces se le llama "confusión".

Un álgebra que no tiene ninguna de estas propiedades indeseables se llamainicial, y este es el significado previsto del tipo de datos abstracto.

El nombre inicial deriva de la propiedad que hay exactamente un homomorfismo del álgebra inicial a cualquier álgebra dada.Esencialmente, puede evaluar el valor de una lista aplicando las operaciones en el otro álgebra, y el resultado está bien definido.

Se vuelve más complicado para los tipos polimórficos...

Una sencilla razón por la que se les llama algebraicos;Hay tipos de suma (disyunción lógica) y producto (conjunción lógica).Un tipo de suma es una unión discriminada, por ejemplo:

data Bool = False | True

Un tipo de producto es un tipo con múltiples parámetros:

data Pair a b = Pair a b

En O'Caml, el término "producto" se hace más explícito:

type 'a 'b pair = Pair of 'a * 'b

Los tipos de datos de Haskell se denominan "algebraicos" debido a su conexión con álgebras iniciales categóricas.Pero ahí está la locura.

@olliej:Los ADT son en realidad tipos de "suma".Las tuplas son productos.

@Timbo:

Básicamente tienes razón en que es algo así como una clase de árbol abstracta con tres clases derivadas (vacía, hoja y nodo), pero también necesitarías hacer cumplir la garantía de que alguien que use tu clase de árbol nunca pueda agregar nuevas clases derivadas. , ya que la estrategia para usar el tipo de datos Árbol es escribir código que cambie en tiempo de ejecución según el tipo de cada elemento en el árbol (y agregar nuevos tipos derivados rompería el código existente).Puedes imaginar que esto se vuelve desagradable en C# o C++, pero en Haskell, ML y OCaml, esto es fundamental para el diseño y la sintaxis del lenguaje, por lo que el estilo de codificación lo admite de una manera mucho más conveniente, a través de la coincidencia de patrones.

ADT (tipos de suma) también son algo así como sindicatos etiquetados o tipos de variantes en C o C++.

Vieja pregunta, pero nadie mencionó la nulidad, que es un aspecto importante de los tipos de datos algebraicos, quizás el aspecto más importante.Dado que cada valor debe ser una de las alternativas, es posible una comparación exhaustiva de patrones basada en casos.

Para mí, el concepto de tipos de datos algebraicos de Haskell siempre pareció polimorfismo en lenguajes OO como C#.

Mira el ejemplo de http://en.wikipedia.org/wiki/Algebraic_data_types:

data Tree = Empty 
          | Leaf Int 
          | Node Tree Tree

Esto podría implementarse en C# como una clase base TreeNode, con una clase Leaf derivada y una clase TreeNodeWithChildren derivada, y si lo desea, incluso una clase derivada VacuumNode.

(Está bien, lo sé, nadie haría eso jamás, pero al menos tú podrías hacerlo).

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top