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?

  • Not a Haskell expert by any means but I didn't think it necessarily computes a function until a value is needed (Lazy evaluation). Until that time I didn't think it memoized function values but instead memoized thunks to possibly be processed, maybe.
    – maple_shaft
    Dec 15, 2016 at 14:39

2 Answers 2


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.

  • Doesn't it memoize thunks though? Just in case the value of a function is required?
    – maple_shaft
    Dec 15, 2016 at 14:40
  • I have read it on the inet, but as so often the inet failed.
    – ceving
    Dec 15, 2016 at 14:51
  • It doesn't memoize @maple_shaft, but because execution is delayed, it can sometimes order it to avoid executing a subexpression multiple times. See this answer for more information. Dec 15, 2016 at 16:44
  • I once verified that even the same expression occurring twice in the same function is evaluated twice. In order to have an expression evaluated only once, you have to bind it to a variable (let x = ...) and then use the variable x multiple times.
    – Giorgio
    Dec 15, 2016 at 22:47
  • @Giorgio, this isn't the same expression written twice, but potentially evaluated multiple times. For example, filter (\x -> (expensivefunction y) + x) list. Dec 16, 2016 at 0:26

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
                      n' = n - 1
                      1 + slowFunction n' + slowFunction n'

fastFunction :: Integer -> Integer
fastFunction n = if n == 0
                   then 0
                       r = fastFunction (n - 1)
                       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, 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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.