Re[Haskell-cafe] duction Sequence of simple Fibonacci sequence implementation

Luke Palmer lrpalmer at
Fri Aug 28 06:28:02 EDT 2009

On Fri, Aug 28, 2009 at 3:54 AM, staafmeister<g.c.stavenga at> wrote:
> Thanks for the memo trick! Now I understand that the haskell compiler
> cannot memoize functions of integers, because it could change the space
> behaviour. However I think it could memoize everything else. Because all
> types that are data objects sitting in memory (so the arg is essentially a
> reference)
> can be memoized, without changing the space properties (except for overall
> constants). Does haskell do this? And if it doesn't can you turn it on?

Integers are nothing special.  Consider functions on:

data Nat = Zero | Succ Nat

Now, perhaps you mean memoize specific Nat *references* (a meaningless
question for Haskell, only for specific implementations) rather than
the *values*.  Eg., for some f:
would not.

let x = Succ Zero in f x + f x

would memoize the result of f, but:

f (Succ Zero) + f (Succ Zero)

would not.

GHC does not do this.

However, I am working in my free time on an experimental graph reducer
which does.  It implements a semantics called "complete laziness"[1].
I'm experimenting to see how that changes the engineering trade-offs
(I have a blog post about what I expect those to be:

For programs that do not benefit from the extra sharing, I should be
lucky to run them only 50 times slower.  This is an indication why GHC
doesn't do this.

Complete laziness is a fairly young research field.  Maybe someday
we'll get a smokin' fast completely lazy reducer.


More information about the Haskell-Cafe mailing list