Tipo de datos algebraicos - Algebraic data type

En programación de computadoras , especialmente programación funcional y teoría de tipos , un tipo de datos algebraicos es un tipo de tipo compuesto , es decir, un tipo formado por la combinación de otros tipos.

Dos clases comunes de tipos algebraicos son los tipos de productos (es decir, tuplas y registros ) y los tipos de suma (es decir, uniones etiquetadas o disjuntas , tipos de coproductos o tipos de variantes ).

Los valores de un tipo de producto suelen contener varios valores, denominados campos . Todos los valores de ese tipo tienen la misma combinación de tipos de campo. El conjunto de todos los valores posibles de un tipo de producto es el producto de la teoría de conjuntos, es decir, el producto cartesiano , de los conjuntos de todos los valores posibles de sus tipos de campo.

Los valores de un tipo de suma suelen agruparse en varias clases, denominadas variantes . Un valor de un tipo de variante generalmente se crea con una entidad cuasifuncional llamada constructor . Cada variante tiene su propio constructor, que toma un número específico de argumentos con tipos específicos. El conjunto de todos los valores posibles de un tipo de suma es la suma teórica de conjuntos, es decir, la unión disjunta , de los conjuntos de todos los valores posibles de sus variantes. Los tipos enumerados son un caso especial de tipos de suma en los que los constructores no toman argumentos, ya que se define exactamente un valor para cada constructor.

Los valores de los tipos algebraicos se analizan con coincidencia de patrones , que identifica un valor por su constructor o nombres de campo y extrae los datos que contiene.

Los tipos de datos algebraicos se introdujeron en Hope , un pequeño lenguaje de programación funcional desarrollado en la década de 1970 en la Universidad de Edimburgo .

Ejemplos de

Uno de los ejemplos más comunes de un tipo de datos algebraicos es la lista enlazada individualmente . Un tipo de lista es un tipo de suma con dos variantes, Nilpara una lista vacía y para la combinación de un nuevo elemento x con una lista xs para crear una nueva lista. Aquí hay un ejemplo de cómo se declararía una lista enlazada individualmente en Haskell : Cons x xs

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

Conses una abreviatura de cons truct. Muchos lenguajes tienen una sintaxis especial para listas definidas de esta manera. Por ejemplo, Haskell y ML usan []para Nil, :o ::para Cons, respectivamente, y corchetes para listas completas. Por Cons 1 (Cons 2 (Cons 3 Nil))lo tanto , normalmente se escribiría como 1:2:3:[]o [1,2,3]en Haskell, o como 1::2::3::[]o [1;2;3]en ML.

Para un ejemplo un poco más complejo, los árboles binarios se pueden implementar en Haskell de la siguiente manera:

data Tree = Empty
          | Leaf Int
          | Node Tree Tree

Aquí, Emptyrepresenta un árbol vacío, Leafcontiene un dato y Nodeorganiza los datos en ramas.

En la mayoría de los lenguajes que admiten tipos de datos algebraicos, es posible definir tipos paramétricos . Se dan ejemplos más adelante en este artículo.

Algo similar a una función, un constructor de datos se aplica a argumentos de un tipo apropiado, produciendo una instancia del tipo de datos al que pertenece el constructor de tipos. Por ejemplo, el constructor de datos Leafes lógicamente una función Int -> Tree, lo que significa que dar un número entero como argumento Leafproduce un valor del tipo Tree. Como Nodetoma dos argumentos del tipo en Treesí, el tipo de datos es recursivo .

Las operaciones sobre tipos de datos algebraicos se pueden definir utilizando la coincidencia de patrones para recuperar los argumentos. Por ejemplo, considere una función para encontrar la profundidad de a Tree, dada aquí en Haskell:

 depth :: Tree -> Int
 depth Empty = 0
 depth (Leaf n) = 1
 depth (Node l r) = 1 + max (depth l) (depth r)

Por lo tanto, un Treedato depthpuede construirse usando cualquiera de Empty, Leafo Nodey debe coincidir con cualquiera de ellos, respectivamente, para tratar todos los casos. En caso de que Node, el patrón extrae los subárboles ly rpara su posterior procesamiento.

