[Haskell-beginners] Data.Stream interleave implementation question

[Isaac Dupree]

On 02/11/2014 11:23 PM, Bryan Brady wrote:
> [...]
> interleaveStreams :: Stream a -> Stream a -> Stream a
> interleaveStreams (Cons a as) (Cons b bs) = Cons a (Cons b
> (interleaveStreams as bs))
>
> ruler :: Stream Integer
> ruler = foldr1 interleaveStreams (map streamRepeat [0..])
> [...]
> In the latter definition, Cons a (interleaveStreams bs as),
> (interleaveStreams bs as) is a thunk. The thunk should only be evaluated
> when it is needed.  In my original definition, (interleaveStreams as bs)
> is a thunk. The difference is an extra Cons (e.g., Cons b).  It seems
> like the additional Cons is causing problems, I just don't understand
> why. Can anyone point out what I'm missing?

The issue is on the left-hand-side of interleaveStreams.  It is strict 
in both its arguments.  Look at foldr1; you're evaluating

interleaveStreams (streamRepeat 0)
   (interleaveStreams (streamRepeat 1)
     (interleaveStreams (streamRepeat 2)
       (interleaveStreams (streamRepeat 3)
         ...

In this situation, if interleaveStreams evaluates its second argument 
before returning any work, it will never be able to return.  Happily, 
the outer Cons of the result does not depend on the second argument.  I 
can fix the issue just by making the second argument be pattern-matched 
lazily (with ~, i.e. only as soon as any uses of the argument in the 
function are evaluated):

interleaveStreams (Cons a as) ~(Cons b bs) = Cons a (Cons b 
(interleaveStreams as bs))

You can also write this without ~ by explicitly pattern matching later, e.g.

interleaveStreams (Cons a as) bs = Cons a (case bs of Cons b bs' -> Cons 
b (interleaveStreams as bs'))


I'm not sure whether there's a practical difference between these and 
Data.Stream's definition.  Actually, I think they turn out to do exactly 
the same thing...


(I tested by deriving Show for Stream, and typing 'ruler' in `ghci 
file.hs`, or 'take 80 (show ruler)'.)

-Isaac