producing and consuming lists

[Tom Pledger]

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