Los tipos de datos algebraicos son muy adecuados para implementar la sintaxis abstracta . Por ejemplo, el siguiente tipo de datos algebraicos describe un lenguaje simple que representa expresiones numéricas:

data Expression = Number Int
                | Add Expression Expression
                | Minus Expression Expression
                | Mult Expression Expression
                | Divide Expression Expression

Un elemento de tal tipo de datos tendría una forma como Mult (Add (Number 4) (Minus (Number 0) (Number 1))) (Number 2).

Escribir una función de evaluación para este lenguaje es un ejercicio sencillo; sin embargo, también resultan factibles transformaciones más complejas. Por ejemplo, una pasada de optimización en un compilador podría escribirse como una función tomando una expresión abstracta como entrada y devolviendo una forma optimizada.

Explicación

Lo que está sucediendo es que hay un tipo de datos que puede ser uno de varios tipos de cosas . Cada tipo de cosa está asociada con un identificador llamado constructor , que puede verse como una especie de etiqueta para ese tipo de datos. Cada constructor puede llevar consigo un tipo diferente de datos. Un constructor no puede contener datos (p. Ej., "Vacío" en el ejemplo anterior), o un dato (p. Ej., "Hoja" tiene un valor Int) o varios elementos de datos (p. Ej., "Nodo" tiene dos valores de árbol ).

Para hacer algo con un valor de este tipo de datos algebraicos Tree, se deconstruye mediante un proceso denominado coincidencia de patrones . Implica hacer coincidir los datos con una serie de patrones . La función de ejemplo "profundidad" anterior patrón coincide con su argumento con tres patrones. Cuando se llama a la función, encuentra el primer patrón que coincide con su argumento, realiza cualquier vinculación de variable que se encuentre en el patrón y evalúa la expresión correspondiente al patrón.

Cada patrón anterior tiene una forma que se asemeja a la estructura de algún valor posible de este tipo de datos. El primer patrón simplemente coincide con los valores del constructor Empty . El segundo patrón coincide con los valores del constructor Leaf . Los patrones son recursivos, por lo que los datos asociados con ese constructor coinciden con el patrón "n". En este caso, un identificador en minúsculas representa un patrón que coincide con cualquier valor, que luego está vinculado a una variable con ese nombre; en este caso, una variable " n" está vinculada al valor entero almacenado en el tipo de datos, que se usará en la expresión a evaluar.

La recursividad en los patrones en este ejemplo es trivial, pero un patrón recursivo más complejo posible sería algo así como . Los patrones recursivos de varias capas de profundidad se utilizan, por ejemplo, para equilibrar árboles rojo-negro , que involucran casos que requieren mirar colores a varias capas de profundidad. Node (Node (Leaf 4) x) (Node y (Node Empty z))

El ejemplo anterior es operativamente equivalente al siguiente pseudocódigo:

 switch on (data.constructor)
   case Empty:
     return 0
   case Leaf:
     let l = data.field1
     return 1
   case Node:
     let l = data.field1
     let r = data.field2
     return 1 + max (depth l) (depth r)

La comparación de esto con la coincidencia de patrones señalará algunas de las ventajas de los tipos de datos algebraicos y la coincidencia de patrones. La primera ventaja es la seguridad de tipos . El pseudocódigo anterior se basa en la diligencia del programador para no accedercampo2cuando el constructor es una hoja, por ejemplo. Además, el tipo decampo1 es diferente para Leaf y Node (para Leaf es En t; para Node esÁrbol), por lo que el sistema de tipos tendría dificultades para asignarle un tipo estático de forma segura en una estructura de datos de registro tradicional . Sin embargo, en la coincidencia de patrones, el tipo de cada valor extraído se verifica en función de los tipos declarados por el constructor relevante, y la cantidad de valores que se pueden extraer se conoce en función del constructor, por lo que no enfrenta estos problemas.

