Estructuras de datos recursivas en Haskell y Scala, segunda parte

Vamos a ejemplificar lo que vimos en el post anteríor con un ejemplo de árbol binario de búsqueda. Si no estás familiarizado con los árboles binarios de búsqueda de otros lenguajes como C, aquí tienes una explicación de lo que son: un elemento apunta a otros dos elementos, uno esta a la izquierda y otro a la derecha. El elemento a la izquierda es más pequeño y el segundo es más grande. Cada uno de estos dos elementos puede apuntar a otros dos elementos (o a uno o a ninguno). En efecto, cada elemento tienen sus propios sub-árboles. Lo bueno de los árboles binarios de búsqueda es que sabemos que todos los elementos que están en el sub-árbol de la izquierda de, 5, por ejemplo, son menores que 5. Lo elementos que están en el sub-árbol de la derecha son mayores. Así que si estamos buscando el elemento 8 en nuestro árbol, empezamos comparándolo con 5, como vemos que es menor que 5, nos vamos al sub-árbol de la derecha. Ahora estaríamos en 7, como es menor que 8 continuaríamos hacia la derecha. De esta forma encontraríamos el elemento en tres pasos. Si estuviéramos usando una lista (o un árbol no balanceado), nos hubiera costado unos 7 pasos encontrar el 8.

Los conjuntos y diccionario de Data.Set y Data.Map de Haskell están implementandos utilizando árboles, solo que en lugar de árboles binarios de búsqueda, utilizan árboles binarios de búsqueda balanceados, de forma que estén siempre balanceados. Ahora implementaremos simplemente árboles binarios de búsqueda normales.

Vamos a decir que: un árbol es o bien un árbol vacío o bien un elemento que contiene un elemento y otros dos árboles. Tiene pinta de que va a encajar perfectamente con los tipos de datos algebraicos.

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Read, Eq)

Esto en Scala podríamos implementarlo con Clases Case, o con herencia también funcionaría pero voy a utilizar  Clases Case:

abstract class Tree
case class EmptyTree extends Tree
case class Node (nro: Int, left: Tree, rigth: Tree) extends Tree

En lugar de construir manualmente un árbol, vamos a crear una función que tome un elemento y un árbol e inserte dicho elemento en su posición adecuada dentro del árbol. Hacemos esto comparando el elemento que queremos insertar con la raíz del árbol y si es menor, vamos a la izquierda y si no a la derecha. Hacemos lo mismo para coda nodo siguiente hasta que alcanzamos un árbol vacío. Cuando lo hagamos simplemente insertamos el elemento en lugar del árbol vacío.

En lenguajes como C, realizamos esta tarea modificando los punteros y valores del árbol. En Haskell, no podemos modificar nuestro árboles, así que tenemos que crear un nuevo sub-árbol cada vez que decidamos si vamos a la derecha o a la izquierda y al final la función de inserción devolver un árbol completamente nuevo, ya que Haskell no tiene el concepto de puntero. Así pues la declaración de tipo de nuestra función será algo como a -> Tree a - > Tree a. Toma un elemento y un árbol y devuelve un nuevo árbol que posee en su interior dicho elemento.

Aquí tienes dos funciones. Una de ellas es una función auxiliar para crear un árbol unitario (que solo contiene un elemento) y la otra es una función que inserta elementos en un árbol.

singleton :: a -> Tree a
singleton x = Node x EmptyTree EmptyTree

treeInsert :: (Ord a) => a -> Tree a -> Tree a
treeInsert x EmptyTree = singleton x
treeInsert x (Node a left right)
    | x == a = Node x left right
    | x < a  = Node a (treeInsert x left) right
    | x > a  = Node a left (treeInsert x right)

La función singleton es forma rápida de crear un árbol que contenga un elemento y dos sub-árboles vacíos. En la función de inserción, tenemos como primer patrón el caso base. Si hemos alcanzado un sub-árbol vacío, esto significa que estamos donde queríamos y en lugar de un árbol vacío, queremos un árbol unitario que contenga el elemento a insertar. Si no estamos insertando el elemento en un árbol vacío tenemos que comprobar varias cosas. Primero, si el elemento que vamos a insertar es el mismo que la raíz del sub-árbol, simplemente devolvemos el árbol como estaba. Si es menor, devolvemos un árbol que tenga la misma raíz, el mismo sub-árbol derecho pero en lugar de su sub-árbol izquierdo, ponemos el árbol que va a contener dicho elemento. Lo mismo ocurre (pero en sentido contrario) para los valores que son mayores que el elemento raíz.

