En programación informática , especialmente en programación funcional y teoría de tipos , un tipo de datos algebraicos (ADT) es una especie de tipo compuesto , es decir, un tipo formado combinando 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 coproductos o tipos de variantes ). [1]
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 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 de suma normalmente se agrupan en varias clases, denominadas variantes . Un valor de un tipo variante generalmente se crea con una entidad cuasi funcional llamada constructor . Cada variante tiene su propio constructor, que toma una cantidad específica 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 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 algebraico 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. A continuación se muestra un ejemplo de cómo se declararía una lista enlazada individualmente en Haskell :Cons x xs
Lista de datos a = Nil | Contras a ( Listar a ) o
datos [] a = [] | un : [ un ] Conses una abreviatura de cons truct. Muchos idiomas tienen una sintaxis especial para las listas definidas de esta manera. Por ejemplo, Haskell y ML usan []for Nilo :for ::, Consrespectivamente, y corchetes para listas completas. Normalmente Cons 1 (Cons 2 (Cons 3 Nil))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:
árbol de datos = Vacío | Hoja interna | Nodo Int Árbol Árbol o
datos BinaryTree a = BTNil | BTNodo a ( Árbol binario a ) ( Árbol binario a ) 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 dan ejemplos.
De manera algo similar a una función, un constructor de datos se aplica a argumentos de un tipo apropiado, generando 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 al dar un número entero como argumento se Leafproduce un valor del tipo Tree. Como Nodese necesitan dos argumentos del tipo Treeen sí, el tipo de datos es recursivo .
Las operaciones con 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:
profundidad :: Árbol -> Int profundidad Vacío = 0 profundidad ( Hoja n ) = 1 profundidad ( Nodo n l r ) = 1 + max ( profundidad l ) ( profundidad r ) Por lo tanto, un Treedado depthpuede construirse utilizando cualquiera de Empty, Leafo Nodey debe coincidir con cualquiera de ellos respectivamente para tratar todos los casos. En el caso de Node, el patrón extrae los subárboles ly rlos procesa posteriormente.
Los tipos de datos algebraicos son muy adecuados para implementar sintaxis abstracta . Por ejemplo, el siguiente tipo de datos algebraicos describe un lenguaje simple que representa expresiones numéricas:
Expresión de datos = Número Int | Agregar expresión Expresión | Menos expresión expresión | Expresión de múltiples expresiones | Expresión de expresión dividida 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 idioma es un ejercicio sencillo; sin embargo, también se vuelven factibles transformaciones más complejas. Por ejemplo, un paso de optimización en un compilador podría escribirse como una función que toma una expresión abstracta como entrada y devuelve un formato optimizado.
Los tipos de datos algebraicos se utilizan para representar valores que pueden ser uno de varios tipos de cosas . Cada tipo de cosa está asociada a un identificador llamado constructor , que puede considerarse una etiqueta para ese tipo de datos. Cada constructor puede llevar consigo un tipo diferente de datos.
Por ejemplo, considerando el ejemplo binario Treemostrado arriba, un constructor podría no transportar ningún dato (p. ej., Empty), o un dato (p. ej., Leaftiene un valor Int), o varios datos (p. ej., Nodetiene dos Treevalores).
Para hacer algo con un valor de este Treetipo de datos algebraicos, se 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 encuentren 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úscula 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) para ser utilizado en la expresión a evaluar.
La recursividad de los 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-negro , lo que implica 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 : devolver 0 caso Hoja : sea n = datos . campo1 devuelve 1 caso Nodo : let l = datos . campo1 sea r = datos . campo2 retorno 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. Asimismo, el tipo decampo1es diferente para Leafy Node. Para Leaf esEn tpero para Node esÁrbol. El sistema de tipos tendría dificultades para asignar un tipo estático de forma segura para las estructuras de datos de registros tradicionales . Sin embargo, en la coincidencia de patrones no se enfrentan 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 coincidencia de patrones, el compilador realiza una verificación exhaustiva para garantizar 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. La verificación exhaustiva puede parecer fácil para patrones simples, pero con muchos patrones recursivos complejos, la tarea pronto se vuelve difícil para el humano promedio (o el compilador, si debe verificar construcciones arbitrarias anidadas if-else). 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, ya que pueden indicar un error de razonamiento.
La coincidencia de patrones de tipos de datos algebraicos no debe confundirse con la coincidencia de patrones de cadenas de expresiones regulares . El propósito de ambos es similar (extraer partes de un dato que cumpla ciertas restricciones), sin embargo, la implementación es muy diferente. La 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.
Un tipo de datos algebraico general 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 incluye en un tipo recursivo y cada constructor también convierte el tipo de datos en el tipo recursivo.
Por ejemplo, el tipo de datos de Haskell:
Lista de datos a = Nil | Contras a ( Listar a ) se representa en teoría de tipos como con los constructores y .
El tipo de datos Lista de Haskell también se puede representar en teoría de tipos de 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 los 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.
A los efectos 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 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).
Muchos lenguajes de programación incorporan tipos de datos algebraicos como 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.
