Pleasing small victories

So a coworker got me hooked on Project Euler today, and I’ve been spending far too much of my free time on it. However, it did lead to a very pleasing moment.

One of the problems deals with Collatz sequences: For any number, divide by two if the number is evenly divisible by two, multiply by three and add one otherwise. Stop when you reach the number 1. The task at hand was to find the number between 1 and 1,000,000 with the longest Collatz sequence.

My first attempt at counting this sequence, rather predictably, failed on large input:

 collatzsz 1 = 1
 collatzsz n = 1 + collatzsz nxt where
     nxt = if 0 == mod n 2 then div n 2 else 3 * n + 1

Duh. Stack overflows everywhere. (Note: there’s probably a flag for GHC that will make this Just Work.) I figured that Haskell would probably go ahead and optimize tail calls for me, so I gave it a go:

 collatzsz 1 accum = 1 + accum
 collatzsz n accum = collatzsz nxt (1+accum) where
     nxt = if 0 == mod n 2 then div n 2 else 3 * n + 1

Sure enough, it works for even the most obnoxiously large values of n.

Yes, I know that this is exactly what the language is supposed to do, but sometimes it seems like a small victory when a piece of software does even that. So thanks to the good folks who make GHC. You made me smile today.

Posted in , | | Leave a response

Leave a Reply