On Fri, Aug 28, 2009 at 3:54 AM, staafmeister
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