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.