Understanding prime number generator

Question

This site shows a function that generate a list of prime numbers.

-module(eratosthenes).
-export([prime_numbers/1]).

% Sieve of Eratosthenes algorithm for finding all prime numbers up to N.
% http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

% Generate list of prime numbers up to N.
prime_numbers(N) when is_number(N) ->
prime_numbers(N, generate(N)).

prime_numbers(Max, [H|T]) when H * H =< Max ->
   [H | prime_numbers(Max, [R || R <- T, (R rem H) > 0])];

prime_numbers(_, T) -> T.

% Generate sequence 2..N
generate(N) -> generate(N, 2).

generate(Max, Max) -> [Max];

generate(Max, X) -> [X | generate(Max, X + 1)].

I did not understand the function at:

prime_numbers(_, T) -> T.

I did this example using a pen and paper:

prime_numbers(5)

1 - prime_numbers(5, [2,3,4,5])
2 - [2 | prime_numbers(5, [R || R <- [3,4,5], (R rem H) > 0)]
3 - [2 | prime_numbers(5, [3,5])]

prime_numbers(5, [3,5])

H * H =< MAX

3*3 =< 5 (False)

prime_numbers(_, T) -> T.

H = 3
T = 5

prime_numbers(5, [3,5]) = [5]

resp: [2,5]


or prime_numbers(5, [3,5]) = [3|[5]]

Answer 1

To understand this, you must look at the whole function:

prime_numbers(Max, [H|T]) when H * H =< Max ->
   [H | prime_numbers(Max, [R || R <- T, (R rem H) > 0])];
prime_numbers(_, T) -> T.

I have removed a newline since it doesn't really apply in this case. The idiom in Erlang is to keep clauses for a function together like this. Note that this function has two clauses. We pattern match against them^[0]. So this reads:

"Suppose we are given something named Max and a list of at least one element with [H|T]. Deconstruct the list into the head element H and the rest of the list T. Now, this pattern has a when guard so it only applies if H*H =< Max.

If this doesn't match, say if the when guard is wrong or we are given an empty list [], then we try to match against the next clause, (_, T). This one always matches and throws away the first parameter (_). It then matches whatever is in the 2nd parameter and binds it to T. Then it runs its body."

The key to understanding this is to understand pattern matches. Once you grasp those, the code should be clear and easy to read.

^[0] Look up the concept of pattern matching. It is central to many languages like Prolog, ML, Haskell, Erlang, ...