## Sunday, April 28, 2013

### Primality by Trial Division OR TDD Example in F# using FsUnit

"Youth, beauty, wisdom, courage – all
That happiness and prime can happy call."

-- Shakespeare All's Well That Ends Well
Act II, Scene I, Lines 182-183

I find RosettaCode to be a valuable resource of ideas for my daily Code Kata.  Recently I came across an entry in RosettaCode that did not have a F# example.  Once I finished my kata I mended that issue.

### Problem statement (from RosettaCode):

Write a boolean function that tells whether a given integer is prime. Remember that 1 and all non-positive numbers are not prime.  Use trial division. Even numbers over two may be eliminated right away. A loop from 3 to √n will suffice, but other loops are allowed.

### Step 1 (2 isPrime = true):

First step in solving the prime, if 2 is given in the input isPrime should return true.

#### Test Case:

[<Test>]
let ``Validate that 2 is prime`` () =
isPrime 2 |> should equal true

#### Code (to pass):

let isPrime x = true

It may look dumb, but this is all that is needed to pass the test.

### Step 2 (4 isPrime = false):

#### Test Case:

[<Test>]
let ``Validate that 4 is not prime`` () =
isPrime 4 |> should equal false

#### Code (to pass):

let isPrime x =
match x with
| 2 -> true
| x when x % 2 = 0 -> false

The mod 2, might be jumping the gun a little bit, but it follows the rules is just enough code to pass the tests.

Note that the match in this state will give a warning (warning FS0025: Incomplete pattern matches on this expression. For example, the value '0' may indicate a case not covered by the pattern(s). However, a pattern rule with a 'when' clause might successfully match this value.), we'll address that later.

### Step 3 (3 isPrime = true):

#### Test Case:

[<Test>]
let ``Validate that 3 is prime`` () =
isPrime 3 |> should equal true

#### Code (to pass):

let isPrime x =
match x with
| 2 -> true
| x when x % 2 = 0 -> false
| _ -> true

Again, this might seem dumb, but it is all we need to pass the test and we've fixed the warning from before.

### Step 4 (9 isPrime = false):

#### Test Case:

[<Test>]
let ``Validate that 9 is not prime`` () =
isPrime 9 |> should equal false

#### Code (to pass):

let isPrime x =
match x with
| 2 | 3 -> true
| x when x % 2 = 0 -> false
| _ -> false

Again, a bit dumb, but this was all that is needed to pass the tests.

### Test Case:

[<Test>]
let ``Validate that 5 is prime`` () =
isPrime 5 |> should equal true

#### Code:

let isPrime x =
match x with
| 2 | 3 -> true
| x when x % 2 = 0 -> false
| _ ->
let rec aux i =
match i with
| i when x % i = 0 -> false
| i when x < i*i -> true
| _ -> aux (i+2)
aux 3

This does not follow TPP, but RosettaCode gave us the algorithm they wanted us to use.  Since we followed TDD, we know that we did not break anything by putting a larger block of code in this iteration.

### Last Step (277 isPrime = true):

#### Test Case:

[<Test>]
let ``Validate that 277 is prime`` () =
isPrime 277 |> should equal true

#### Code:

The code is exactly the same as above, this test case was just a double check to make sure the solution scaled well.

### Full Example:

#### Entry in RosettaCode (as of 28 April 2013):

http://rosettacode.org/wiki/Primality_by_trial_division#F.23

#### Code:

open NUnit.Framework
open FsUnit

let isPrime x =
match x with
| 2 | 3 -> true
| x when x % 2 = 0 -> false
| _ ->
let rec aux i =
match i with
| i when x % i = 0 -> false
| i when x < i*i -> true
| _ -> aux (i+2)
aux 3

[<Test>]
let ``Validate that 2 is prime`` () =
isPrime 2 |> should equal true

[<Test>]
let ``Validate that 4 is not prime`` () =
isPrime 4 |> should equal false

[<Test>]
let ``Validate that 3 is prime`` () =
isPrime 3 |> should equal true

[<Test>]
let ``Validate that 9 is not prime`` () =
isPrime 9 |> should equal false

[<Test>]
let ``Validate that 5 is prime`` () =
isPrime 5 |> should equal true

[<Test>]
let ``Validate that 277 is prime`` () =
isPrime 277 |> should equal true

Thank you, F# Weekly for all the links to this blog!