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 = trueIt 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.
Step 5 (5 isPrime = true):
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.23Code on TryFSharp.org:
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!
