haskellstreaminfiniteself-referenceinterleave

Implementing the ruler function using `streamInterleave`

I am doing the homework of CIS 194. The problem is to implement the ruler function by using streamInterleave. The code looks like

data Stream a = Cons a (Stream a)

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

streamMap :: (a -> b) -> Stream a -> Stream b
streamMap f (Cons x xs) = Cons (f x) (streamMap f xs)

streamInterleave :: Stream a -> Stream a -> Stream a
streamInterleave (Cons x xs) ys = Cons x (streamInterleave ys xs)

ruler :: Stream Integer
ruler = streamInterleave (streamRepeat 0) (streamMap (+1) ruler)

I am really confused why ruler can be implemented like this. Is this going to give me [0,1,0,1....]?

Any help will be greatly appreciated. Thank you!!

Solution

  • Firstly, we'll represent a Stream like this:

    a1 a2 a3 a4 a5 ...

    Now, let's take the definition of ruler apart:

    ruler :: Stream Integer
ruler = streamInterleave (streamRepeat 0) (streamMap (+1) ruler)

    In Haskell, an important point is laziness; that is, stuff doesn't need to be evaluated until it needs to be. This is important here: it's what makes this infinitely recursive definition work. So how do we understand this? We'll start with the streamRepeat 0 bit:

    0 0 0 0 0 0 0 0 0 ...

    Then this is fed into a streamInterleave, which interleave this the with (as yet unknown) stream from streamMap (+1) ruler (represented with xs):

    0 x 0 x 0 x 0 x 0 x 0 x ...

    Now we'll start filling in those xs. We know already that every second element of ruler is 0, so every second element of streamMap (+1) ruler must be 1:

      1   x   1   x   1   x   1   x   1   x ... <--- the elements of (streamMap (+1) ruler)
0 1 0 x 0 1 0 x 0 1 0 x 0 1 0 x 0 1 0 x ... <--- the elements of ruler

    Now we know every second element out of each group of four (so numbers 2,6,10,14,18,...) is 1, so the corresponding elements of streamMap (+1) ruler must be 2:

      1   2   1   x   1   2   1   x   1   2 ... <--- the elements of (streamMap (+1) ruler)
0 1 0 2 0 1 0 x 0 1 0 2 0 1 0 x 0 1 0 2 ... <--- the elements of ruler

    Now we know that every fourth element out of each group of eight (so numbers 4,12,20,...) is 2 so the corresponding elements of streamMap (+1) ruler must be 3:

      1   2   1   3   1   2   1   x   1   2 ... <--- the elements of (streamMap (+1) ruler)
0 1 0 2 0 1 0 3 0 1 0 2 0 1 0 x 0 1 0 2 ... <--- the elements of ruler

    And we can continue building ruler like this ad infinitum, by substituting back each n/2, 3n/2, 5n/2, ... numbered value of ruler.