Haskell keeps the computed values of functions. This can be done only up the the storage limit. When the storage limit is reached, how does Haskell decide which computations to keep and which to discard?
I believe you are characterizing Haskell incorrectly. It could automatically memoize function results, but I don't think it does, precisely because of the problem you're describing. I watched an interview of Simon Peyton Jones a while back where he discussed this, which I will link to if I can find it again, but the basic issue is the correct value to keep varies by algorithm, so it's very difficult to do automatically by the runtime.
In order to illustrate my observation and answer
user102008's question, here is a small example.
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"
slowFunction, the expression
1 + slowFunction n' + slowFunction n' contains the subexpression
slowFunction n' twice. Both subexpressions must be evaluated (forced) in order to produce the final result. It would be possible to memoize the result of the first subexpression and use it as the result of the second occurrence, but Haskell runtime will not do this. In
fastFunction, the common subexpression is bound to a variable and therefore evaluated only once.
If you run this program you can observe very different running times for the two functions (the first is exponential, the second linear in the parameter
n). If Haskell automatically memoized the subexpressions in the first function, the two functions would have similar running times.