Haskell not lazy evaluating interleaving

Question

I am working through a problem (its from a UPenn class, but I am not taking it (just working through it to learn Haskell)), and the point is to construct a Stream (as defined below), that is defined by "ruler" (ruler !! n = the exponent of the highest power of 2 which will divide n). The issue is that I think that the definition for ruler below should lazily evaluate, but it seems to be evaluating strictly and running infinitely. If I cap it by adding a terminal case like "nthStream 10 = streamRepeat 10" it runs and generates output up to the point I want correctly.

data Stream a = Stream a (Stream a)

streamToList :: Stream a -> [a]
streamToList (Stream a rest) = [a] ++ streamToList rest

instance Show a => Show (Stream a) where
    show s = show $ take 100 $ streamToList s

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

interleaveStreams :: Stream a -> Stream a -> Stream a
interleaveStreams (Stream a arest) (Stream b brest) = (Stream a (Stream b (interleaveStreams arest brest)))

nthStream :: Integer -> Stream Integer

nthStream n = interleaveStreams (streamRepeat n) (nthStream (n+1))

ruler :: Stream Integer
ruler = nthStream 0 

Can anyone explain why ruler (and nthStream) is not lazily evaluating?

Answer 1

I'll try to nudge you in the right direction, or at least point out what's going wrong. The function nthStream will never evaluate, not even its first element, because of how it's defined with interleaveStreams. To give you an example, let's work out what it evaluates to for nthStream 0 (for brevity and readability I've renamed nthStream to nth, interleaveStream to interleave, streamRepeat to repeat, and Stream to Strm):

nth 0 = interleave (repeat 0) (nth 1)
      = interleave (Strm 0 _0) (interleave (repeat 1) (nth 2))
      = interleave (Strm 0 _0) (interleave (Strm 1 _1) (nth 2))
      = interleave (Strm 0 _0) (interleave (Strm 1 _1) (interleave (repeat 2) (nth 3)))
      = interleave (Strm 0 _0) (interleave (Strm 1 _1) (interleave (Strm 2 _2) (nth 3)))

I've chosen to represent the tails of each stream returned from repeat as _N where N is the number being repeated. These are currently thunks, since we haven't had to request their values yet. Notice how what is building up is a chain of interleaves, rather than a chain of Strm constructors. We get each one we're interested in, but they can never return from interleave until the second argument is evaluated. Since the second argument is always getting reduced to a new call to interleave, it'll never reduce.

Here's a hint: how can you define interleaveStreams recursively so that it only depends on its first argument being constructed already? i.e.

interleaveStreams (Stream a arest) streamB = Stream a (???)