producing and consuming lists
Wed, 6 Nov 2002 01:01:16 +0000
> I think you have a choice between risking a space leak and repeating
Well, sometimes neither is a good option...
> If you use 'streams' like this
> let (xs, ys) =3D streams ...
> in -- anything which requires the first element of xs while ys may
> -- still be used in future (or vice versa)
> and p (or q, respectively) rejects the first trillion numbers it sees,
> you create a huge trail of 'if' thunks, which can't be garbage
> collected because you're still holding ys (or xs, respectively).
Even repeatedly processing one element of xs and one of ys, can still cau=
memory leaks - it happens evaluation of an elements of one of the lists=20
causes evaluation of lots of elements of the other.
One way out in my example, is=20
- *always* adding elements to both lists in each recursive call.
- processing lists alternating between them like I just said.
streams :: (Int->Bool, Int->Bool)->(Int,Int)->([Maybe Int],[Maybe Int])
streams (p,q) (x,y) =3D (xs',ys')
(xs,ys) =3D streams (p,q) ((x+y),(y-x))
xs' =3D if p x then (Just x:xs) else (Nothing:xs)
ys' =3D if q y then (Just y:xs) else (Nothing:ys)
(I could, of course, return a list of pairs in this case)
This might not be feaseble in more general cases though.
> If you do the following
> let xs =3D fst (streams ...)
> ys =3D snd (streams ...)
> in ...
> and somehow suppress Common Subexpression Elimination, I think the
> garbage collector will remove the trails of thunks, but the x+y and
> x-y and pair construction and matching will be done up to twice as
> many times as in the other version.
Like I said, sometimes that is not really an option...
In my example, it doesn't really matter in which order the lists are cons=
I was hoping you could take advantage of that in some way...