On Wed, Feb 12, 2014 at 3:10 AM, Kim-Ee Yeoh wrote:

I'd hazard to say that it's probably not the solution the author had in mind, so bonus points for novelty!

What solution do you think the author had in mind? He did hint to use define and use interleaveStreams and to avoid checking divisibility testing.

How would you prove it correct though?

I haven't attempted this yet, but if I were to, I'd go for an inductive proof. If you list the solution along with the numbers they correspond to (divide), you get: 1 2 3 4 5 6 7 8 9 10... 0 1 0 2 0 1 0 3 0 1... If you drop all the numbers corresponding to a 0 in the ruler function: 2 4 6 8 10... 1 2 1 3 1 ... then drop the numbers corresponding to a 1 in the ruler function: 4 6 ... 2 3 ... At each level, you drop every other number, and the first number of each successive level is 1 greater than the previous level. Formalize that a bit and you got a proof.

On Wed, Feb 12, 2014 at 03:10:21PM +0700, Kim-Ee Yeoh wrote:

On Wed, Feb 12, 2014 at 11:23 AM, Bryan Brady wrote:

...

ruler :: Stream Integer ruler = foldr1 interleaveStreams (map streamRepeat [0..])

This is an interesting solution.

I'd hazard to say that it's probably not the solution the author had in mind, so bonus points for novelty!

You're right that it's not the exact solution I had in mind, but I like it! I had in mind a more directly recursive version of ruler; I think proving the two solutions equivalent should not be too hard. -Brent

Thanks Isaac! It never crossed my mind that the problem was on the left hand side. On Wed, Feb 12, 2014 at 3:36 AM, Isaac Dupree < ml@isaac.cedarswampstudios.org> wrote:

[...] In this situation, if interleaveStreams evaluates its second argument before returning any work, it will never be able to return. Happily, the outer Cons of the result does not depend on the second argument. I can fix the issue just by making the second argument be pattern-matched lazily (with ~, i.e. only as soon as any uses of the argument in the function are evaluated):

interleaveStreams (Cons a as) ~(Cons b bs) = Cons a (Cons b

(interleaveStreams as bs))

So that's what the ~ does... :)

I'm not sure whether there's a practical difference between these and

Data.Stream's definition. Actually, I think they turn out to do exactly the same thing...

Yes, they do. I used the solution in Data.Stream to fix mine, though I didn't recognize the true source of the problem until you pointed it out. Thanks again!

On 2014-08-18 20:22, Curt McDowell wrote:

Funny, I was trying the same Homework, implemented interleaveStreams using the same algorithm you did (taking one item from each stream per recursive call), and got the same result with the ruler function hanging. It was also fixed by changing interleaveStreams to take from just one stream per call and switch back and forth between streams.

I hit the same problem when I did the exercise. In fact, it made me post this question on StackOverflow, asking about how pattern matching might cause the function to work differently: http://stackoverflow.com/questions/25078598/why-would-using-head-tail-instea... I thought the answers were quite enlightening, if only to emphasize that debugging this kind of problem is really difficult (to me). I only noticed that not using pattern matching for the second argument of 'interleave' helps by accident... -- Frerich Raabe - raabe@froglogic.com www.froglogic.com - Multi-Platform GUI Testing