Haskell Kata

primes = sieve [2..] where
    sieve (p:ns) = p : sieve [n | n <- ns, n `mod` p > 0]

Here we are using the sieve of Eratosthenes. First, recall that Haskell is a non-strict language. In practice, Haskell runs lazily: calculation is delayed until you need to output a value or pick a branch in a conditional. There’s no reason why a non-strict language needs to be lazy. (I find the alternative quite inspiring.) An advantage of laziness is that, you can define a non-terminating list without creating a non-terminating program.

The simplest way to define a non-terminating list is to use an arithmetic sequence construct [2..]. This creates the list of integers starting at 2 and heading off toward infinity. Although arithmetic sequences are built-in, we could easily define an equivalent construct:

from i = i : from (i + 1)

Then [i..] == from i for any number i.

Starting with [2..] we pass the list of numbers through a sieve. We apply the sieve to a list of numbers such that the first p is a prime and the rest ns contains all the numbers greater than p with all the multiples of primes less than p filtered out. We want sieve (p:ns) to return the list of all primes starting at p Since we’re starting at p, its at the head (p :) of the list.

To get the primes after p, we do two things. First, we sift out the numbers in ns divisible by p. Then we apply the sieve to the result. Even though sieve recurses forever, it doesn’t matter because we’re lazy.

The last part is the sift [n | n <- ns, n `mod` p > 0]. It uses a comprehension. List comprehension are very intuitive. For the sift, we want the each number n in the list of numbers n <- ns such that n `mod` p > 0 or in other words we want to sift out all the numbers in ns that are divisible by p.