In che modo Haskell decide quale valore memoizzato verrà scartato?

Credo che tu stia caratterizzando in modo errato Haskell. potrebbe memoizzare automaticamente i risultati delle funzioni, ma non credo che faccia , proprio a causa del problema che stai descrivendo. Ho visto un'intervista di Simon Peyton Jones qualche tempo fa in cui ha discusso di questo, a cui collegherò se riesco a trovarlo di nuovo, ma il problema fondamentale è il valore corretto da mantenere varia in base all'algoritmo, quindi è molto difficile da eseguire automaticamente il runtime.

Per illustrare la mia osservazione e rispondere alla domanda di user102008 , ecco un piccolo esempio.

slowFunction :: Integer -> Integer
slowFunction n = if n == 0
                   then 0
                  else
                    let
                      n' = n - 1
                    in
                      1 + slowFunction n' + slowFunction n'

fastFunction :: Integer -> Integer
fastFunction n = if n == 0
                   then 0
                   else
                     let
                       r = fastFunction (n - 1)
                     in
                       1 + r + r

main :: IO ()
main = do
         putStrLn "Computing fast"
         putStrLn $ show $ fastFunction 25
         putStrLn "Computing slow"
         putStrLn $ show $ slowFunction 25
         putStrLn "Done"

In slowFunction , l'espressione 1 + slowFunction n' + slowFunction n' contiene la sottoespressione slowFunction n' due volte. Entrambe le sottoespressioni devono essere valutate (forzate) al fine di produrre il risultato finale. Sarebbe possibile memoizzare il risultato della prima sottoespressione e usarlo come risultato della seconda occorrenza, ma il runtime di Haskell non lo farà. In fastFunction , la sottoespressione comune è associata a una variabile e quindi valutata solo una volta.

Se si esegue questo programma è possibile osservare tempi di esecuzione molto diversi per le due funzioni (la prima è esponenziale, la seconda lineare nel parametro n ). Se Haskell memorizza automaticamente le sottoespressioni nella prima funzione, le due funzioni avranno tempi di esecuzione simili.