Tipos y árboles en Ocaml

Aunque en Ocaml existen infinitos tipos de datos (partiendo de las combinaciones de los tipos primitivos del lenguaje), puede en un momento resultar útil dar un nombre más práctico a un tipo concreto. Con ese nombre no nos referimos a un dato concreto, sino al conjunto de todos los que pertenezcan a ese tipo. Por ejemplo, en pascal podríamos hacer algo muy simple:
type entero = integer;
Con esto, conseguiríamos poder emplear la palabra “entero” en nuestros programas para referirnos a los números enteros del conjunto “integer“. Puede resultar útil cuando queramos hacer nuestro código más legible. En Ocaml, esto se realiza mediante la expresión “type” y su sintaxis es la siguiente:
# type <nombre_de_tipo> = <nombre_de_constructor> of <esquema_de_tipos>;;
Tambien podemos definir varios constructores de la forma habitual en la sintaxis de Ocaml:
# type <nombre_de_tipo> =
        <nombre_de_constructor_1> of <esquema_de_tipos_1>
      | <nombre_de_constructor_2> of <esquema_de_tipos_2>
      | ...
      | <nombre_de_constructor_n> of <esquema_de_tipos_n>;;

La forma más sencilla es entenderlo con un ejemplo básico. Imaginemos que queremos representar un reloj mediante un par de enteros: el primero es la hora y el segundo los minutos. Algo tal que (00, 00) para representar la medianoche y (12,30) para representar las 12 horas y 30 minutos del mediodía.
Es fácil construir un tipo “reloj”.
# type reloj = Hora of int*int;;
Y si queremos crear un reloj, usaremos el constructor “Hora” con el par que nos interese (por cierto, los constructores deben empezar por letra mayúscula):
# Hora (12,30);;
- : reloj = Hora (12, 30)

Quizás para algo tan sencillo no sería demasiado útil definir el tipo “reloj“, ya que a fin de cuentas los pares int*int y, en general cualquier tipo, ya existe en Ocaml sin necesidad de ser definido por el usuario. Pero debemos reflexionar sobre la naturaleza de los programas. Por sí mismo, ningún programa tiene sentido, sólo el que el usuario le otorgue. Yo puedo tener un programa con un montón de celdas numéricas que pueden comunicarse entre sí; aunque el sentido que yo le doy es que es una hoja de cálculo, o una base de datos, etc. Digamos que los tipos definidos por el usuario suponen la capa de información que conecta un programa con el sentido que un usuario vé en el mismo. Están ahí para aportar claridad al código y también para ayudarnos a abstraernos durante el desarrollo.

Esto nos lleva a pensar que los tipos definidos por el usuario son interesantes para trabajar de forma más comprensible con datos brutos. En la asignatura de PD, se ven para poder explicar cómo construir árboles en Ocaml, que no son más que otra forma de estructurar la información. El lenguaje ya “trae” incorporadas algunas estructuras, como las listas o las tuplas, pero no los árboles asi que… ¡¡Construyamos un árbol!!

Árboles
Como sabemos, un árbol puede almacenar cualquier dato, asi que nuestro árbol será un ‘a arbol (se lee alpha arbol). Esto pone sobre aviso al compilador de que nuestro dato es polimórfico, asi que:
# type 'a arbol =
Vayamos con la primera regla. Se trata el caso de que el árbol sea el árbol vacío con lo que no habrá que hacer nada. Simplemente ponemos un constructor vacío y pasamos a la siguiente regla.
# type 'a arbol =
        ArbolVacio
      |

Para el constructor del árbol, tenemos que pensar que se trata de una estructura de naturaleza recursiva. Cada nodo del arbol contiene un dato y de él derivan unos hijos, que a su vez son nodos con dato y más nodos hijos. De modo que, cada nodo es el par que contiene:
(dato, lista de nodos hijos)
En código, representamos el par de tipos con el simbolo *, tal y como lo haría Ocaml.
# type 'a arbol =
        ArbolVacio
      | ArbolNodo of 'a * 'a arbol list;;

Ahora podemos crear árboles vacíos:
# ArbolVacio;;
O árboles con raiz, pero ningún hijo en su lista:
# ArbolNodo ("dato_raiz", []);;
Fíjate que en este caso el tipo del árbol ya cambia para ser un árbol de strings, ya que en su raiz hemos guardado la cadena “dato_raiz”. Su lista de hijos es una lista vacía. Si quisiesemos añadir hijos, lo haríamos…
# ArbolNodo ("dato_raiz", [ ArbolNodo("dato_hijo1",[]) ; ArbolNodo("dato_hijo2", []) ] );;
He ahí un árbol con dos hijos. En la lista de cada uno de ellos podríamos añadir aún más nodos.
Llegados a este punto, es fácil saber como dar nombre a un elemento árbol. Solo tenemos que recurrir a un “let” normal y corriente, por ejemplo:
# let a1 = ArbolNodo ("dato_raiz", []);;

