27 de febrero de 2008

Evaluación Perezosa

Hoy quisiera hablar de una de las características de Haskell más fascinantes, la evaluación perezosa. Y me han entrado ganas de hablar de ello al ver la utilización que se da a la evaluación perezosa en el problema repMin de Richard Bird. El problema viene a ser el siguiente: reemplazar los valores en los nodos de un árbol por el mínimo valor de este mismo árbol, y solo recorriendo el árbol una sola vez.

Yo voy a explicarlo con una estructura más sencilla, sustituir todos los valores de una lista de números por el mínimo valor de esta lista, recorriendo la lista una sola vez. Y esto usando de manera muy inteligente la evaluación perezosa. Vamos a empezar contando que es la evaluación perezosa (lazy).

Evaluación Perezosa

En los lenguajes de programación tradicionales, lo que tenemos es evaluación ansiosa (eager). Con este tipo de evaluación, cuando asignamos un valor a una variable, o pasamos un parámetro a una función, se calcula cual es el valor final a asignar o cual es el valor final del parámetro. Por ejemplo:

v = sqrt(2) + 3 * sqrt(5);

f( 4 / g( 7 ) );

Antes de asignar nada a v, se llamara a las funciones sqrt con sus parámetros correspondientes, luego se aplicara la expresión matemática para obtener el valor final a asignar a v. En el caso de la llamada a la función f, antes se ha de llamar a la función g y dividir entre 4 el resultado de esta llamada. Por eso se denomina evaluación perezosa, porque se ha de obtener el valor de las expresiones en cuanto el programa se las encuentra.

La evaluación perezosa solo calcula el valor de las expresiones cuando necesita hacer uso de este valor. En el código de ejemplo anterior, en v se guardaría como se calcula su valor y no el valor final. Y el parámetro pasado a f sería la formula completa y no el valor de aplicar la expresión. Si resulta que ni la variable v ni el parámetro de la función f se usan, pues nunca se llamaría a las funciones sqrt y g, ni se realizarían las operaciones matemáticas pertinentes.

Esto puede suponer una diferencia enorme entre ejecutar con evaluación perezosa y evaluación ansiosa. Si tenemos definidas f y g como:

int f( int a ){
return 4;
}
int g( int a ){
return a - 7;
}

Con evaluación ansiosa obtendríamos un error "division by zero" mientras que con evaluación perezosa la ejecución terminaría sin error.

ReplaceMin

La primera versión que podemos pensar de replaceMin es la que pongo a continuación:

replaceMin xs = replace xs (minimum xs)
where replace xs m = map (\a -> m) xs

Primero se calcula el mínimo de la lista de números xs y luego se sustituye todos los valores de esta lista por el valor mínimo (usando la función replace). Esta primera versión recorre la lista dos veces, una vez para calcular el mínimo y una segunda vez para reemplazar los valores.

Y ahora viene lo verdaderamente impresionante. La versión de replaceMin que recorre la lista una sola vez:

replaceMin xs = ys
where (ys, m) = rpMin xs m

¿Y como funciona? Gracias a la evaluación perezosa. Entendiendo lo que hace la función rpMin, lograremos entender como funciona. La función rpMin tiene dos parámetros, una lista de números xs y un numero m. Lo que hace rpMin es sustituir todos los valores de xs por m (igual que replace) con el añadido de que a la vez va calculando el mínimo de xs. La función rpMin devuelve una tupla con la nueva lista con los valores sustituidos y con el mínimo de la antigua lista.

La magia ocurre en la manera de llamar a rpMin desde la función replaceMin, como valor a sustituir se le pasa el mínimo que todavía no ha calculado rpMin y del cual no necesita saber su valor. Básicamente la conversación entre las dos funciones seria:
  • replaceMin: sustituyeme todos los valores de xs por este valor m del que de momento no se nada
  • rpMin: ¿Pero como? ¡Necesitare saber el valor de m para ponerlo en la lista!
  • replaceMin: ¡No hombre, no! Recuerda que nosotros tenemos evaluación perezosa.
  • rpMin: Bueno, pues tu sabrás cual es el valor de m, ya se lo dirás al que quiera usar la lista resultante.
  • replaceMin: ¡Te vuelves a equivocar! El valor me lo dirás tu, cuando calcules el mínimo de xs.

