7

Possible Duplicate:
When is memoization automatic in GHC Haskell?

As a consequence, pure function always returns the same value for a fixed input. That said, does Haskell (more precisely GHC) automatically cache (memoize) these results if there is enough memory (question 1) and does developer have any control on it (question 2)?

Community
  • 1
  • 1
Cartesius00
  • 23,584
  • 43
  • 124
  • 195
  • 1
    @LoganCapaldo Oh, yes, I see. But that post is about 2 years old, maybe there was some progress. – Cartesius00 Sep 12 '12 at 14:29
  • 3
    If you edit your question to a) acknowledge the other one and b) clarify what you mean by "progress" as compared to the answer to the original and or why or why not "progress" would occur there could be some valuable answers. I'm not prepared to get into it, but I think you'll find that automatic memoization of the kind you might be imagining is a bigger can of worms than might might appear at first blush. – Logan Capaldo Sep 12 '12 at 14:38

1 Answers1

11

I voted to close, but short answer:

GHC does not do any automatic memoization of functions, and that is probably a good thing because it would make space complexity even harder to reason about. Also, memoization is not in general a very solvable problem, since it requires the argument of the function be comparable for equality which is not really possible for all types (for example, functions).

Haskell has non-strict semantics. GHC provides a, more or less, call by need cost model. Although the overhead of lazy evaluation at high optimization levels is not that bad because of the strictness analyzer.

It is very easy to implement memoization in Haskell using lazy evaluation. Be careful about space usage though.

fib' :: (Integer -> Integer) -> Integer -> Integer
fib' f 0 = 0
fib' f 1 = 1
fib' f n | n > 1 = (f (n - 1)) + ((f (n - 2))

slow_fib :: Integer -> Integer
slow_fib = fib' slow_fib

fibs :: [Integer]
fibs = map (fib' memo_fib) [0..] 

memo_fib :: Integer -> Integer
memo_fib n = fibs !! n

This is actually not that fast, and is a space leak, but captures the general idea. You can learn more on the Haskell wiki.

dave4420
  • 46,404
  • 6
  • 118
  • 152
Philip JF
  • 28,199
  • 5
  • 70
  • 77