On 5/26/07, Mark Engelberg <[EMAIL PROTECTED]> 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?
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
