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:

"Deﬁne 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 ﬁrst 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,