Re[Haskell-cafe] : Reduction Sequence of simple Fibonacci
g.c.stavenga at uu.nl
Fri Aug 28 06:34:07 EDT 2009
Bulat Ziganshin-2 wrote:
> 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?
Well in case I call (prod list) again it could lookup the reference and see
that this computation has already been performed and just lookup the answer.
In case `list' becomes GCed the GC should also destroy the lookup in the
The overhead is a O(1) overhead for the function because it needs to check
a computation has already performed. And the space overhead is not so big
every data object in memory there are a couple of references to be stored in
So although there is space overhead it is not excessive.
View this message in context: http://www.nabble.com/Reduction-Sequence-of-simple-Fibonacci-sequence-implementation-tp25178377p25187710.html
Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.
More information about the Haskell-Cafe