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

[Bulat Ziganshin]

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 at gmail.com