Cuando Funcional casi me defrauda (2º parte)

¿Por qué el título del post?
Porque hubo algunos problemas que no pude resolver con funcional de forma eficiente. Uno que me molestaba hasta hace poco era el siguiente: Dado un árbol binario no ordenado, buscar un elemento en el mismo.

En Pascal

1º versión

   1:function existe (a : arbol; codigo : integer) : boolean;
   2:begin
   3:  if (a = nil) then
   4:    existe := false
   5:  else
   6:    if (a^.dato.codigo = codigo) then
   7:      existe := true
   8:    else
   9:      existe := 
  10:        existe(a^.izq, codigo) or existe(a^.der, codigo);
  11:end;
  12:

2º versión : "optimizada"

   1:procedure existe (a : arbol; cod : integer; 
   2:                                var encontrado : boolean);
   3:begin
   4:  if (a = nil) then
   5:    encontrado := false
   6:  else
   7:    if not encontrado then
   8:      if (a^.dato.codigo = codigo) then
   9:        encontrado := true
  10:      else      
  11:        begin
  12:          existe(a^.izq, cod, encontrado);
  13:          existe(a^.der, cod, encontrado);
  14:        end;                            
  15:end;

La supuesta ventaja de esta solución es que termina de recorrer el árbol, ni bien encuentra el código que buscaba.

En Haskell

1)

   1:existe :: Eq a => Arbol a -> a -> Bool
   2:existe Empty valor = False
   3:existe (Arbol x izq der) valor = 
   4:        if x == valor then
   5:                True
   6:        else
   7:                (existe izq valor) || (existe der valor)

La "desventaja" de esta solución que incluso si encuentra el elemento en uno de los subárboles, lo sigue buscando en el otro, ya que no se tiene forma de saber si se encontró.

2) En esta solución, se transforma el árbol en una lista y se busca el elemento en la lista.

   1:aplanar :: Arbol a -> [a]
   2:aplanar Empty = []
   3:aplanar (Arbol x izq der) = aplanar izq ++ [x] ++ aplanar der
   4:
   5:existe :: Eq a => a -> Arbol a -> Bool
   6:existe e = (elem e).aplanar

Esta solución termina cuando encuentra el elemento, pero si el elemento no está, recorre el árbol dos veces.

Nota: El uso de lazy evaluation en Haskell puede distorsionar los cálculos.

Nunca pude encontrar una solución mejor a esas dos para resolver ese problema. Si a alguien se le ocurro alguna con gusto la posteo.

Sin embargo mientras buscaba una solución, me di cuenta de que el problema no tenía sentido. Llegué a pensar: "Si con funcional no se puede resolver elegantemente, es que no tiene sentido resolverlo". Reflexiones aparte, me puse a pensar que era lo que se hacía con la estructura, y la respuesta es: se realizan operaciones que requieren recorrer toda la estructura en el peor caso.

Estaba tratando de buscar la solución a un problema mal planteado. No tenía sentido usar un árbol binario no ordenado, sino que había que usar la vieja lista. De hecho en el único ámbito en que los árboles binarios no ordenados son útiles es en la construcción del árbol sintáctico durante el parsing.

Además la supuesta optimización no es tal, ya que la 1º solución en Haskell, al utilizar lazy evaluation (e inclusive en Pascal con los operadores short-circuit), deja de recorrer el árbol al encontrar el elemento buscado. El único caso en que está optimización es útil, es cuando la búsqueda se realiza en paralelo en ambos subárboles, utilizando concurrencia recursiva.

Esa es una de las cosas más importantes que aprendí en Funcional: las estructuras de datos se definen en base a las operaciones que proveen. Recordando un ejemplo dado en la teoría: "Si a mí me traen expedientes, pero nunca los vienen a buscar, tranquilamente puedo prenderlos fuego"