WARNING! This post contains a spoiler for Problem #7 listed at Project Euler. Do not read the rest of this post if you’re planning to attempt to solve the problem yourself.
Problem #7 was as boring as batshit (to be quite frank). The only reason I’m posting about it is to keep The Head happy 
The reason I thought it was boring was because it was just the age-old problem of “how fast can you generate primes”:
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10001st prime number?
A simple search of the web reveals a million different ways of solving this problem — mostly written by people smarter than me 
So did I cheat? No I didn’t. I wrote the standard Sieve of Eratosthenes implementation in Haskell and got the answer in a respectable amount of time. Exciting stuff 
I browsed around the web a little bit after solving the problem because I was interested to see how others might have solved it using Haskell. Yes, I am aware that there is a whole page dedicated to it but that wasn’t enough.
After a bit of a search, I stumbled across this little doozy. If you can make heads or tails of it you’re a better man than I It’s quite a mind job to get your head around how this code works. This is an exercise I leave to the reader.
merge :: (Ord a) => [a] -> [a] -> [a] merge xs@(x:xt) ys@(y:yt) = case compare x y of LT -> x : (merge xt ys) EQ -> x : (merge xt yt) GT -> y : (merge xs yt) diff :: (Ord a) => [a] -> [a] -> [a] diff xs@(x:xt) ys@(y:yt) = case compare x y of LT -> x : (diff xt ys) EQ -> diff xt yt GT -> diff xs yt primes, nonprimes :: [Integer] primes = [2, 3, 5] ++ (diff [7, 9 ..] nonprimes) nonprimes = foldr1 f $ map g $ tail primes where f (x:xt) ys = x : (merge xt ys) g p = [ n * p | n <- [p, p + 2 ..]] main :: IO () main = print $ primes !! 10000
Enjoy
PS. Jon - are ya happy now? 
June 17, 2008
I am beside myself with glee…
June 17, 2008
The next problem will be a bit more interesting, but not much
It’ll get a lot more exciting as we progress past the mundane and into the fun problems.
June 20, 2008
I don’t understand the difficulty. It produces an ordered (via classic mergesort) list of nonprimes from {p*p, p*(p+2), …} (map g) for every odd (tail primes) prime p, and produces the primes by diffing the odd integers with the nonprimes … all via heavy use of lazy evaluation.
P.S. I don’t know Haskell, I’ve never programmed it or ML or anything similar (mostly C, Java, and Perl), but isn’t the point of declarative languages to be transparent and problem oriented? It all seemed pretty obvious to me, although I did have to google foldr1.
June 20, 2008
Why does your blog swallow comments? I explained the (obvious) logic of this, but it’s gone. Mergesort (classic algorithm) p*p, p*(p+2), … for each odd prime p and you get the odd nonprimes. Diff (classic algorithm) that with the odd integers and you get the odd primes. Everything gets generated as needed via lazy evaluation. Manually throw in 2 (so the 10000 count is right), and 3 and 5 to “prime” the primes list. You don’t even need to know Haskell … I don’t (but I googled foldr1).
June 20, 2008
@truth seeker: The comment about difficulty was a bit tongue in cheek. This solution, which I do understand fully, was way more interesting than the standard Sieves that you see around the traps. That’s why I posted it.
The blog doesn’t swallow comments. Comments are moderated, and since I don’t sit in front of my computer 24/7, there is sometimes a lag between when you post and when your comment appears. I’m guessing this isn’t the first time you’ve posted on a blog before, so why assume that your comments been eaten when moderation is relatively common?
Thanks for the explanations, despite the fact that it wasn’t needed (particularly the second one).
June 21, 2008
Your first statement
“If you can make heads or tails of it you’re a better man than I It’s quite a mind job to get your head around how this code works. This is an exercise I leave to the reader.”
is not at all consistent with your second statement. Regardless of the smiley, “tongue in cheek” is not enough to explain the discrepancy. I think the implication is clear, and is furthered with your disingenuous “Thanks for the explanations, despite the fact that it wasn’t needed” — you left it as an exercise for the reader, I’m a reader, and other readers can read my explanation(s) (the second adds details to the first).
“I’m guessing this isn’t the first time you’ve posted on a blog before, so why assume that your comments been eaten when moderation is relatively common? ”
Earlier posts went through without disappearing. And your site is abnormal; most moderated sites put up some sort of “held for moderation” notice (I did later get some “held as spam” notices from your site, in addition to the sheer disappearance). Positive feedback is a good UI attribute that your site is lacking in.
June 23, 2008
@truthmachine: There are multiple levels of spam protection on this site (because the amount of spam comments is insane). The first few would have come through fine, then the others would have been caught as spam because of the rate you were posting. Now that I’ve “moderated” you, you should see your comments come through without my approval and without being caught by the spam catcher. That is, of course, unless you post a million links and talk about Viagra
I won’t be adding any “held for moderation” functionality to this blog. Most of the time people’s comments go through just fine without me having to moderate them. If you smell like a spammer expect a bit of time to get through moderation.
OK, point taken. If that’s not how you read my comments then I guess I wasn’t clear in my intention.
I did understand how it worked. The first of your explanations was fine. The second wasnt necessary. The reason I had a stab at your second post was because of your complaining about the blog “swallowing” comments when it wasn’t the case.
I’m sure that the other readers will get something out of what you have written if they do struggle to understand the code, so thanks. But how about you work on your tone a bit mate? You’ve obviously got a brain in your head and it’s great to have comments from people who fit into that category. However, the tone of your comments is very “high and mighty”. I’ll work on making your time here more pleasant if you work on making your comments more pleasant to read?
Deal?