Tipo de dato algebraico

En matemáticas discretas es usual introducir definiciones de estructuras recursivas dando los casos de definición y un axioma de clausura indicando que ninguna otra cosa forma parte de lo definido.

Por ejemplo, los árboles con información en los nodos pueden definirse como sigue:

Sea T un conjunto. Los árboles con información en los nodos son todos los valores que se pueden construir con las reglas siguientes.

El árbol vacío es un árbol y es representado con la constante AVacio.
Si $t_{1}$ y $t_{2}$ son árboles, y x es un elemento de T, entonces Nodo( $t_{1}$ ,x, $t_{2}$ ) es un árbol.
Los árboles son únicamente los valores que se construyen utilizando las reglas 1 y 2.

La construcción correspondiente en los lenguajes de programación se llama Tipo de datos algebraico. Sus reglas de tipo polimórficas fueron introducidas por Robin Milner junto con la definición del lenguaje Standard ML y han sido adoptadas desde enntonces en diversos lenguajes de programación, sobre todo en los lenguajes de programación funcionales. Por ejemplo, la definición del tipo árbol binario con información en los nodos de tipo T se escribe en Ocaml como sigue:

 type 'T Arbol = AVacio | Nodo of ('T Arbol * 'T * 'T Arbol)

y en sintaxis de Haskell:

data Arbol T = AVacio | Nodo (Arbol T) T (Arbol T)

Los constructores del tipo Arbol son AVacio y Nodo los cuales, al recibir los argumentos necesarios producen un valor del tipo árbol. Por ejemplo, en Ocaml, AVacio es un árbol al igual que Nodo(AVacio,5,AVacio).

Las operaciones sobre los tipos recursivos se generalmente se escriben utilizando la construcción de llamada por patrones. Por ejemplo, en Haskell, el número de niveles de un árbol de define como:

niveles :: Arbol T -> Int
niveles AVacio = 0
niveles (Nodo i n d) = 1 + max (niveles i) (niveles d)

en Standard ML la misma función se escribe

fun niveles AVacio = 0
  | niveles Nodo(i,n,d) = 1 + max (niveles i) (niveles d)

Corrección de programas

A cada tipo de datos algebraico corresponde el orden bien fundamentado de subtérminos y un esquema de inducción estructural en base a la definición del tipo. En el caso de los árboles éstos son los siguientes:

$t_{1}<Nodo(t_{1},n,t_{2})~~~~~~t_{2}<Nodo(t_{1},n,t_{2})$

${\frac {P(AVacio)\wedge (\forall i,n,d:i,d\in Arbol(T):P(i)\wedge P(d)\Rightarrow P(Nodo(i,n,d)))}{(\forall x:x\in Arbol(T):P(x))}}$

Para demostrar la terminación de la función niveles aplicando este esquema de inducción estructural, se tiene que demostrar, utilizando las reglas semánticas del lenguaje, que la expresión (niveles AVacio) termina y que si (niveles i) y (niveles d) terminan entonces (niveles (Nodo(i,n,d)) termina también.

La llamada por patrones es una operación compleja que puede definirse con ayuda de dos primitivas, El operador is permite identificar el caso particular de una definición y la definición estructurada de variables permite obtener los componentes de un caso ya identificado:

En el ejemplo de árboles, el predicado e is AVacio es cierto cuando el árbol e es efectivamente un árbol vacío y e is Nodo es cierto cuando e es un nodo. Una definición del tipo let Nodo(u,x,v) = e ..., que sólo tiene sentido cuando e is Nodo es cierto, permite asociar a las variables u,x,v los conponentes del nodo.

Enlaces externos

FOLDOC (Algebraic data type)