Implementing Function that Maps over Stream

Question

I implemented the following function:

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'm giving it a vague name in the event that students try to cheat and search for it.

foo :: Stream Integer
foo = streamMap f startAtOne
    where f x        = if (odd x) then 0 else g x 0
          g y acc    = if y == 0 then acc else g (y-2) (acc+1)
          startAtOne = streamFromSeed 1 (+1)

Here's the streamFromSeed function and the Stream data type.

data Stream a = Stream (a, Stream a)

streamMap :: (a -> b) -> Stream a -> Stream b
streamMap f (Stream (x, rest)) = Stream (f x, streamMap f rest)

-- Given a start value and function, generate a stream by applying fn to each Stream value
streamFromSeed :: a -> (a -> a) -> Stream a
streamFromSeed x f = Stream $ (x, streamFromSeed (f x) f)

Note that this technically is homework, but from 2013. I'm working on this material since Prof. Yorgey provides excellent lectures and homework assignments. I'm not in this class nor a student at the school.

Answer 1

• Since streamMap allows you to map over a stream, you can as well define a Functor instance for Stream. Actually, streams can also define an Applicative instance which zips two streams and also a Monad instance whose join computes the diagonal of a 2-dimensional stream.
• Your definition of Stream is slightly inefficient as it wraps the (,) constructor in another constructor Stream. You could:
  • make it a newtype, or
  • use the UNPACK pragma, or
  • define just a 2-argument constructor like data Stream a = Cons a (Stream a).
• Your solution deviates from the assignment that forbids any kind of divisibility testing. Function odd tests for divisibility by 2 and g implements (somewhat inefficiently) division by 2.
• Without the full code it's a bit hard to test/judge correctness, but I believe your implementation is not correct. In particular, I believe for n=6 your code will yield 3, while the expected value is 1.

Answer 2

I think you missed a very important hint in the homework:

Hint: define a function interleaveStreams which alternates the elements from two streams. Can you use this function to implement ruler in a clever way that does not have to do any divisibility testing?

Let's look at the first few terms:

0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, . . .

Every other term is 0, so let's ignore those for the moment. That leaves us with

1, 2, 1, 3, 1, 2, 1, 4, . . .

Every other term is 1, so let's ignore those for the moment...

2, 3, 2, 4, ...

Every other term is 2, ... etc etc.

That gives us a strong hint that our function will look like this:

interleave (streamRepeat 0) (interleave (streamRepeat 1) (interleave (streamRepeat 2) ...))

Which should look familiar to you by now -- we can write this in terms of foldr!

As Petr pointed out, we can just define Stream as

data Stream a = Stream a (Stream a)

I'll put the rest of the solution behind a spoiler tag.

 streamRepeat :: a -> Stream a
 streamRepeat x = let s = Stream x s in s
 
 interleaveStreams :: Stream a -> Stream a -> Stream a
 interleaveStreams (Stream x xs) ys = Stream x (interleaveStreams ys xs)
 
 ruler :: Stream Integer
 ruler = foldr1 interleaveStreams (map streamRepeat [0..])

Bonus question: why won't this definition work for our solution?

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