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
memode la serie de Fibonacci no funciona tan rápido como la funciónfibMemoDirectes debido a la forma en que se implementa la funciónmemo. La funciónmemoutiliza las funcionesmapy!!para memoizar la función. El problema con esto es que cada vez que se necesita el resultado, la funciónmapse evalúa hasta ese punto, lo cual puede ser muy costoso para números grandes.En contraste, la función
fibMemoDirectutiliza 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
memogenerando una lista de valores hasta el argumentonen lugar de usar las funcionesmapy!!.