Re[Haskell-cafe] duction Sequence of simple Fibonacci sequence
lrpalmer at gmail.com
Fri Aug 28 06:28:02 EDT 2009
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
> 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:
let x = Succ Zero in f x + f x
would memoize the result of f, but:
f (Succ Zero) + f (Succ Zero)
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".
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