[Haskell-cafe] [newbie question] Memoization automatic in Haskell?
lrpalmer at gmail.com
Sat Jan 12 19:00:04 EST 2008
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.
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
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
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
class Memo a where
memo :: (a -> b) -> (a -> b)
For a bunch of different types.
Hmm, one probably already exists, actually...
More information about the Haskell-Cafe