En Scala podemos hacer un método que con pattern matching saber que clase es:

  def treeInsert(nro:Int, tree: Tree) : Tree = tree match {
    case EmptyTree => Node (nro, EmptyTree(), EmptyTree())
    case Node (nroTree, left, right) => if (nroTree == nro)  Node (nro, left, right)
                                                           else if (nro < nroTree)  Node (nroTree, treeInsert(nro, left), right)
                                                           else Node (nroTree, left, treeInsert(nro, right))  
  }

A continuación vamos a crear una función que compruebe si un elemento pertence a un árbol. Primero vamos a definir el caso base. Si estamos buscando un elemento en un árbol vacío, obviamente el elemento no está ahí. Vale, fíjate que esto es básicamente lo mismo que el caso base de la búsqueda en listas: si estamos buscando un elemento en una lista vacía, obviamente el elemento no está ahí. De todos modos, si no estamos buscando el elemento en un árbol vacío, entonces tenemos que hacer varias comprobaciones. Si el elemento que estamos buscando es el elemento raíz ¡Genial! ¿Y si no lo es? Bueno, tenemos la ventaja de que sabemos que todos los elementos menores que la raíz están en el sub-árbol izquierdo. Así que si el elemento que estamos buscando es menor que la raíz, comprobamos si el elemento está en el sub-árbol izquierdo. Si es mayor, comprobamos el sub-árbol derecho.

treeElem :: (Ord a) => a -> Tree a -> Bool
treeElem x EmptyTree = False
treeElem x (Node a left right)
    | x == a = True
    | x < a  = treeElem x left
    | x > a  = treeElem x right

En Scala:

  def treeElem(nro:Int, tree: Tree) : Boolean = tree match {
    case EmptyTree => false
    case Node (nroTree, left, right) => if (nroTree == nro)  true
                                                           else if (nro < nroTree)  treeElem(nro, left)
                                                           else treeElem(nro, right)
  }

¡Vamos a divertirnos con nuestro árboles! En lugar de construir manualmente un árbol (aunque podríamos), usaremos un pliegue para construir un árbol a partir de una lista. Recuerda, casi cualquier cosa que recorra una lista elemento a elemento y devuelve alguna especie de valor puede ser implementado con un pliegue. Empezaremos con un árbol vacío y luego recorreremos la lista desde la derecha e iremos insertando elementos a nuestro árbol acumulador.

ghci> let nums = [8,6,4,1,7,3,5]
ghci> let numsTree = foldr treeInsert EmptyTree nums
ghci> numsTree
Node 5 (Node 3 (Node 1 EmptyTree EmptyTree) (Node 4 EmptyTree EmptyTree)) (Node 7 (Node 6 EmptyTree EmptyTree) (Node 8 EmptyTree EmptyTree))

En este foldr, treeInsert es la función de pliegue (toma un árbol y un elemento de la lista y produce un nuevo árbol) y EmptyTree es el valor inicial. Por supuesto, nums es la lista que estamos plegando.
No es muy legible el árbol que se muestra por la consola, pero si lo intentamos, podemos descifrar su estructura. Vemos que el nodo raíz es 5 y luego tiene dos sub-árboles, uno que tiene como elemento raíz a 3, y otro a 7.

ghci> 8 `treeElem` numsTree
True
ghci> 100 `treeElem` numsTree
False
ghci> 1 `treeElem` numsTree
True
ghci> 10 `treeElem` numsTree
False

Vamos que comprobar la pertenencia de un elemento a un árbol funciona perfectamente. Genial.
Como puede ver los tipos de datos algebraicos en Haskell son un concepto muy interesante a la vez potentes. Podemos utilizarlos desde para representar valores booleanos hasta enumeraciónes de los días de la semana, e incluso árboles binarios de búsquedas.