En programación informática , especialmente en programación funcional y teoría de tipos , un tipo de datos algebraicos (TDA) es un tipo de tipo compuesto , es decir, un tipo formado mediante la combinación de otros tipos.
Dos clases comunes de tipos algebraicos son los tipos de producto (es decir, tuplas y registros ) y los tipos de suma (es decir, uniones etiquetadas o disjuntas , tipos de coproducto o tipos de variantes ). [1]
Los valores de un tipo de producto suelen contener varios valores, llamados 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 teórico 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 suma se agrupan normalmente en varias clases, llamadas variantes . Un valor de un tipo variante se crea normalmente 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 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 suma en los que los constructores no toman argumentos, ya que se define exactamente un valor para cada constructor.
Los valores de 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 . [2]
Uno de los ejemplos más comunes de un tipo de datos algebraicos es la lista enlazada simple . 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. A continuación, se muestra un ejemplo de cómo se declararía una lista enlazada simple en Haskell :Cons x xs
datos Lista a = Nil | Cons a ( Lista a ) o
datos [] a = [] | a : [ a ] Conses una abreviatura de construct . Muchos lenguajes tienen una sintaxis especial para las listas definidas de esta manera. Por ejemplo, Haskell y ML usan []for Nilo for respectivamente, y corchetes para listas enteras. Por lo tanto, :normalmente se escribiría como o en Haskell, o como o en ML.::ConsCons 1 (Cons 2 (Cons 3 Nil))1:2:3:[][1,2,3]1::2::3::[][1,2,3]
Para un ejemplo un poco más complejo, los árboles binarios se pueden implementar en Haskell de la siguiente manera:
datos Árbol = Vacío | Hoja Int | Nodo Int Árbol Árbol o
datos ÁrbolBinarioa = BTNil | BTNodea ( ÁrbolBinarioa ) ( ÁrbolBinarioa ) Aquí, Emptyrepresenta un árbol vacío, Leafrepresenta un nodo hoja 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 . Más adelante en este artículo se ofrecen ejemplos.
De forma similar a una función, un constructor de datos se aplica a argumentos de un tipo apropiado, lo que produce una instancia del tipo de datos al que pertenece el constructor de tipo. Por ejemplo, el constructor de datos Leafes lógicamente una función Int -> Tree, lo que significa que dar un entero como argumento a Leafproduce un valor del tipo Tree. Como Nodetoma dos argumentos del tipo Treeen sí, el tipo de datos es recursivo .
Las operaciones con tipos de datos algebraicos se pueden definir mediante la búsqueda de patrones para recuperar los argumentos. Por ejemplo, considere una función para encontrar la profundidad de un Tree, dada aquí en Haskell:
profundidad :: Árbol -> Int profundidad Vacío = 0 profundidad ( Hoja n ) = 1 profundidad ( Nodo n l r ) = 1 + máx ( profundidad l ) ( profundidad r ) Por lo tanto, se puede construir un Treedado usando cualquiera de , , o y debe coincidir con cualquiera de ellos respectivamente para tratar todos los casos. En el caso de , el patrón extrae los subárboles y para su posterior procesamiento.depthEmptyLeafNodeNodelr
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:
datos Expresión = Número Int | Expresión de suma Expresión | Expresión de resta Expresión | Expresión de multiplicación Expresión | Expresión de división Expresión Un elemento de dicho 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 se pueden realizar transformaciones más complejas. Por ejemplo, un paso de optimización en un compilador podría escribirse como una función que tome una expresión abstracta como entrada y devuelva una forma optimizada.
Los tipos de datos algebraicos se utilizan para representar valores que pueden ser de varios tipos . Cada tipo de cosa está asociado a un identificador llamado constructor , que puede considerarse una etiqueta para ese tipo de datos. Cada constructor puede llevar consigo un tipo de datos diferente.
Por ejemplo, considerando el ejemplo binario Treemostrado arriba, un constructor podría no llevar ningún dato (por ejemplo, Empty), o un solo dato (por ejemplo, Leaftiene un valor Int), o varios datos (por ejemplo, Nodetiene dos Treevalores).
Para hacer algo con un valor de este Treetipo de datos algebraicos, se lo deconstruye mediante un proceso llamado coincidencia de patrones . Esto implica hacer coincidir los datos con una serie de patrones . La función de ejemplo depthanterior hace coincidir 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 variables 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 se corresponden con el patrón "n". En este caso, un identificador en minúscula representa un patrón que coincide con cualquier valor, que luego se vincula a una variable de ese nombre (en este caso, una variable " n" se vincula al valor entero almacenado en el tipo de datos) para usarse en la expresión a evaluar.
La recursión en patrones en este ejemplo es trivial, pero un posible patrón recursivo más complejo sería algo como:
Node (Node (Leaf 4) x) (Node y (Node Empty z))
Los patrones recursivos de varias capas de profundidad se utilizan, por ejemplo, para equilibrar árboles rojo-negros , que involucran casos que requieren observar colores de varias capas de profundidad.
El ejemplo anterior es operativamente equivalente al siguiente pseudocódigo :
encender ( datos.constructor ) caso Vacío : retorna 0 caso Hoja : let n = datos.campo1 retorna 1 caso Nodo : let l = datos.campo1 let r = datos.campo2 retorna 1 + máx ( profundidad l ) ( profundidad r ) Las ventajas de los tipos de datos algebraicos se pueden resaltar comparando el pseudocódigo anterior con un equivalente de coincidencia de patrones.
En primer lugar, está la seguridad de tipos . En el ejemplo de pseudocódigo anterior, se requiere diligencia del programador para no accedercampo2cuando el constructor es un Leaf. Además, el tipo decampo1es diferente para Leafy Node. Para Leaf esIntpero para Node esÁrbolEl sistema de tipos tendría dificultades para asignar un tipo estático de forma segura a las estructuras de datos de registros tradicionales . Sin embargo, en la comparación de patrones no se enfrentan a estos problemas. El tipo de cada valor extraído se basa en los tipos declarados por el constructor correspondiente. La cantidad de valores que se pueden extraer se conoce en función del constructor.
En segundo lugar, en la comparación de patrones, el compilador realiza una comprobación exhaustiva para garantizar que se gestionen todos los casos. Si faltara uno de los casos de la función de profundidad anterior, el compilador emitiría una advertencia. La comprobación exhaustiva puede parecer fácil para patrones simples, pero con muchos patrones recursivos complejos, la tarea pronto se vuelve difícil para el ser humano promedio (o el compilador, si debe comprobar construcciones if-else anidadas arbitrarias). De manera similar, puede haber patrones que nunca coincidan (es decir, que ya estén cubiertos por patrones anteriores). El compilador también puede comprobarlos y emitir advertencias para ellos, ya que pueden indicar un error en el razonamiento.
La comparación de patrones de tipos de datos algebraicos no debe confundirse con la comparación de patrones de cadenas de expresiones regulares . El propósito de ambas es similar (extraer partes de un conjunto de datos que cumplan con ciertas restricciones), sin embargo, la implementación es muy diferente. La comparación de patrones en tipos de datos algebraicos se basa en las propiedades estructurales de un objeto en lugar de en la secuencia de caracteres de las cadenas.
Un tipo de datos algebraicos generales es un tipo de suma posiblemente recursiva de tipos de productos . Cada constructor etiqueta un tipo de producto para separarlo de otros, 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, toda la suma 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:
datos Lista a = Nil | Cons a ( Lista a ) se representa en la teoría de tipos como con constructores y .
El tipo de datos de lista de Haskell también se puede representar en la teoría de tipos de una forma ligeramente diferente, por ejemplo: . (Observe cómo las construcciones y están invertidas 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 sobre tipos. (La variable de tipo se utiliza para sugerir una función en lugar de un tipo base como , ya que es como una f griega ). La función también debe aplicarse ahora a su tipo de argumento en el cuerpo del tipo.
Para los fines del ejemplo de la lista, estas dos formulaciones no son significativamente diferentes; pero la segunda forma permite expresar los llamados 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 la teoría de conjuntos, el equivalente de un tipo suma es una unión disjunta , un conjunto cuyos elementos son pares que consisten en una etiqueta (equivalente a un constructor) y un objeto de un tipo correspondiente a la etiqueta (equivalente a los argumentos del constructor). [3]
Muchos lenguajes de programación incorporan tipos de datos algebraicos como una noción de primera clase, incluidos:
Las presentaciones incluyeron a Rod Burstall, Dave MacQueen y Don Sannella sobre Hope, el lenguaje que introdujo los tipos de datos algebraicos
