On Fri, Aug 28, 2009 at 3:54 AM, staafmeister<g.c.stave...@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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe