[Haskell-cafe] Space leak whilst implementing streams

[Udo Stenzel]

ephemeral.elusive at gmail.com wrote:
> I found a way to remove this space leak, however, I do not really
> understand why there was a space leak in the first place. I would
> really appreciate any light that could be shed on this.
 
> instance ArrowChoice SF where
>  left (SF f)
>      = SF (\xs -> combine xs (f [y | Left y <- xs]))
>        where combine (Left _:xs)  (z:zs) = Left z :combine xs zs
>              combine (Right r:xs) zs     = Right r:combine xs zs
>              combine []           _      = []

The list comprehension is holding onto 'xs' until something of the 'zs'
is consumed.  That only happens when 'xs' contains 'Left _', and your
input input stream doesn't.  So the whole stream is leaked, which indeed
produces a linear space profile.  The easiest way to correct it, is to
consume the list 'xs' only once:

    instance ArrowChoice SF where
     left (SF f) = SF (map f')
	   where f' (Left x) = Left (f x)
		 f' (Right y) = Right y

or simply

    instance ArrowChoice SF where
     left (SF f) = SF (map (left f))


> instance ArrowChoice SF' where
>  left (SF' f)
>      = SF' (\xs -> xs `combined` f (map drop_right xs))
>        where combined = zipWith merge_left

Here you're also risking the leak of a whole copy of 'xs', but since you
end up consuming both lists at the same pace, nothing bad happens.


Udo.
-- 
Nicht alles was hinkt ist ein Vergleich.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org//pipermail/haskell-cafe/attachments/20060826/8fa7730b/attachment.bin