El valor de m solo será necesario fuera de la función replaceMin, por ejemplo cuando se imprima la lista resultante por pantalla, y para entonces rpMin ya habrá calculado el mínimo.

Esta sería la definición de rpMin. Simplemente va sustituyendo los valores de la lista por el valor m pasado como parámetro, y mientras va calculando el mínimo comparando cada valor de la lista con el mínimo hasta ese momento. Y todo recorriendo la lista una sola vez.

rpMin [x] m = ([m], x)
rpMin (x:xs) m = (m:ys, min x my)
where (ys, my) = rpMin xs m

Bueno, os dejo pensando en porqué funciona. O podeis probarlo por vosotros mismos en vuestra distribución de Haskell favorita. También os dejo los enlaces a las versiones de replaceMin para arboles.

Referencias:
Functional Pearl: Trees
Solving the repMin problem with I/O

6 comentarios:

marcoil dijo...

La evaluación perezosa es muy interesante, pero el ejemplo concreto es muy fácil de implementar en lenguages con evaluación ansiosa. Por ejemplo, en Scheme:

(define (cons-min-rec l m)
(if (null? l)
(list m)
(let ((ln (cons-min-rec (cdr l) (min (car l) m))))
(cons (car ln) ln))))

(define (cons-min l)
(cons-min-rec (cdr l) (car l)))

En lenguages que permiten múltiples resultados es todavía más fácil, pues no es necesario guardar temporalmente el resultado interno en cons-min-rec. Esta técnica se usa mucho en Lisp para construir listas.

Por cierto, el Blogger me destroza la indentación en el código.

Luis Cabellos dijo...

He pensado en la versión en Scheme con evaluación ansiosa (la he probado incluso en drscheme). Y funciona. Por lo que entiendo, va calculando el mínimo recorriendo la lista hasta llegar a la lista vacía, y al volver de la recursión va arrastrando el mínimo y recreando la lista con este valor.

El problema lo tienes cuando quieres aplicar la misma idea a un árbol en vez de a una lista. Con el ejemplo de Scheme acabarías teniendo diferentes mínimos en cada sub-árbol. Sin embargo, con evaluación perezosa seguiría funcionando.

Pongo el ejemplo de como seria con una estructura de árbol binario, con valores solo en las hojas. ReplaceMin es igual, solo cambia rpMin.

rpMin (Leaf x) m = (Leaf m, x)
rpMin (Branch l r) m = (Branch ll rr, min ml mr)
____where (ll,ml) = rpMin l m
__________(rr,mr) = rpMin r m

Cierto, Blogger destroza la identacion, pero por suerte, Scheme no necesita de ella para funcionar (al contrario que Haskell, por lo que usado guiones bajos para formatear el ejemplo)

Marsano dijo...

XD

Truco para añadir mas de un espacio en html, es usar los non-breaking space "   "

De esta forma podemos identar...

editor de texto:
if a == b:
    expresion 1
    expresion 2
    ...
    expresion n
else:
    expresion 1
    expresion 2
    ...
    expresion n

Visualizacion:
if a == b:
    expresion 1
    expresion 2
    ...
    expresion n
else:
if a == b:
    expresion 1
    expresion 2
    ...
    expresion n

... Lamento el offtopic, pero de mas ke le sirve alguien algun dia xD

señor clorofila dijo...

Hola Luis,

Muy interesante la entrada. Curso ingeniería en informática y este ejemplo me vendrá muy bien para una presentación que tengo que realizar sobre Haskell. Gracias por la explicación!

Un saludo y felicitaciones por el blog,

Sr. Clorofila

Luis Cabellos dijo...

señor clorofila, otro ejemplo para impresionar con la evaluación perezosa es:

minimum = head . sort

Coje el mínimo de una lista pero tardando o(N) en vez del esperado o(N log N) que tarda el algoritmo de ordenar.

Anónimo dijo...

Sí, si muy... ¿curioso? será. Pero es increíblemente más lento con la segunda implementación.