Hello staafmeister, Friday, August 28, 2009, 1:54:38 PM, you wrote: it just works other way. imagine a whole haskell program as a graph. i.e. expression 1+2, for example, forms a node with (=) in its root and 1 and 2 as its subtrees. computation of program is a series of graph reductions, replacing nodes with results, f.e. 1+2 => 3 this graph can share computations in only one way - when you give sharec node a name and use this name twice. for example, the following sum[1..1000] + prod[1..1000] don't share anything, but this let list = [1..1000] in sum list + prod list share the list. performing sharing via explicit naming common subexpressions is the only way to memoize results you imagine something highly inefficient like storing results of every computation ever done. are you think it really makes a sense? sometimes haskell compilers may deduce that some computation is used twice. if result of this computation definitely require less memory than computation itself, compiler may perform optimization by storing its result. it's called Common Subexpression Elimination. but its' not guaranteed, and afaik is pretty limited in ghc
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?
Cheers, Gerben
-- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com