Re: [Haskell-cafe] Memoization

On Sat, May 26, 2007 at 11:41:28PM -0300, Felipe Almeida Lessa wrote:

On 5/26/07, Mark Engelberg wrote:

...

I don't see any elegant way to do this in Haskell, and I'm doubting its possible. Can someone prove me wrong?

Provided some sort of memoize :: (a->b) -> (a->b), I'd do something like

f = memoize g where g = .... recursive call to f, not g ...

But probably there's something better I've missed =).

memofix :: ((a -> b) -> (a -> b)) -> a -> b memofix ff = let g = memoize (ff g) in g fib = memofix $ \fib k -> case k of 0 -> 0 1 -> 1 n -> fib (n-1) + fib (n-2) Stefan