La recursión generalizada no funciona para la memoización de Haskell.
Después de leer varias fuentes, cree la siguiente función memo
para memoización en Haskell con “recursión generalizada”. Pero no funciona. ¿Por qué?!
fib f 0 = 1
fib f 1 = 1
fib f n = fib f (n - 1) + fib f (n - 2)
memo f n = fList !! n
where fList = map (f (fList !!)) [0..]
Ejecución recursiva sin memoización
λ> fix fib 30
1346269
(1.65 secs, 962,135,992 bytes)
Tarda lo mismo que una versión “memoizada”:
λ> memo fib 30
1346269
(1.62 secs, 962,141,192 bytes)
Sin embargo, lo siguiente funciona:
fibMemoDirect n = fibList !! n
where fibList = map fib [0..]
fib 0 = 1
fib 1 = 1
fib n = fibList !! (n - 1) + fibList !! (n - 2)
λ> fibMemoDirect 30
1346269
(0.01 secs, 93,728 bytes)
¿Por qué no funciona memo fib
como fibMemoDirect
, dado que ambos usan CAF?
Fuentes:
davy.ai
La razón por la cual la función
memo
de la serie de Fibonacci no funciona tan rápido como la funciónfibMemoDirect
es debido a la forma en que se implementa la funciónmemo
. La funciónmemo
utiliza las funcionesmap
y!!
para memoizar la función. El problema con esto es que cada vez que se necesita el resultado, la funciónmap
se evalúa hasta ese punto, lo cual puede ser muy costoso para números grandes.En contraste, la función
fibMemoDirect
utiliza un enfoque directo donde se calcula una lista de números de Fibonacci que se utiliza para memoizar. Esto es mucho más eficiente porque la lista se calcula solo una vez, y cada llamada posterior solo necesita recuperar el valor precalculado.Por lo tanto, se puede mejorar la función
memo
generando una lista de valores hasta el argumenton
en lugar de usar las funcionesmap
y!!
.