Re[Haskell-cafe] [2]: Reduction Sequence of simple Fibonacci sequence implementation

staafmeister g.c.stavenga at
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
lookup tables.
So although there is space overhead it is not excessive.

View this message in context:
Sent from the Haskell - Haskell-Cafe mailing list archive at

More information about the Haskell-Cafe mailing list