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.

  • \$\begingroup\$ Updated to include the missing function and problem statement. thanks for asking \$\endgroup\$ – Kevin Meredith Oct 15 '14 at 13:35
  • 1
    \$\begingroup\$ I strongly recommend doing Exercise 6 from the homework, Yorgey isn't lying when he says it's very cool. \$\endgroup\$ – mjolka Oct 16 '14 at 3:28
  • \$\begingroup\$ After I got help on multiplying and dividing streams, I just got the answer. I haven't yet digested the solution, but it's very sweet! \$\endgroup\$ – Kevin Meredith Oct 29 '14 at 0:12
  • 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.

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))

  • \$\begingroup\$ Thank you! I glimpsed at your solution, and then realized (as you point out) that interleave (streamRepeat 0) ... (if written ad infinitum) would solve this problem. I tried ruler without foldr, but I ran into a StackOverflow - gist.github.com/kevinmeredith/506aad8a13fca5a7e190. Could you please take a look at my ruler there? I don't want to look at your spoiler just yet! \$\endgroup\$ – Kevin Meredith Oct 21 '14 at 2:34
  • \$\begingroup\$ @KevinMeredith I should have split the spoiler in two parts (you'll see why later). Think about why your definition of interleave won't play nicely with ruler'. You'll need a different definition of interleave. \$\endgroup\$ – mjolka Oct 21 '14 at 2:38
  • \$\begingroup\$ ahh. so your advice to me is to implement interleave with foldr? \$\endgroup\$ – Kevin Meredith Oct 21 '14 at 2:47
  • \$\begingroup\$ @KevinMeredith no, try expanding out ruler' 0: ruler' 0 = interleave (streamRepeat 0) (ruler' 1) = interleave (streamRepeat 0) (interleave (streamRepeat 1) (...)). How will the outer interleave be evaluated? Sorry if that's not clear... I got stumped by this for a while too. \$\endgroup\$ – mjolka Oct 21 '14 at 2:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.