Árboles n-arios
En el ejemplo anterior, podríamos añadir hijos a la lista de hijos de un nodo de forma indefinida, porque estos estaban ubicados en una lista. Pero de nuevo nos asalta un problema. ¿Que pasa si queremos ceñirnos exclusivamente a árboles binarios (dos hijos por nodo como máximo)? ¿O a árboles ternarios (tres hijos por nodo como máximo)?
La solución pasa por sustituir la lista de la definición por alguna expresión que fije la cantidad de hijos de un árbol. Podemos pensar de nuevo en que un árbol binario viene dado por una terna en la que la primera componente es el dato de su raiz, la segunda su hijo por la izquierda y la tercera su hijo por la derecha.
(raiz, hijo_izda, hijo_dcha)
Definamos un arbol binario entonces, usando unos constructores con nombres distintos para no machacar los anteriores:
# type 'a arbolbin =
        ArbolbinVacio
      | ArbolbinNodo of 'a * 'a arbolbin * 'a arbolbin;;

¿Que ha cambiado? Además de los nombres, hemos sustituido una lista de elementos ‘a arbol por dos árboles ‘a arbolbin. El primero es el hijo de la izquierda y el segundo el de la derecha, tal y como habíamos razonado antes.
Un árbol ternario (tres hijos) sería simplemente una extensión de esta idea:
# type 'a arbolter =
        ArbolterVacio
      | ArbolterNodo of 'a * 'a arbolter * 'a arbolter * 'a arbolter;;

Por último, en un arbol genérico no sería legal hacer:
# ArbolNodo ("dato_raiz", ArbolVacio);;
porque la segunda componente del par debía ser una lista, y no un elemento ‘a arbol. Sin embargo ahora tenemos definidos el segundo y tercer elemento de la terna como árboles binarios ‘a arbolbin, así que sí podemos recurrir al constructor “ArbolbinVacio“:
# ArbolbinNodo ("dato_raiz", ArbolbinVacio, ArbolbinVacio);;

Por lo tanto, un árbol con dos hijos en el que el hijo de la derecha tenga a su vez otro hijo por la derecha…
# ArbolbinNodo ("raiz", ArbolbinNodo ("hijo_i", ArbolbinVacio, ArbolbinVacio), ArbolbinNodo ("hijo_d", ArbolbinVacio, ArbolbinNodo ("hijo_d_d", ArbolbinVacio, ArbolbinVacio)));;
Esto se correspondería con:

Algunos consejos definiendo árboles
Ya hemos hablado de dar nombres diferentes a los constructores para no machacar otros que hubiera previamente para otros tipos, pero hay otros consejos más. En la asignatura de PD de nuestra facultad, se suelen utilizar palabras en inglés como constructores, por ejemplo:
# type 'a bintree =
        Empty
      | Node of 'a * 'a bintree * 'a bintree;;

Se hace por convención, pero deberían explicarnos que las palabras se puede escojer a nuestro libre albedrío (respetando algunas limitaciones puntuales que no voy a explicar aquí pero que están reflejadas en el manual del lenguaje, como por ejemplo que el nombre comience por una letra mayúscula).
Con los árboles (y en general, con estructuras de datos) lo más normal sería definir un tipo polimórfico (que almacene cualquier dato) como vimos en la explicacion. Pero si queremos limitarlos a tan solo ser usados con, por ejemplo, enteros, bastaría con eliminar el alfa de nuestra definición. Este árbol solo podría guardar números enteros y nada más.
# type inttree =
        Empty
      | Node of int * inttree * inttree;;

Y la otra cosa importante es… ¡¡no liarse con los cierres de paréntesis, corchetes y demás parafernalia!! Así que ya sabes: trabaja con tu editor preferido y siempre que abras uno de ellos, escribe directamente a continuación su cierre. Imagínate un árbol de, pongamos, 5 niveles de altura. ¿Estás dispuesto a buscar cual puede ser el paréntesis que te falla? En serio, vale la pena ser ordenado al escribir código.

Nada más por ahora, aunque espero poder hacer una pequeña entrada sobre cómo trabajar con árboles y definir algunas funciones relacionadas. 🙂

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s