[Haskell-beginners] Data.Stream interleave implementation question

[Bryan Brady]

I'm in the process of learning Haskell and am implementing my own Stream
type. ( I'm working my way through homework problems I found at
http://www.seas.upenn.edu/~cis194/hw/06-laziness.pdf )

One of the questions is:
"Define the stream
ruler :: Stream Integer
which corresponds to the ruler function
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, . . .
where the nth element in the stream (assuming the first element
corresponds to n = 1) is the largest power of 2 which evenly
divides n. "

I got pretty close, but ended up looking at Data.Stream to nail down my
mistake. My original solution was:

-----
data Stream a = Cons a (Stream a) deriving (Eq, Ord)

streamRepeat :: a -> Stream a
streamRepeat a = Cons a (streamRepeat a)

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..])
-----

Attempting to evaluate 'ruler' in ghci does not finish. I knew something
was wrong with my implementation of interleaveStreams because it worked
when I expanded it out manually for a few steps. The way Data.Stream
implements interleave is:
interleaveStreams (Cons a as) bs = Cons a (interleaveStreams bs as)

I don't understand why this works and why my original implementation
doesn't. I figure if the latter works, the former should as well. Here is
my reasoning:

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?

thanks,

bb
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20140211/a73d7f48/attachment.html>