[Haskell-cafe] Memoization

[Creighton Hogg]

On 5/26/07, Mark Engelberg <mark.engelberg at gmail.com> wrote:
>
> I'd like to write a memoization utility.  Ideally, it would look
> something like this:
>
> memoize :: (a->b) -> (a->b)
>
> memoize f gives you back a function that maintains a cache of
> previously computed values, so that subsequent calls with the same
> input will be faster.
>
> I've searched the web for memoization examples in Haskell, and all the
> examples use the trick of storing cached values in a lazy list.  This
> only works for certain types of functions, and I'm looking for a more
> general solution.
>
> In other languages, one would maintain the cache in some sort of
> mutable map.  Even better, in many languages you can "rebind" the name
> of the function to the memoized version, so recursive functions can be
> memoized without altering the body of the function.
>
> I don't see any elegant way to do this in Haskell, and I'm doubting
> its possible.  Can someone prove me wrong?


Now maybe I'm being dense here, but would you really *want* a way in Haskell
to do something like
memo :: (a->b) -> a->b
since it changes the semantics of the function?
It seems like a better abstraction would be to have
memo :: (a->b)-> M a b
where M is an instance of Arrow so that you can keep a proper notion of
composition between memoized functions.
Is there something wrong with my thinking?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20070530/50fa3555/attachment.htm