Haskell and memoization of pure function results [

问题:

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)?

回答1:

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.