Qualcuno può spiegare il concetto dietro la memoizzazione di Haskell?

Solo per spiegare i meccanismi alla base della memoizzazione effettiva,

memo_fib = (map fib [1..] !!)

produce un elenco di "thunk", calcoli non valutati. Pensa a questi come regali non aperti, finché non li tocchiamo, non correranno.

Ora, una volta valutato un thunk, non lo valuteremo mai più. Questa è in realtà l'unica forma di mutazione in "normale" haskell, i thunks mutano una volta valutati per diventare valori concreti.

Quindi, tornando al tuo codice, hai una lista di thunk, e continui a fare questa ricorsione dell'albero, ma ricorri usando l'elenco, e una volta valutato un elemento nella lista, non viene mai più calcolato. Così, evitiamo la ricorsione dell'albero nella fasulla funzione ingenua.

Come nota tangenzialmente interessante, questo è particolarmente veloce su una serie di numeri di fibonnaci calcolati poiché tale lista viene valutata solo una volta, il che significa che se si calcola memo_fib 10000 due volte, la seconda volta dovrebbe essere istantanea. Questo perché Haskell ha valutato gli argomenti solo una volta e si sta utilizzando un'applicazione parziale anziché una lambda.

TLDR: memorizzando i calcoli in un elenco, ogni elemento dell'elenco viene valutato una volta, pertanto, ogni numero di fibonnacci viene calcolato esattamente una volta per l'intero programma.

Visualizzazione:

 [THUNK_1, THUNK_2, THUNK_3, THUNK_4, THUNK_5]
 -- Evaluating THUNK_5
 [THUNK_1, THUNK_2, THUNK_3, THUNK_4, THUNK_3 + THUNK_4]
 [THUNK_1, THUNK_2, THUNK_1 + THUNK_2, THUNK_4, THUNK_3 + THUNK_4]
 [1, 1, 1 + 1, THUNK_4, THUNK_3 + THUNK_4]
 [1, 1, 2, THUNK_4, 2 + THUNK4]
 [1, 1, 2, 1 + 2, 2 + THUNK_4]
 [1, 1, 2, 3, 2 + 3]
 [1, 1, 2, 3, 5]

Quindi puoi vedere come per la valutazione di THUNK_4 è molto più veloce dato che le sottoespressioni sono già state valutate.

Il punto di memoizzazione non è mai quello di calcolare la stessa funzione due volte - questo è estremamente utile per accelerare i calcoli che sono puramente funzionali, cioè senza effetti collaterali, perché per quelli il processo può essere completamente automatizzato senza intaccare la correttezza. Ciò è particolarmente necessario per funzioni come fibo , che portano a ricorsione dell'albero , vale a dire sforzo esponenziale, se implementato in modo ingenuo. (Questo è uno dei motivi per cui i numeri di Fibonacci sono in realtà un pessimo esempio per insegnare la ricorsione: quasi tutte le implementazioni demo che trovi in tutorial o libri sono inutilizzabili per grandi valori di input.)

Se traccia il flusso di esecuzione, vedrai che nel secondo caso, il valore per fib x sarà sempre disponibile quando viene eseguito fib x+1 , e il sistema di runtime sarà in grado di leggerlo semplicemente dalla memoria piuttosto che tramite un'altra chiamata ricorsiva, mentre la prima soluzione tenta di calcolare la soluzione più grande prima che i risultati siano disponibili per valori più piccoli. Questo è in definitiva perché l'iteratore [0..n] viene valutato da sinistra a destra e quindi inizierà con 0 , mentre la ricorsione nel primo esempio inizia con n e solo dopo chiede circa n-1 . Questo è ciò che porta a molte, molte chiamate di funzioni duplicate non necessarie.