REVISED: Thursday, February 8, 2024
Haskell And Prime Numbers.
I. SIEVE OF ERATOSTHENES
Eratosthenes of Cyrene (275-194 B.C.) was a Greek mathematician who created the Sieve of Eratosthenes, an algorithm for rapidly locating all prime numbers within a range of integers.
"Copy Paste" the following program into your text editor and then "File, Save As" Eratosthenes.hs to your working directory:
sieve :: Integral a => [a] -> [a]
sieve (p : xs) = p : sieve [x | x <- xs, x `mod` p /= 0]
primes :: [Integer]
primes = sieve [2..]
main = print $ take 100 primes
Load the example into GHCi as follows:
GHCi, version 9.8.1: http://www.haskell.org/ghc/ :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude>
Prelude> :load Eratosthenes
[1 of 1] Compiling Main ( Eratosthenes.hs, interpreted )
Ok, modules loaded: Main.
Prelude>
Call the main function, take the first 100 prime numbers generated by our program, and print them as follows:
Prelude> main
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97, 101,103,107,109,113,127,131,137,139,149,151,157,163,167,173, 179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263, 269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359, 367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457, 461,463,467,479,487,491,499,503,509,521,523,541]
Prelude>
II. PRIME NUMBER DEFINITION
A prime number is a natural number, a counting number, greater than 1 with no positive divisors or factors other than 1 and itself.
III. PRIMES
primes is a function name, primes is not a Haskell keyword.
primes :: [Integer]
primes = sieve [2..]
The initial prime generated by sieve is 2.
IV. LIST COMPREHENSION
The following sieve function is a list comprehension which takes, as shown in its type signature, a list as its input and produces a list as its output.
sieve :: Integral a => [a] -> [a]
sieve (p : xs) = p : sieve [x | x <- xs, x `mod` p /= 0]
The sieve function obtains its arguments (p : xs) by deconstructing the beginning of the list sieve, to get its head p and tail xs.
After we have the arguments, read the sieve function from right to left.
The list comprehension iterates over xs, binding each element to x, which it returns if x is not (/=) evenly divisible by p.
, comma before the predicate is pronounced, "such that".
<- arrow is pronounced, "drawn from". A generator expression binds a variable on the left of a <- arrow to an element of the list on the right.
| pipe is pronounced, "such that". The part before the | pipe, x, is called the output function. The expression on the left of the | pipe is evaluated for each combination of generator expressions on the right.
p : sieve puts p on the front of a new list, which is constructed by calling sieve.
The sieve function determines whether or not the head of the list is a prime, and then calls itself recursively on the tail of the list. Therefore, sieve is a tail recursive function.
sieve is a function name, sieve is not a Haskell keyword.
The function sieve is defined in terms of itself; therefore, sieve is recursive. Haskell is lazily evaluated, and it will do no more work than is necessary, and stop once the take 100 primes have been calculated.
As shown below [2..] could produce an infinite number of integers starting from the number 2 if it were allowed to do so. When it is run as part of the total program we are saved from the imperative programming results of an infinite loop by the lazy nature of Haskell's functional programming language in which elements of the range object are only generated when they are needed.
Prelude> [2..]
[2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25, ...
The sieve function takes a single list of integers as its argument, and assumes that the first integer in the list is a prime. The sieve function then removes from the list integers that are not prime.
V. TAKE
take is a Haskell Prelude function name.
The Prelude take function returns a sublist consisting of the first k elements from the sublist. Therefore, we are working with several lists, the [2..] list of integers, the take sublist of prime numbers, and each new list created from the integers which could not be divided by the last prime division.
VI. ANALYSIS
When our Sieve of Eratosthenes starts [2..] provides us with the prime number, 2 and a list of xs.
p is bound to 2.
x is bound to 2.
In other words:
First, sieve is passed a list of all integers greater than or equal to 2.
Second, sieve uses 2 as the first prime and passes itself a list of all remaining integers not divisible by 2 ([3, 5, 7, 9, 11, 13, ...]).
Third, sieve uses the 3 as the second prime and passes itself a list of all remaining integers not divisible by 3 ([5, 7, 11, 13, ...]).
Fourth, this process proceeds recursively until the number of primes necessary to satisfy the take requirement of 100 prime numbers is met.
The lists discussed above are list generators, functions which calculate only on demand the next number in a list.
VII. CONCLUSION
In this tutorial, you have been introduced to using Haskell to find prime numbers.
VIII. REFERENCES
Bird, R. (2015). Thinking Functionally with Haskell. Cambridge, England: Cambridge University Press.
Davie, A. (1992). Introduction to Functional Programming Systems Using Haskell. Cambridge, England: Cambridge University Press.
Goerzen, J. & O'Sullivan, B. & Stewart, D. (2008). Real World Haskell. Sebastopol, CA: O'Reilly Media, Inc.
Hutton, G. (2007). Programming in Haskell. New York: Cambridge University Press.
Lipovača, M. (2011). Learn You a Haskell for Great Good!: A Beginner's Guide. San Francisco, CA: No Starch Press, Inc.
Thompson, S. (2011). The Craft of Functional Programming. Edinburgh Gate, Harlow, England: Pearson Education Limited.
