producing and consuming lists

Jorge Adriano
Wed, 6 Nov 2002 01:01:16 +0000

> I think you have a choice between risking a space leak and repeating
> evaluation.

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

Yeap, exactly
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...