Prime Factors Kata in F#
The Prime Factors Kata, is one of many BDD (Behavior Driven Development) katas out there to help developers practice development with a "BDD mind set". Long story short, I wanted to see what the solution would look like in F#...so I tried it...and now I'm writing a blog post on it :-).
What is a BDD Kata?
The Prime Factors BDD Kata introduces BDD concepts and helps developers get into the habit of finding a solution to a problem using a test driven development style. Kata's are meant to be done over and over again, until it becomes muscle memory. Once you've "mastered" the kata, it then becomes much easier to cut your teeth on a non-trivial/real world problem. Wax on, wax off.
The Goal for Prime Factors Kata
The goal of the Prime Factors Kata is to create a method that returns a list of primes for any whole number. The solution should be derived using a "BDD mind set". I would strongly recommend watching this video which shows the kata done in Ruby.
Prime Factors Solution in F#
Taking a BDD approach, this is the first solution I came up with:
let Primes number =
let mutable factors = []
let mutable n, factor = number, 2
while n > 1 do
if n % factor = 0 then
factors <- List.append factors [factor]
n <- n / factor
else factor <- factor + 1
factors
This is a pretty straightforward solution, but the solution isn't "functional"...some dead giveaways are the use of the mutable keyword and the use of loops (if I'm not mistaken, functional solutions are immutable and recursive in nature).
Refactoring the Solution
I wanted the solution to be a functional solution as opposed to a procedural solution. Since I took a test driven approach to development, I had many tests written to ensure the correctness of the algorithm...and because of this, I was able to refactor the algorithm KNOWING that my unit tests would catch any errors I may make. Here is the functional solution:
let Primes number =
let rec factorsOf number factor accumulator =
if number > 1 && number % factor = 0 then
factorsOf (number / factor) (factor) (List.append accumulator [factor])
else if number > 1 then
factorsOf (number) (factor + 1) (accumulator)
else accumulator
factorsOf number 2 []
As you can see, there is a huge difference between the procedural approach and the functional approach....good thing I had those unit tests ;-).
The Spec
Here are the unit tests (the spec) that came about using BDD (Behavior Driven Development):
namespace kata
open System
open System.Collections.Generic
open System.Linq
open NUnit.Framework
[<TestFixture>]
type when_factoring() =
class
//solution
let Primes number =
let rec factorsOf (number) (factor) (accumulator) =
if number > 1 && number % factor = 0 then
factorsOf (number / factor) (factor) (List.append accumulator [factor])
else if number > 1 then
factorsOf (number) (factor + 1) (accumulator)
else accumulator
factorsOf number 2 []
//methods added for readability of spec
let given = fun number -> Primes number
let shouldbe = fun (actual:IEnumerable<int>) (expected:IEnumerable<int>) -> Assert.IsTrue (actual.SequenceEqual expected)
[<Test>]
member t.given_0_should_be_empty() =
given 0 |> shouldbe []
[<Test>]
member t.given_1_should_be_empty() =
given 1 |> shouldbe []
[<Test>]
member t.given_2_should_be_2() =
given 2 |> shouldbe [2]
[<Test>]
member t.given_3_should_be_3() =
given 3 |> shouldbe [3]
[<Test>]
member t.given_4_should_be_2_2() =
given 4 |> shouldbe [2; 2]
[<Test>]
member t.given_5_should_be_5() =
given 5 |> shouldbe [5]
[<Test>]
member t.given_6_should_be_2_3() =
given 6 |> shouldbe [2; 3]
[<Test>]
member t.given_7_should_be_7() =
given 7 |> shouldbe [7]
[<Test>]
member t.given_8_should_be_2_2_2() =
given 8 |> shouldbe [2; 2; 2]
[<Test>]
member t.given_9_should_be_3_3() =
given 9 |> shouldbe [3; 3]
[<Test>]
member t.given_2730_should_be_2_3_5_7_13() =
given 2730 |> shouldbe [2; 3; 5; 7; 13]
end
Written: 8/24/2010