C'è un modo per "preservare" i risultati in Haskell?

Question

Sono nuovo di Haskell e capisco che è (fondamentalmente) un linguaggio puramente funzionale, che ha il vantaggio che risulta che le funzioni non cambieranno in più valutazioni. Detto questo, sono perplesso dal fatto che non possa facilmente contrassegnare una funzione in modo tale che ricordi i risultati della sua prima valutazione e non debba essere nuovamente valutata ogni volta che è necessario il suo valore.

In Mathematica, per esempio, c'è una simple idiom per realizzare questo:

f[x_]:=f[x]= ... 

ma in Haskell, le cose più vicine che ho trovato è something like

f' = (map f [0 ..] !!) 
    where f 0 = ... 
     f n = f' ... 

, che oltre ad essere molto meno chiaro (e apparentemente limitato agli argomenti Int?) non (sembra) preservare i risultati all'interno di una sessione interattiva.

Ammettiamo (e chiaramente), non capisco esattamente cosa sta succedendo qui; ma ingenuamente, sembra che Haskel dovrebbe avere qualche modo, a livello di definizione della funzione, di

• approfittando del fatto che le sue funzioni sono funzioni e saltare ricalcolo dei risultati una volta che sono stati calcolati e
• indicando il desiderio di farlo a livello di definizione della funzione con un linguaggio semplice e pulito.

C'è un modo per farlo in Haskell che mi manca? Capisco (una specie di) che Haskell non può memorizzare le valutazioni come "stato", ma perché non può semplicemente (in effetti) ridefinire le funzioni valutate come il loro valore calcolato?

---

Questo nasce da this question, in cui la mancanza di questa caratteristica si traduce in prestazioni terribile.

Answer 1

Utilizzare una libreria appropriata, ad esempio MemoTrie.

import Data.MemoTrie 

f' = memo f 
where f 0 = ... 
     f n = f' ... 

Non è meno bello della versione Mathematica, vero?

---

Per quanto riguarda

“ funzioni perché non può semplicemente (in effetti) Ridefinire valutati per essere il loro valore calcolato? ”

Bene, non è così facile in generale. Questi valori devono essere memorizzati da qualche parte. Anche per una funzione valutata da Int, non è possibile allocare un array con tutti i possibili valori – che non si adatta alla memoria. La soluzione elenco funziona solo perché Haskell è pigro e quindi consente elenchi infiniti, ma ciò non è particolarmente soddisfacente poiché la ricerca è O (n). Per altri tipi è semplicemente senza speranza – che ti serve per diagonizzare in qualche modo un dominio infinitamente numerabile.

Avete bisogno di un'organizzazione più intelligente. Non so come faccia Mathematica, ma probabilmente usa un sacco di magia proprietaria “ ”. Non sarei così sicuro che funzioni davvero come vorresti, per qualsiasi input.

Haskell dispone fortunatamente di classi di tipi, che consentono di esprimere esattamente ciò di cui un tipo necessita per essere rapidamente memorizzabile. HasTrie è una classe del genere.