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"

Marge en Internet

No sé cómo me olvidé de postear este video:



Este no lo había visto:

Ay, una candelabra precariosa

Sabía que en la versión original de "Los Simpson", el Hombre Abejorro (Bumble Bee Man) hablaba en un pseudo-español, pero nunca lo había escuchado, y encontré el video de esa escena que siempre me pareció graciosa.



Según los productores, la mala pronunciación es a propósito, aunque no entiendo que pretende satirizar.

Cuando Funcional casi me defrauda (1º parte)

El otro día estaba en lo de un amigo que cursa Programación. Y encontré una explicación de práctica que me puse a revisar.

El problema consistía en: Dado un árbol binario no ordenado de productos (código, precio), informar el código del producto de mayor precio.

Código Pascal

   1:type
   2:  producto =
   3:    record
   4:      codigo : integer;
   5:      precio : real;
   6:    end;
   7:
   8:  arbol = ^nodo;
   9:  nodo =
  10:    record
  11:      dato : producto;
  12:      izq, der : arbol;
  13:    end;                        
  14:
  15:function codProdMax (a : arbol) : integer;
  16:var
  17:  max : real;
  18:  cod : integer;
  19:
  20:begin
  21:  max := -1;
  22:  cod := -1;    
  23:  verPrecioMax(a, max, cod);
  24:  codProdMax := cod;
  25:end;
  26:
  27:procedure verPrecioMax (a : arbol; var max : real; 
  28:                                        var cod : integer);
  29:begin
  30:  if (a <> nil) then
  31:    begin
  32:      if (a^.dato.precio > max) then
  33:        begin
  34:          max := a^.dato.precio;
  35:          cod := a^.dato.codigo;
  36:        end
  37:      verPrecioMax(a^.izq, max, cod);
  38:      verPrecioMax(a^.der, max, cod);   
  39:    end;
  40:end;

Por alguna razón, quizá estaba muy al pedo, se me ocurrió hacerlo en Haskell, y me quedó algo así:

   1:data Arbol a = Empty | Arbol a (Arbol a) (Arbol a)
   2:
   3:data Producto = Producto Int Float deriving (Eq, Show)
   4:
   5:codigo :: Producto -> Int
   6:codigo (Producto c p) = c
   7:
   8:precio :: Producto -> Float
   9:precio (Producto c p) = p
  10:
  11:
  12:maxProd :: Producto -> Producto -> Producto
  13:maxProd p1 p2 =
  14:        if precio p1 > precio p2 then
  15:                p1
  16:        else
  17:                p2

La función se podría haber hecho a partir de un fold sobre el árbol, pero quería probarlo rápido, así que hice una especie de pseudofold:

   1:funcArbol :: (a -> a -> a) -> a -> Arbol a -> a
   2:funcArbol f valor Empty = valor
   3:funcArbol f valor (Arbol x t1 t2) = 
   4:        f x (f (funcArbol f valor t1) (funcArbol f valor t2))
   5:
   6:maxProdArbol = funcArbol maxProd (Producto 0 0.0)

Se puede hacer algo más directo, pero ya no estoy acostumbrado:

   1:maxProdArbol :: Arbol Producto -> Producto
   2:maxProdArbol Empty = Producto 0 0.0
   3:maxProdArbol (Arbol x t1 t2) = 
   4:        maxProd x (maxProd 
   5:                        (maxProdArbol t1) (maxProdArbol t2))

Continuará...

Code Monkey

Creo que este es el original:



Code Monkey Lyrics

Test de ideología

Siguiendo con esa mala costumbre de completar todos los tests que encuentro, por más boludos que sean, hice este de "Cuál es tu ideología". Por no tener una forma práctica de bajar la imagen los cago y explico la lógica del test. Supuestamente la vieja clasificación izquierda-derecha es simplista e irreal, ya que se dificulta cómo clasificar a la gente.

El test clasifica de acuerdo a las ideas económicas y político-sociales, sobre las abscisas (líneas horizontales) va la posición en economía (de -10, todo colectivo, a 10, todo privatizado), y sobre las ordenadas (líneas verticales), la posición "social"(de -10, anarquía total, a 10, superdespotismo).

Mi puntuación (es el punto rojo en el plano):

Your political compass
Economic Left/Right: 6.88
Social Libertarian/Authoritarian: -7.59

El test creo que algunas preguntas son un poco tendenciosas/ambigüas y me parece que no contempla la posibilidad de ser anarquista clásico (estilo Bakunin). Habría que hacer alguno más completo.

El test está en:
Test de ideología(inglés)
Test de ideología(español)

Arte con ensamblador

Esta idea que vi en Internet me pareció muy original. Ben Fry toma el código de viejos juegos realizados para el Atari 2600, reemplazando cada salto por una línea, y haciendo cosas parecidas con los bloques de datos. Desde lejos parecen figuras.

Distellamap

Generador de libros de Dan Brown

Leí un par de libros de Dan Brown, el escritor de "El Código Da Vinci". Tengo que reconocerlo, son entretenidos y atrapantes, pero me cansó el hecho de que sean todos iguales. Leí todos los libros de él, menos "La Conspiración", porque me aburrió el mismo patrón. Es como que hay en algún lado una clase DanBrownBook, y el tipo la instancia y crea libros.

En resumen, en Internet encontré este generador de argumentos de libros de Dan Brown, bastante gracioso.

Crea tu propia novela de Dan Brown