En segundo lugar, en la coincidencia de patrones, el compilador verifica estáticamente que se manejen todos los casos. Si faltara uno de los casos de la función de profundidad anterior, el compilador emitiría una advertencia, indicando que no se maneja un caso. Esta tarea puede parecer fácil para los patrones simples anteriores, pero con muchos patrones recursivos complejos, la tarea se vuelve difícil para el humano promedio (o compilador, si debe verificar construcciones if-else anidadas arbitrarias) de manejar. De manera similar, puede haber patrones que nunca coinciden (es decir, que ya están cubiertos por patrones anteriores), y el compilador también puede verificar y emitir advertencias para estos, ya que pueden indicar un error en el razonamiento.

No confunda estos patrones con los patrones de expresión regular utilizados en la coincidencia de patrones de cadenas. El propósito es similar: verificar si un dato coincide con ciertas restricciones y, de ser así, extraer partes relevantes para su procesamiento. Sin embargo, el mecanismo es muy diferente. Este tipo de coincidencia de patrones en tipos de datos algebraicos coincide con las propiedades estructurales de un objeto en lugar de con la secuencia de caracteres de las cadenas.

Teoría

Un tipo de datos algebraicos generales es un tipo de suma posiblemente recursivo de tipos de productos . Cada constructor etiqueta un tipo de producto para separarlo de los demás, o si solo hay un constructor, el tipo de datos es un tipo de producto. Además, los tipos de parámetros de un constructor son los factores del tipo de producto. Un constructor sin parámetros corresponde al producto vacío . Si un tipo de datos es recursivo, la suma completa de productos se envuelve en un tipo recursivo y cada constructor también convierte el tipo de datos en el tipo recursivo.

Por ejemplo, el tipo de datos Haskell:

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

se representa en la teoría de tipos como con los constructores y . ${\ Displaystyle \ lambda \ alpha. \ mu \ beta .1+ \ alpha \ times \ beta}$${\ Displaystyle \ mathrm {nil} _ {\ alpha} = \ mathrm {roll} \ (\ mathrm {inl} \ \ langle \ rangle)}$${\ Displaystyle \ mathrm {cons} _ {\ alpha} \ x \ l = \ mathrm {roll} \ (\ mathrm {inr} \ \ langle x, l \ rangle)}$

El tipo de datos Lista Haskell también se puede representar en teoría tipo en una forma ligeramente diferente, así: . (Observe cómo las construcciones y se invierten en relación con el original). La formación original especificaba una función de tipo cuyo cuerpo era un tipo recursivo. La versión revisada especifica una función recursiva en tipos. (La variable de tipo se usa para sugerir una función en lugar de un tipo base como , ya que es como una f griega ) . La función ahora también debe aplicarse a su tipo de argumento en el cuerpo del tipo. ${\ Displaystyle \ mu \ phi. \ lambda \ alpha .1+ \ alpha \ times \ phi \ \ alpha}$${\ Displaystyle \ mu}$${\ Displaystyle \ lambda}$${\ Displaystyle \ phi}$${\ Displaystyle \ beta}$${\ Displaystyle \ phi}$${\ Displaystyle \ phi}$${\ Displaystyle \ alpha}$

A los efectos del ejemplo de la Lista, estas dos formulaciones no son significativamente diferentes; pero la segunda forma permite expresar los denominados tipos de datos anidados , es decir, aquellos en los que el tipo recursivo difiere paramétricamente del original. (Para obtener más información sobre los tipos de datos anidados, consulte los trabajos de Richard Bird , Lambert Meertens y Ross Paterson).

En teoría de conjuntos, el equivalente de un tipo suma es una unión disjunta , un conjunto cuyos elementos son pares que constan de una etiqueta (equivalente a un constructor) y un objeto de un tipo correspondiente a la etiqueta (equivalente a los argumentos del constructor).

Lenguajes de programación con tipos de datos algebraicos

Muchos lenguajes de programación incorporan tipos de datos algebraicos como una noción de primera clase, que incluye:

Ver también

• Unión disjunta
• Tipo de datos algebraicos generalizados
• Álgebra inicial
• Tipo de cociente
• Unión etiquetada
• Teoría de tipos
• Patrón de visitante

Referencias