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),(yx))
 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
xy and pair construction and matching will be done up to twice as
many times as in the other version.
Regards,
Tom