Tipo De Dato Algebraico

Tipo de dato algebraicoDe Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
En matemáticas discretas es usual introducir definiciones de estructuras recursivas dando los casos dedefinició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.

1.El árbol vacío es un árbol y es representado con la constante AVacio.
2.Si t1 yt2 son árboles, y x es un elemento de T, entonces Nodo(t1,x,t2) es un árbol.
3.Los árboles son únicamente los valores que se construyen utilizando las reglas 1 y 2.
La construcción correspondienteen los lenguajes de programación se llama Tipo de dato abstracto Sus reglas de tipo polimórficas fueron introducidas por Robin Milner junto con la definición del lenguaje Standard ML y han sidoadoptadas desde entonces 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 tipoT 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)

Losconstructores del tipo Árbol 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 generalmente se escriben utilizando la construcción de llamada por patrones. Por ejemplo, en Haskell, el número de niveles de un árbol se 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) =...