CODEWITHSUNDEEP
haskellstreamlazy-evaluation
Rahn
Rahn

Reputation: 5405

Fail to define an infinite stream

I'm working on UPENN Haskell Homework 6 Exercise 5, trying to define a 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 just came up with an idea to build it without any divisibility testing:

data Stream x = Cons x (Stream x) deriving (Eq)

streamRepeat x = Cons x (streamRepeat x)

interleaveStreams (Cons x xs) (Cons y ys) =
    Cons x (Cons y (interleaveStreams xs ys))

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

where first 20 element of

ruler =
    interleaveStreams (streamRepeat 0)
        (interleaveStreams (streamRepeat 1)
            (interleaveStreams (streamRepeat 2)
                (interleaveStreams (streamRepeat 3) (streamRepeat 4))))

is

[0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2]

Obviously I couldn't define it manually to infinite so I defined a infInterStream to help such infinite recursion definition:

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

ruler = infInterStream 0

But now I get stuck when typing in ruler in ghci, it probably falls into infinite loop.

It shouldn't be if lazy evaluation works. I want to know why lazy evaluation fails here.

Helper function to observe Stream:

streamToList (Cons x xs) = x : streamToList xs

instance Show a => Show (Stream a) where
    show = show . take 20 . streamToList

Upvotes: 3

Views: 319

Answers (2)

Mike Spivey
Mike Spivey

Reputation: 660

There's no need for a new type for streams, and we can just use Haskell's lazy lists instead. As others have noted, the definition of interleave must be sufficiently lazy that it can produce the first element of the output before testing whether the second argument is non-empty. This definition will do:

interleave (x:xs) ys = x : interleave ys xs

If you want interleave to work also for finite lists, you can add the equation

interleave [] ys = ys

Note also that, using functions from the standard prelude,

ruler = interleave (repeat 0) (map (+1) ruler)

Here repeat 0 is the list [0, 0, 0, ...].

Upvotes: 1

András Kovács
András Kovács

Reputation: 30103

Your interleaving function is too strict. The following works:

interleaveStreams (Cons x xs) ys = Cons x (interleaveStreams ys xs)

This also works:

interleaveStreams (Cons x xs) ~(Cons y ys) = 
    Cons x (Cons y (interleaveStreams xs ys))

The original definition goes into infinite loop because interleaveStreams demands that both arguments must be of Cons forms. infInterStream n evaluates to the the interleaving of two streams, and the first one can be immediately evaluated to Cons, but the second one must also be reduced first to Cons, so we recursively call infInterStream (n + 1), which keeps calling itself ad infinitum.

If interleaveStreams can return a Cons a _ without first having to force the second argument, infInterStream can also incrementally build the result.

Upvotes: 7

Related Questions