Come funziona questa funzione fibonacci memoizzata?

Question

Nell'attribuzione dell'esercizio corrente del corso di Programmazione funzionale che sto facendo, dobbiamo creare una versione memoizzata di una determinata funzione. Per spiegare Memoizzazione, il seguente esempio è dato:

fiblist = [ fibm x | x <- [0..]] 

fibm 0 = 0 
fibm 1 = 1 
fibm n = fiblist !! (n-1) + fiblist !! (n-2) 

Ma io non comprendere appieno come funziona.

Chiamiamo fibm 3.

fibm 3 
--> fiblist !! 2 + fibList 1 
--> [fibm 0, fibm 1, fibm 2] !! 2 + [fibm 0, fibm 1] !! 1 
--> fibm 2 + fibm 1 
--> (fiblist !! 1 + fiblist 0) + 1 
--> ([fibm 0, fibm 1] !! 1 + [fibm 0] !! 0) + 1 
--> (fibm 1 + fibm 0) + 1 
--> 1 + 0 + 1 
--> 2 

Da altre domande/risposte e googling ho imparato che in qualche modo, il fiblist valutato è condivisa tra le chiamate.

Ciò significa che, ad esempio, per fiblist !! 2 + fiblist !! 1, i valori di elenco vengono calcolati una sola volta per fiblist !! 2 e quindi vengono riutilizzati per fiblist !! 1?

Quindi i due numeri di Fibonacci vengono calcolati solo una volta per chiamata, quindi nessun numero esponenziale di chiamate. Ma per quanto riguarda i livelli "inferiori" della chiamata nella funzione fiblist? In che modo beneficiano del calcolato fiblist nella chiamata originale fibm?

Answer 1

La parte cruciale qui è che la lista viene pigramente valutata, il che significa che l'elemento non viene calcolato fino alla prima richiesta. Una volta che è stato valutato, tuttavia, è lì per qualsiasi altra cosa da cercare. Quindi, nel tuo esempio, hai ragione nel dire che i valori vengono calcolati una sola volta per il fiblist !! 2 e quindi riutilizzati per fiblist !! 1.

I "livelli inferiori" della funzione fiblist funzionano allo stesso modo. La prima volta che chiamo fiblist !! 1 verrà valutata chiamando fibm 1, che è solo 1, e questo valore rimarrà nella lista. Quando si tenta di ottenere il numero più alto di Fibonacci, lo fiblist chiamerà il numero fibm che cercherà quei valori nelle posizioni inferiori - e potenzialmente già valutate - di fiblist.

Answer 2

Esaminiamo passo dopo passo la valutazione. Oltre a mostrare l'espressione corrente, mostriamo lo stato attuale di valutazione di fiblist in memoria. Lì, scrivo <expr> per indicare un'espressione non valutata (spesso chiamata thunk) e >expr< per indicare un'espressione non valutata che è attualmente in fase di valutazione. Puoi vedere la valutazione pigra in azione. L'elenco viene valutato solo per quanto richiesto e le subcomputazioni che verranno completate saranno condivise per il riutilizzo futuro.

Current expression      Current evaluation state of fiblist 

    fibm 3         <[ fibm x | x <- [0..] ]> 

-> (simple expansion of the definition) 

    fiblist !! (3-1) + fiblist !! (3-2)  <[ fibm x | x <- [0..] ]> 

-> ((+) has to evaluate both its arguments to make progress, let's assume 
    it starts with the left argument; (!!) traverses the list up to the given 
    element and returns the element it finds) 

    fibm 2 + fiblist !! (3-2)    <fibm 0> : <fibm 1> : >fibm 2< : <[ fibm x | x <- [3..] ]> 

-> (simple expansion of the definition) 

    (fiblist !! (2-1) + fiblist !! (2-2)) + fiblist !! (3-2) 
              <fibm 0> : <fibm 1> : >fibm 2< : <[ fibm x | x <- [3..] ]> 

-> (we again start with the first argument to (+), 
    computing the result of (!!) does not cause any 
    further evaluation of fiblist) 

    (fibm 1 + fiblist !! (2-2)) + fiblist !! (3-2) 
              <fibm 0> : >fibm 1<:>fibm 2< : <[ fibm x | x <- [3..] ]> 

-> (expanding fibm 1 returns a result immediately; 
    this concludes the computation of fibm 1, 
    and the thunk is updated with the result) 

    (1 + fiblist !! (2-2)) + fiblist !! (3-2) 
              <fibm 0> : 1 : >fibm 2< : <[ fibm x | x <- [3..] ]> 

-> (now we compute fiblist !! (2-2)) 

    (1 + fibm 0) + fiblist !! (3-2)   >fibm 0< : 1 : >fibm 2< : <[ fibm x | x <- [3..] ]> 

-> (expanding fibm 0 returns 0 immediately, and the 
    corresponding thunk can be updated) 

    (1 + 0) + fiblist !! (3-2)    0 : 1 : >fibm 2< : <[fibm x | x <- [3..] ]> 

-> (we can compute the (+), yielding the result of 
    fibm 2; the corresponding thunk is updated) 

    1 + fiblist !! (3-2)      0 : 1 : 1 : <[fibm x | x <- [3..] ]> 

-> (now the right argument of (+) has to be evaluated, but (!!) 
    will return the already evaluated list element directly) 

    1 + 1         0 : 1 : 1 : <[fibm x | x <- [3..] ]> 

-> (arithmetic; note that as we called fibm 3 directly in the 
    beginning, instead of fiblist !! 3, the list is unaffected 
    by this final result) 

    2          0 : 1 : 1 : <[fibm x | x <- [3..] ]> 

Come fiblist è una costante globale (spesso chiamato CAF a "forma applicativa costante"), allo stato parzialmente valutato dell'elenco persisterà e chiamate future fibm sarà riutilizzare elementi già valutati della lista. L'elenco alla fine diventerà sempre più grande, consumando sempre più memoria.