Beginner's question: Memo functions in Haskell

[Koen Claessen]

 | Actually, I was also expecting "fast n = memo slow n"
 | to work ?

In most lazy implementations, the idea is that sharing only
occurs between computations with the same name. A
computation declaration always has the form:

  x = ...

So, if you want sharing to occur between different uses of a
function f, you have to define f as follows (even if it is a
function):

  f = ...

If you however declare f as follows:

  f x = (...) x

This means (in most implementations) that the expression
(...) will be evaluated every time the function f is called
with an argument.

To understand memo better, we can make a special version of
memo that only works on booleans:

  memo :: (Bool -> b) -> (Bool -> b)
  memo f =
    let fTrue  = f True
        fFalse = f False
     in \x -> if x then fTrue else fFalse

We can see now that the computations "fTrue" and "fFalse"
are shared between calls to "memo f".

So when we define:

  expensive b = <some very expensive thing>

  f = memo expensive

  f' b = memo expensive b

We can see that "memo expensive" is reused between different
calls of "f", and therefore are "expensive True" and
"expensive False" remembered. We can also see that "memo
expensive" is recomputed between calls of "f'", so the
introduction of the memo function has no effect.

/Koen.

--
Koen Claessen
http://www.cs.chalmers.se/~koen
Chalmers University, Gothenburg, Sweden.