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\$ Oct 15, 2014 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, 2014 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\$ Oct 29, 2014 at 0:12

2 Answers 2

  • 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\$ Oct 21, 2014 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, 2014 at 2:38
  • \$\begingroup\$ ahh. so your advice to me is to implement interleave with foldr? \$\endgroup\$ Oct 21, 2014 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, 2014 at 2:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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