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-implem... Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.