Learning F#: The Game of Life (Vol. 9)

Intro

I decided to learn about Active Patterns within F# and find opportunities to apply them within my Game of Life implementation.

Active Patterns

I interpret Active Patterns as a feature within F# that enables a programmer to use labels as an alias to an expression when performing pattern matching.

Example 1

Here’s the first example:

let isValueNeighbor v1 v2 =
    match v1 >= 0
      &&  v2 >= 0 with
    | true  -> isAbsNeighbor v1 v2
    | _     -> isAbsNeighbor v2 v1

With Active Patterns, we can arguably enhance readability and rewrite the code like this:

let isValueNeighbor v1 v2 =
    match v1, v2 with
    | BothPositive    -> isAbsNeighbor v1 v2
    | NotBothPositive -> isAbsNeighbor v2 v1

To support this rewrite we had to implement the following Active Pattern:

let (|BothPositive|NotBothPositive|) (v1, v2) =

    if v1 >= 0 && v2 >= 0 
    then BothPositive
    else NotBothPositive

If you’ve noticed, we took the original code that I highlighted earlier:

match v1 >= 0
  &&  v2 >= 0 with

And lifted it into an Active Pattern:

    if v1 >= 0 && v2 >= 0 
    then BothPositive
    else NotBothPositive

Example 2

Here’s another example:

match cell1.X <> cell2.X
  ||  cell1.Y <> cell2.Y with
| true ->   isValueNeighbor cell1.X cell2.X
         && isValueNeighbor cell1.Y cell2.Y
| _    -> false

Applying Active Patterns to this code could result in the following:

 match (cell1,cell2) with
 | Different -> isValueNeighbor cell1.X cell2.X
             && isValueNeighbor cell1.Y cell2.Y
 | Same      -> false

Here’s the definition of the Active Pattern that we use for the above code:

let (|Same|Different|) (cell1, cell2) =

    if cell1.X <> cell2.X || cell1.Y <> cell2.Y 
    then Different
    else Same

Domain Logic

Here’s the domain logic:

module Model

type State = Alive | Dead
type Cell = { X:int; Y:int; State:State }

type Response = | Die
                | Survive
                | Resurect

let (|Same|Different|) (cell1, cell2) =

    if cell1.X <> cell2.X || cell1.Y <> cell2.Y 
    then Different
    else Same

let (|BothPositive|NotBothPositive|) (v1, v2) =

    if v1 >= 0 && v2 >= 0 
    then BothPositive
    else NotBothPositive
    
let isNeighbor cell1 cell2 =

    let isAbsNeighbor v1 v2 =
        match abs (v1 - v2) with
        | 0 | 1 -> true
        | _     -> false

    let isValueNeighbor v1 v2 =
        match v1, v2 with
        | BothPositive    -> isAbsNeighbor v1 v2
        | NotBothPositive -> isAbsNeighbor v2 v1

    match (cell1,cell2) with
    | Different -> isValueNeighbor cell1.X cell2.X
                && isValueNeighbor cell1.Y cell2.Y
    | Same      -> false

let createGrid rowCount = 

    [for x in 0..rowCount-1 do
        for y in 0..rowCount-1 do
            yield { X=x; Y=y; State=Dead } 
    ]|> List.map (fun c -> (c.X, c.Y), { X=c.X; Y=c.Y; State=Dead })
     |> Map.ofList

let setCell cell (grid:Map<(int * int), Cell>) =

    grid |> Map.map (fun k v -> match k with
                                | c when c = (cell.X, cell.Y) -> { v with State=cell.State }
                                | _ -> v)

let getStatus coordinate (grid:Map<(int * int), Cell>) =

    match grid.TryFind coordinate with
    | Some cell -> cell.State
    | None      -> Dead

let getNeighbors (coordinate:int*int) =
        
    let x,y = coordinate
    let west = x-1, y
    let northWest = x-1, y+1
    let north = x, y+1
    let northEast = x+1, y+1
    let east = x+1, y
    let southEast = x+1, y-1
    let south = x, y-1
    let southWest = x-1, y-1

    [west; northWest; north; northEast; east; southEast; south; southWest]

