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

[staafmeister]

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
cache.
The overhead is a O(1) overhead for the function because it needs to check
if
a computation has already performed. And the space overhead is not so big
because
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: 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.