(re-joining the list -- I forgot to "reply all")
Vincent Kraeutler wrote:
Roberto Zunino wrote:
Vincent Kraeutler wrote:
i see that the definition of fix (from Control.Monad.Fix) could not be
any simpler:
fix f = let x = f x in x
I actually consider
fix f = f (fix f)
to be simpler. Alas, it breaks sharing...
;-)
sharing?
v.
The two functions
fix1 f = let x = f x in x
fix2 f = f (fix2 f)
have the same semantics. However I believe many implementations run them
with different performance.
Consider
y = fix1 (2:)
This would be expanded to
y = let x = 2:x in x
A typical implementation would then represent the infinite list using
(roughly) a circular pointer-list, i.e. x = cons(2, pointer-to-x) .
So, the tail of the list is shared with the list itself, causing a
constant space to be allocated for the list, even if a large portion of
the list is demanded as in (take 1000000 y).
On the contrary,
y = fix2 (2:)
would be
y = 2 : fix2 (2:)
and, unless some optimization magic kicks in, the representation for y
is not a circular list. Each time a new list element is demanded, a new
cons cell will be allocated. Running (take 1000 y) would then "waste"
space for 1000 copies of 2. This is because the tail is not shared.
Zun.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
