[Haskell-cafe] [newbie question] Memoization automatic in Haskell?

[Luke Palmer]

On Jan 12, 2008 11:30 PM, David Benbennick <dbenbenn at gmail.com> wrote:
> On 1/12/08, Henning Thielemann <lemming at henning-thielemann.de> wrote:
> >  Caching is not the default, but you can easily code this by yourself:
> > Define an array and initialize it with all function values. Because of
> > lazy evaluation the function values are computed only when they are
> > requested and then they persist in the array.
>
> But how can I implement memoization for a more complicated function?
> For example, perhaps I want to memoize
>
> f :: String -> Int -> Double -> String -> Bool
>
> In Python, it's pretty easy to memoize this.  How can I do it in
> Haskell?  I suspect the only way would involve changing the function
> signature to use IO or ST.

No, that is one way to do it, and probably the easiest to think about.
 Because its
conceptually pure, I wouldn't be opposed to wrapping it in unsafePerformIO (but
that can be, well, unsafe if you do it wrong :-)

But there is a way to do it if you demand to be a purist, but only if you can
code a data structure representing all values of a type.  Doing this for a
particular type is one of my favorite ways to spend a half hour when
I'm bored :-)

For an obvious case, but to illustrate the point, I'll do Bool.

  data BoolCache a = BC a a

  bools :: BoolCache Bool
  bools = BC True False

  lookupBool :: BoolCache a -> Bool -> a
  lookupBool (BC t f) True  = t
  lookupBool (BC t f) False = f

  memoBool :: (Bool -> a) -> (Bool -> a)
  memoBool f = lookupBool (fmap f bools)

The pattern is the same for any type.  You can do it for types with infinitely
many members, like Integer, but it's trickier (but it's the same pattern, just
a trickier data structure).  The Integer case is scattered here and
there online.
I haven't found any other cases online, but I've implemented a few.

> It would be nice if I could just tell the compiler "I command you to
> memoize this function", and have it produce the required code
> automatically.

Tru dat!

But it's not clear what the best way for the compiler writer to do
that is.  For
example, if I know the access patterns of the function, I can design the
aforementioned data structure to favor those.   Also, not every type admits
memoization, for example functions.  But I can certainly envisage a
library providing:

  class Memo a where
    memo :: (a -> b) -> (a -> b)

For a bunch of different types.

Hmm, one probably already exists, actually...

Luke