let createTimer timerInterval eventHandler =

    let timer = new System.Timers.Timer(float timerInterval)
    timer.AutoReset <- true
    timer.Elapsed.Add eventHandler

    async { timer.Start()
            do! Async.Sleep 500
            timer.Stop() }

let setReaction coordinate grid:Map<(int * int), Cell> = 

    let x,y = coordinate
    let count = coordinate |> getNeighbors
                           |> List.filter (fun coordinate -> grid |> getStatus coordinate = Alive)
                           |> List.length
    match count with
    | count when count < 2 
             ||  count > 3 -> grid |> setCell { X=x; Y=y; State=Dead }
    | 3                    -> match grid.TryFind coordinate with
                              | Some cell -> match cell.State with
                                             | Dead -> grid |> setCell { cell with State=Alive }
                                             | _    -> grid
                              | None      -> failwith "Cell doesn't exists"
    | _ -> grid

let cycleThroughCells (grid:Map<(int * int), Cell>) =

    grid |> Map.toSeq
         |> Seq.map snd
         |> Seq.fold (fun grid c -> grid |> setReaction (c.X, c.Y)) grid

Unit Tests

Here’s the tests:

module Tests

open FsUnit
open NUnit.Framework
open Model

[<Test>]
let ``cells sharing x-coordinate are neighbors``() =
   // Setup
   let cell1 = { X=0; Y=0; State=Dead }
   let cell2 = { X=0; Y=1 ; State=Dead }

   // Verify
   cell1 |> isNeighbor cell2 
         |> should equal true

[<Test>]
let ``cells sharing y-coordinate are neighbors``() =
   // Setup
   let cell1 = { X=0; Y=1; State=Dead }
   let cell2 = { X=1; Y=1; State=Dead }

   cell1 |> isNeighbor cell2 
         |> should equal true

[<Test>]
let ``cell that's right 1 and down 1 is neighbor``() =
   // Setup
   let cell1 = { X=0; Y=0; State=Dead }
   let cell2 = { X=1; Y=(-1); State=Dead }

   // Verify
   cell1 |> isNeighbor cell2 
         |> should equal true

[<Test>]
let ``cell that's right 1 and down-0 is neighbor``() =
   // Setup
   let cell1 = { X=0; Y=0; State=Dead }
   let cell2 = { X=1; Y=0; State=Dead }

   // Verify
   cell1 |> isNeighbor cell2 
         |> should equal true

[<Test>]
let ``cell that's right 1 and up 1 is neighbor``() =
   // Setup
   let cell1 = { X=0; Y=0; State=Dead }
   let cell2 = { X=1; Y=1 ; State=Dead }

   // Verify
   cell1 |> isNeighbor cell2 
         |> should equal true

[<Test>]
let ``cell that's up 1 is neighbor``() =
   // Setup
   let cell1 = { X=0; Y=0; State=Dead }
   let cell2 = { X=0; Y=1 ; State=Dead }

   // Verify
   cell1 |> isNeighbor cell2 
         |> should equal true

[<Test>]
let ``cell that's down 1 is neighbor``() =
   // Setup
   let cell1 = { X=0; Y=0;    State=Dead }
   let cell2 = { X=0; Y=(-1); State=Dead }

   // Verify
   cell1 |> isNeighbor cell2 
         |> should equal true

[<Test>]
let ``cell that's left 1 and up 1 is neighbor``() =
   // Setup
   let cell1 = { X=0; Y=0; State=Dead }
   let cell2 = { X=(-1); Y=1 ; State=Dead }

   // Verify
   cell1 |> isNeighbor cell2 
         |> should equal true

[<Test>]
let ``cell that's left 1 and down 1 is neighbor``() =
   // Setup
   let cell1 = { X=0;    Y=0;    State=Dead }
   let cell2 = { X=(-1); Y=(-1); State=Dead }

   // Verify
   cell1 |> isNeighbor cell2 
         |> should equal true

[<Test>]
let ``far away x-coordinates are not neighbors``() =
   // Setup
   let cell1 = { X=(-1); Y=0; State=Dead }
   let cell2 = { X=(+1); Y=0; State=Dead }

   // Verify
   cell1 |> isNeighbor cell2 
         |> should equal false

