[Haskell-cafe] Cute code [was: The C Equiv of != in Haskell miscommunication thread]

[Roberto Zunino]

(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.