# producing and consuming lists

Tom Pledger Tom.Pledger@peace.com
Wed, 6 Nov 2002 12:09:51 +1300

```Jorge Adriano writes:
:
| streams :: (Int->Bool, Int->Bool)->(Int, Int)->([Int],[Int])
| streams (p,q) (x,y) = (xs',ys')
|     where
|     (xs,ys) = streams (p,q) ((x+y),(y-x))
|     xs' = if p x then x:xs else xs
|     ys' = if q y then y:xs else ys
|
|
| - produces a pair of ('infinite') lists
| - produced lists are not indepentent (you need to calculate elements of one
| list to calculate elements of the other)
| - in each recursive call an element is added to the 1st/2nd list iff  it
| satisfies a given (Int->Bool) function p/q
|
| How should one consume (part of) both lists, avoiding space leaks?

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

If you use 'streams' like this

let (xs, ys) = 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).

If you do the following

let xs = fst (streams ...)
ys = 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.

Regards,
Tom

```