[<Test>]
let ``far away y-coordinates are not neighbors``() =
   // Setup
   let cell1 = { X=0; Y=(+1); State=Dead }
   let cell2 = { X=0; Y=(-1); State=Dead }

   // Verify
   cell1 |> isNeighbor cell2 
         |> should equal false

[<Test>]
let ``far away x,y-coordinates are not neighbors``() =
   // Setup
   let cell1 = { X=(+1); Y=(+1); State=Dead }
   let cell2 = { X=(+1); Y=(-1); State=Dead }

   // Verify
   cell1 |> isNeighbor cell2 
         |> should equal false

[<Test>]
let ``cells with same coordinates cannot be neighbors``() =
   // Setup
   let cell1 = { X=0; Y=0; State=Dead }
   let cell2 = { X=0; Y=0; State=Dead }

   // Verify
   cell1 |> isNeighbor cell2 
         |> should equal false

[<Test>]
let ``create grid``() =
    // Test
    let rowCount = 3
    let grid = rowCount |> createGrid
    
    // Verify
    grid.Count |> should equal 9

[<Test>]
let ``find center``() =
    // Setup
    let rowCount = 3
    let grid = rowCount |> createGrid

    let getCoordinate coordinate =
        match grid.TryFind coordinate with
        | Some coordinate -> true
        | None            -> false

    // Test
    let found = getCoordinate (1,1)

    // Verify
    found |> should equal true

[<Test>]
let ``get status``() =
    // Setup
    let rowCount = 3
    let grid = rowCount |> createGrid

    // Test
    let center = grid |> getStatus (1,1)

    // Verify
    center |> should equal Dead

[<Test>]
let ``set cell to alive``() =
    // Setup
    let rowCount = 3
    let target = { X=1; Y=1; State=Alive }

    let grid = rowCount |> createGrid
                        |> setCell target
    // Test
    let result = grid |> getStatus (1,1)

    // Verify
    result |> should equal Alive

[<Test>]
let ``get neighbors``() =
    // Setup
    let rowCount = 3
    let grid = rowCount |> createGrid

    let center = 2,2
    let count = center |> getNeighbors
                       |> List.length
    // Verify
    count |> should equal 8

[<Test>]
let ``Any live cell with fewer than two live neighbors dies, as if caused by under-population``() =
    // Setup
    let rowCount = 3
    let grid = rowCount |> createGrid
                        |> setCell { X=1; Y=1; State=Alive }
                        |> setReaction (1,1)
    // Verify
    grid |> getStatus (1,1) |> should equal Dead

[<Test>]
let ``Any live cell with two or three live neighbours lives on to the next generation``() =
    // Setup
    let rowCount = 3
    let grid = rowCount |> createGrid
                        |> setCell { X=0; Y=0; State=Alive }
                        |> setCell { X=1; Y=1; State=Alive }
                        |> setCell { X=2; Y=1; State=Alive }
                        |> setReaction (1,1)
    // Verify
    grid |> getStatus (1,1) |> should equal Alive

[<Test>]
let ``Any live cell with more than three live neighbours dies, as if by over-population``() =
    // Setup
    let rowCount = 3
    let grid = rowCount |> createGrid
                        |> setCell { X=0; Y=0; State=Alive }
                        |> setCell { X=1; Y=1; State=Alive }
                        |> setCell { X=0; Y=1; State=Alive }
                        |> setCell { X=1; Y=0; State=Alive }
                        |> setCell { X=2; Y=1; State=Alive }
                        |> setReaction (1,1)
    // Verify
    grid |> getStatus (1,1) |> should equal Dead

[<Test>]
let ``Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction``() =
    // Setup
    let rowCount = 3
    let grid = rowCount |> createGrid
                        |> setCell { X=0; Y=1; State=Alive }
                        |> setCell { X=1; Y=1; State=Dead }
                        |> setCell { X=0; Y=2; State=Alive }
                        |> setCell { X=1; Y=2; State=Alive }
                        |> setReaction (1,1)
    // Verify
    grid |> getStatus (1,1) |> should equal Alive

Conclusion

In conclusion, I decided to learn about Active Patterns within F# and find opportunities to apply them within my Game of Life implementation.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: