Help explain this chunk of haskell code that outputs a stream of primes

Question

Hi,

I have trouble understanding this chunk of code:

let
  sieve (p:xs) = p : sieve {filter (\ x -> x 'mod' p /= 0) xs)
in sieve [2 .. ]

Can someone break it down for me? I understand there is recursion in it, but thats the problem I can't understand how the recursion in this example works.

Thank you!

Answer 1

It's implementing the Sieve of Eratosthenes

Basically, start with a prime (2), and filter out from the rest of the integers, all multiples of two. The next number in that filtered list must also be a prime, and therefore filter all of its multiples from the remaining, and so on.

Answer 2

It says "the sieve of some list is the first element of the list (which we'll call p) and the sieve of the rest of the list, filtered such that only elements not divisible by p are allowed through". It then gets things started by by returning the sieve of all integers from 2 to infinity (which is 2 followed by the sieve of all integers not divisible by 2, etc.).

I recommend The Little Schemer before you attack Haskell.

Answer 3

It's actually pretty elegant.

First, we define a function sieve that takes a list of elements:

sieve (p:xs)

In the body of sieve, we take the head of the list (because we're passing the infinite list [2..], and 2 is defined to be prime) and append it to the result of applying sieve to the rest of the list:

p : sieve (filter (\ x -> x 'mod' p /= 0) xs)

So let's look at the code that does the work on the rest of the list:

sieve (filter (\ x -> x 'mod' p /= 0) xs)

We're applying sieve to a filtered list. Let's break down what the filter part does:

filter (\ x -> x 'mod' p /= 0) xs

filter takes a function and a list on which we apply that function, and retains elements that meet the criteria given by the function. In this case, filter takes an anonymous function:

\ x -> x 'mod' p /= 0

This anonymous function takes one argument, x. It checks the modulus of x against p (the head of the list, every time sieve is called):

 x 'mod' p

If the modulus is not equal to 0:

 'mod' p /= 0

Then the element x is kept in the list. If it is equal to 0, it's filtered out. This makes sense: if x is divisible by p, than x is divisible by more than just 1 and itself, and thus it is not prime.

Answer 4

Contrary to what others have stated here, this function does not implement the true sieve of Eratosthenes. It does returns an initial sequence of the prime numbers though, and in a similar manner, so it's okay to think of it as the sieve of Eratosthenes.

I was about done explaining the code when mipadi posted his answer; I could delete it, but since I spent some time on it, and because our answers are not completely identical, I'll leave it here.

---

Firs of all, note that there are some syntax errors in the code you posted. The correct code is,

let sieve (p:xs) = p : sieve (filter (\x -> x `mod` p /= 0) xs) in sieve [2..]

1. let x in y defines x and allows its definition to be used in y. The result of this expression is the result of y. So in this case we define a function sieve and return the result of applying [2..] to sieve.

2. Now let us have a closer look at the let part of this expression:

   sieve (p:xs) = p : sieve (filter (\x -> x `mod` p /= 0) xs)
   

   1. This defines a function sieve which takes a list as its first argument.
   2. (p:xs) is a pattern which matches p with the head of said list and xs with the tail (everything but the head).
   3. In general, p : xs is a list whose first element is p. xs is a list containing the remaining elements. Thus, sieve returns the first element of the list it receives.

   4. Not look at the remainder of the list:

      sieve (filter (\x -> x `mod` p /= 0) xs)
      

      1. We can see that sieve is being called recursively. Thus, the filter expression will return a list.
      2. filter takes a filter function and a list. It returns only those elements in the list for which the filter function returns true.

      3. In this case xs is the list being filtered and

         (\x -> x `mod` p /= 0)
         

         is the filter function.

      4. The filter function takes a single argument, x and returns true iff it is not a multiple of p.

3. Now that sieve is defined, we pass it [2 .. ], the list of all natural numbers starting at 2. Thus,

   1. The number 2 will be returned. All other natural number which are a multiple of 2 will be discarded.
   2. The second number is thus 3. It will be returned. All other multiples of 3 will be discarded.
   3. Thus the next number will be 5. Etc.