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: TreesSolving the repMin problem with I/O
