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

[Luke Palmer]

On Fri, Aug 28, 2009 at 3:54 AM, staafmeister<g.c.stavenga at uu.nl> 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:
http://lukepalmer.wordpress.com/2009/07/07/emphasizing-specialization/)

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.

[1] http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/sinot-wrs07.pdf