memoization con recursividad

Question

Estoy tratando de entender Haskell realization of memoization, pero no entiendo como funciona:

memoized_fib :: Int -> Integer 
memoized_fib = (map fib [0..] !!) 
    where fib 0 = 0 
       fib 1 = 1 
       fib n = memoized_fib(n - 2) + memoized_fib(n - 1) 

Primero de todo lo que aún no entiendo por qué 'map'-función de obtener tres parámetros (función - fib, list [0 ..] y ||), pero no dos cómo debe hacer.

Actualizado:

he tratado de reescribir el código, pero conseguir el resultado diferente:

f' :: (Int -> Int) -> Int -> Int 
f' mf 0 = 0 
f' mf 1 = 1 
f' mf n = mf(n - 2) + mf(n - 1) 

f'_list :: [Int] 
f'_list = map (f' faster_f') [0..] 

faster_f' :: Int -> Int 
faster_f' n = f'_list !! n 

¿Por qué? ¿Hay algún error en mi razonamiento?

Answer 1

Primero: Haskell admite secciones de operador. Entonces (+ 2) es igual a \ x -> x + 2. Esto significa que la expresión con map es igual a \ x -> map fib [0..] !! x.

En segundo lugar, cómo funciona esto: esto se está aprovechando de la estrategia de evaluación de call-by-need de Haskell (su pereza).

Inicialmente, la lista que resulta de map no se evalúa. Luego, cuando necesite llegar a un índice en particular, todos los elementos hasta ese punto serán evaluados. Sin embargo, una vez que se evalúa un elemento, no se vuelve a evaluar (siempre que se refiera al mismo elemento). Esto es lo que te da la memoria.

Básicamente, la estrategia de evaluación perezosa de Haskell implica la memorización de valores forzados. Esta función memorada fib solo se basa en ese comportamiento.

Aquí "forzar" un valor significa evaluar una expresión diferida llamada thunk. Así que la lista básicamente se almacena inicialmente como una "promesa" de una lista, y forzarla convierte esa "promesa" en un valor real, y una "promesa" de más valores. Las "promesas" son solo estocadas, pero espero que llamarlas una promesa tenga más sentido.

Estoy simplificando un poco, pero esto debería aclarar cómo funciona la memorización real.

Answer 2

map no toma tres parámetros aquí.

(map fib [0..] !!) 

parcialmente aplica (rodajas) La función (!!) con map fib [0..], una lista, como su primer argumento (izquierda).

Answer 3

Tal vez sea más clara escrito como:

memoized_fib n = (map fib [0..]) !! n 

por lo que es simplemente tomar la ésimo elemento n de la lista, y la lista se evalúa con pereza.

Esto operator section es exactamente lo mismo que la aplicación parcial normal, pero para operadores de infijo. De hecho, si escribimos la misma forma con una función regular en lugar del operador infijo !!, ver cómo se ve:

import Data.List (genericIndex) 

memoized_fib :: Int -> Integer 
memoized_fib = genericIndex (map fib [0..]) 
    where fib 0 = 0 
       fib 1 = 1 
       fib n = memoized_fib(n - 2) + memoized_fib(n - 1)