Within this article I want to show you how to calculate prime numbers in F# by writing only one line of code. This shows the strength and elegance of functional programming languages.

In the first step we want to think about the basic functions needed to calculate some prime numbers. We need to filter all prime numbers out of a list of numbers. To check whether a number is a prime number it is possible to use modulo calculation. If a number modulo all previous numbers is not zero, then it is a prime number.

In summary we need following function:

–          filter: to filter a list of numbers

–          countUp: to create a list of numbers in a given range

–          checkAll: to check a number against all previous numbers

–          isPrime: to check whether a number is a prime number

 
The following source code shows a possible implementation of these functions.

let rec countUp x y = 
    if x > y
    then []
    else x::countUp (x+1) y

let rec checkAll f v = 
    match v with
        [] -> true
      | x::xs -> if f(x) then checkAll f xs else false

let rec filter f v = 
    match v with
        [] -> []
      | x::xs -> if f(x) then x::filter f xs else filter f xs

let isPrime x =
    checkAll (fun y -> x%y<>0) (countUp 2 (x/2))

let a = countUp 1 20
let b = checkAll (fun x -> x<20) a
let c = filter (fun x -> x%2=0) a
let d = isPrime 2
let e = isPrime 3
let f = isPrime 4

If you execute this source code the following output will be shown:

val a : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19; 20]

val b : bool = false

val c : int list = [2; 4; 6; 8; 10; 12; 14; 16; 18; 20]

val d : bool = true

val e : bool = true

val f : bool = false

By using this functions it is possible to calculate all prime numbers with the following command:

let primes = (countUp 2 20) |> filter isPrime

The previous solution contains the function isPrime. But this function only calls another function. Therefore it is possible to optimize the code and remove the isPrime function. The following source code shows the new solution to calculate prime numbers.

let rec countUp x y = 
    if x > y
    then []
    else x::countUp (x+1) y

let rec checkAll f v = 
    match v with
        [] -> true
      | x::xs -> if f(x) then checkAll f xs else false

let rec filter f v = 
    match v with
        [] -> []
      | x::xs -> if f(x) then x::filter f xs else filter f xs

let primes = (countUp 2 20) |> filter (fun x -> checkAll (fun y -> x%y<>0) (countUp 2 (x/2))) 

As you can see we are far away from a solution with just one line of code. But the current source code contains a lot of not needed functions. The functions filter, countUp and checkAll are very basic functions which are needed very often. Therefore these functions are part of the F# standard libraries. The following standard functions may be used to replace our own functions.

–          countUp may be replaced by [x..y]

–          checkAll may be replaced by List.forall

–          filter may be replaced by List.filter

 
By using the standard libraries it is possible to implement the prime number calculation in a single line of code. The following source code shows the final solution.

let primes = [2..20] |> List.filter(fun x -> List.forall(fun y -> x%y<>0) [2..x/2])

Summary

Functional programming languages offer elegant and efficient ways to implement mathematical calculations. For example a basic prime number calculation can be implemented in only one line of code.