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.