2

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 '16 at 14:39
3

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 '16 at 14:40
  • I have read it on the inet, but as so often the inet failed. – ceving Dec 15 '16 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. – Karl Bielefeldt Dec 15 '16 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 '16 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. – Karl Bielefeldt Dec 16 '16 at 0:26
2

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"

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.