[Haskell-cafe] Memoization

[Stefan O'Rear]

On Sat, May 26, 2007 at 11:41:28PM -0300, Felipe Almeida Lessa wrote:
> On 5/26/07, Mark Engelberg <mark.engelberg at gmail.com> 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