Project Euler

Haskell Prime Number Generator

This one has been curly, but I have finally implemented the Python Prime Number Generator using Haskell. This has been a major stumbling block to continuing on with Haskell answers to Project Euler, as a Primes module is critical to many of these challenges. Below I have recapped the Python version, and followed it with the Haskell version:

Python

def first_k_primes(k):
    k, n = k - 2, 5
    while k:
        if is_prime(n):
            yield n
            k = k -1
        n = n + 2

Haskell

isPrime k (x:xs) = if (mod k x) > 0
                   then isPrime k xs
                   else False
isPrime _ []     = True

gatherPrimes k p = if (isPrime k p)
                   then k : gatherPrimes (k + 2) p ++ [k]
                   else gatherPrimes (k + 2) p

Ok, so there are heaps of examples out there that I could have followed, but I was determined to do this on my own! No Google, no cheats, just quality time with GHCi. The whole point of working through these Project Euler challenges is to learn Haskell. Sometimes, that means doing it a little wrong and completely pig-headed!

I realise that this is not a pretty solution. But then, neither was the Python one really. I like the Python version because it was a great chance to play with generators, which were new to me. And, I like the Haskell one for much a similar reason. I battled with this, and I am proud to produce a solution that is as succinct as the Python version and that is infinite. That is one of the coolest things about functional programming, the ability to run with an infinite series.

This is a start. It really is horribly slow. But now that I have got this far, I am happy to look at the Haskell docs on this and implement something faster. (It is a little scary how much time I have spent on this, only to overhaul it – but then, I said from the start that I was in this for the hard-yards and the long-haul.)

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s