producing and consuming lists
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')
| (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
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 ...)
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.