6

I have the following code:

memoize f = (map f [0 ..] !!)

fib' 0 = 1
fib' 1 = 1
fib' n = fib' (n - 1) + fib' (n - 2)

fibMemo n = memoize fib' n
fibMemo'  = memoize fib'

(I am aware of that fibonacci implementation has exponential time complexity and does not use the cache)

The first time I execute fibmemo' 30 it takes 3 seconds, and the second time it takes ~0 seconds, because the result is cached. But the first version, fibmemo, does not get the result cached, it always takes 3 seconds to execute. The only difference is the definition (which as far as I know are equivalent).

So my question is, what functions are cached in Haskell?

I have already read https://wiki.haskell.org/Memoization and does not resolve my question.

ManuelVS
  • 125
  • 6
  • 7
    The short version is that [Constant Applicative Forms](https://wiki.haskell.org/Constant_applicative_form) (CAFs) are memoised. (Leaving this as a comment since it’s not a complete answer.) – Jon Purdy Oct 28 '18 at 10:40
  • if it takes 3 seconds for 30, it's not memoized at all. i.e. you do build a cache of results, but the function itself does not use that cache. for an example of memoized Fibonacci, see e.g. [this](https://stackoverflow.com/questions/11466284/how-is-this-fibonacci-function-memoized). – Will Ness Oct 28 '18 at 11:02

1 Answers1

4

Essentially, the functions you defined behave as the following ones:

fibMemo n = let m = map fib' [0..] in m !! n
fibMemo'  = let m = map fib' [0..] in (m !!)

Why is fibMmemo' more efficient? Well, we can rewrite it as

fibMemo'  = let m = map fib' [0..] in \n -> m !! n

which makes it more clear that the single list m gets created before n is taken as input. This means that all the calls to fibMemo' will use the same m. The first call evaluates a part of m slowly, and the successive calls will reuse that cached result (assuming the call hits the cache, of course, otherwise another part of m is evaluated and cached).

Instead, fibMemo is equivalent to

fibMemo = \n -> let m = map fib' [0..] in m !! n

which takes the input n before the list m gets created. So, each call gets a new cache, which is pointless, since the whole purpose of a cache is that it is reused later.

The order of the lambda \n -> vs the let m = .. matters a lot in terms of the performance. Since m = .. does not use n, technically the let m = .. can be floated outwards, essentially turning fibMemo into fibMemo', without affecting the semantics. However, as you discovered, this does not preserve performance, in general!

This is indeed an optimization that GHC could perform, but does not, because it can easily make the performance significantly worse.

chi
  • 111,837
  • 3
  • 133
  • 218