data-structures - programacion - suma de dos listas en haskell

Tipos de datos algebraicos de Haskell

Question

Intento entender completamente todos los conceptos de Haskell.

¿De qué manera son los tipos de datos algebraicos similares a los tipos genéricos, por ejemplo, en C # y Java? ¿Y cómo son diferentes? ¿Qué es tan algebraico sobre ellos de todos modos?

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

Answer 1

@Timbo:

Básicamente tienes razón al tratarse de una especie de clase Árbol abstracta con tres clases derivadas (Vacío, Hoja y Nodo), pero también necesitarías hacer cumplir la garantía de que alguien que use tu clase Árbol nunca podrá agregar nuevas clases derivadas , ya que la estrategia para usar el tipo Treet datat 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). Puede imaginar que esto se pone desagradable en C # o C ++, pero en Haskell, ML y OCaml, esto es fundamental para el diseño del lenguaje y la sintaxis, por lo que el estilo de codificación lo admite de una manera mucho más conveniente, mediante la coincidencia de patrones.

ADT (tipos de suma) también son como uniones etiquetadas o tipos de variantes en C o C ++.

Answer 2

En el á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 asignan elementos a los elementos.

Por ejemplo, supongamos 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 argumento 0 que devuelve una "lista", y una función "contra" 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 ocurrir dos cosas indeseables:

• Puede haber elementos en el conjunto de "listas" que no se pueden generar a partir de la "lista vacía" y la "operación contra", llamada "basura". Esto podría ser listas que comiencen a partir de 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, consing un elemento a una lista no vacía podría ser igual a la lista vacía. Esto a veces se llama "confusión".

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

El nombre inicial deriva de la propiedad de que hay exactamente un homomorfismo desde el álgebra inicial hasta 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 ...

Answer 3

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

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

Es equivalente (en la medida de lo posible, e ignorando una evaluación no estricta, 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 un uso más interesante de los parámetros tipo, pero esto es solo un ejemplo simple. Con respecto al nombre de "Tipo algebraico", honestamente, nunca he estado del todo seguro de la razón exacta por la que se llama así, pero he supuesto que se debe a los fundamentos matemáticos del sistema de tipos. Creo 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, por lo que ya no recuerdo los detalles.

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

Answer 4

Los tipos de datos algebraicos de Haskell se llaman así porque corresponden a un álgebra inicial en la teoría de categorías, que nos da algunas leyes, algunas operaciones y algunos símbolos para manipular. Incluso podemos usar notación algebraica para describir estructuras de datos regulares, donde:

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

con alguna notación adicional:

• X² para X•X

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

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

• Unidades: data () = ()

  1

• Opciones: data Maybe a = Nothing | Just a data Maybe a = Nothing | Just a

  1 + X

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

  L = 1+X•L

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

  B = 1 + X•B²

Otras operaciones son válidas (tomadas del documento de Brent Yorgey, enumeradas en las referencias):

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

• Composición, ◦ , dados los tipos F y G , la composición F ◦ G es un tipo que construye "estructuras F hechas de estructuras G" (por ejemplo, R = X • (L ◦ R) , donde L es una lista, es una árbol de rosa.

• La 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

• Especies, funtores y tipos , ¡Oh, mi !, Brent A. Yorgey, Haskell''10, 30 de septiembre de 2010, Baltimore, Maryland, EE. UU.
• Payasos a la izquierda de mí, jokers a la derecha (Disección de estructuras de datos) , Conor McBride POPL 2008

Answer 5

Los tipos de datos de Haskell se llaman "algebraicos" debido a su conexión con las álgebras iniciales categóricas . Pero de esa manera se encuentra la locura.

@olliej: los ADT son en realidad tipos de "suma". Tuplas son productos.

Answer 6

Para mí, el concepto de los tipos de datos algebraicos de Haskell siempre se parecía al polimorfismo en OO-languages ​​como C #.

Mire 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 derivada TreeNodeWithChildren, y si desea incluso una clase derivada EmptyNode.

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

Answer 7

Una razón simple por la que se llaman algebraicos; hay dos 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 "producto" se hace más explícito:

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

Answer 8

vieja pregunta, pero no se menciona la capacidad de unión, que es un aspecto importante de los tipos de datos algebraicos, tal vez el aspecto más importante. Como cada valor es una de las alternativas, es posible una concordancia exhaustiva de patrones basada en casos.