[prev in list] [next in list] [prev in thread] [next in thread] 

List:       haskell-cafe
Subject:    Re: [Haskell-cafe] Space leak whilst implementing streams
From:       Udo Stenzel <u.stenzel () web ! de>
Date:       2006-08-26 14:51:44
Message-ID: 20060826145144.GB7006 () web ! de
[Download RAW message or body]


ephemeral.elusive@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.

["signature.asc" (application/pgp-signature)]

[prev in list] [next in list] [prev in thread] [next in thread]