Conway's Game of Life in F# (and Standard ML)

Hi,

here I want to show a solution to the algorithm for the Conway's Game of Life in F#.

(Edit: a live coding session recorded and commented, in Italian, by me is now available here: https://www.youtube.com/watch?v=FRH7Hawru78)


I developed a first version in Standard ML,  a language that is taught in the first part of the fantastic course "Programming Languages" (by Coursera), then I decided to port it to the quite similar,  nowadays more popular, F#.

The solution consists only in:
the function "numOfAliveNeightbours" that computes the number of the alive neighbours
the function "nextGeneration" that, given a grid, returns the grid representing the next generation of that grid
(so any runnable simulator are unavailable, ...for now).

Each cell is represented by a triple: two integer coordinates (x and y) and a state (Dead or Alive), so I defined both the types: state and cell:

   type state = | Dead | Alive
   type cell = int*int*state


state type consist only in two possible value: Dead and Alive, ,and cell is just a triple of int, int and state like (0, 0, Alive).

I found highly convenient to use these Dead Alive states instead of plain booleans, because the new defined states are more informative about the domain, and substantially don't add extra complexity anyway respect to using just booleans.

According to the rules of the game, the next status of a cell in a board depends of the current status of the cell itself and the number of its neighbours alive cells.

So in order to compose the pieces that allow me to get this new state I think that the solution needs to:
- get the set of the neighbours.
- count how many of them are alive

If I had a predicate areNeighbours that says if two cells are neighbours, I could obtain the neighbours by a filter, and the filter is as follow:

    let neighbours (cell, board) =   
            List.filter(fun c -> areNeighbours cell c) board                     
Type for function and parameters are missing: types can be inferred by the compiler. However, during the development phase I rather use types to avoid "misunderstanding" with the type inferences engine, so the first version of that function actually included type annotation, as follows:
    let neighbours (cell: cell, board: list cell): list cell =   
            List.filter(fun c -> areNeighbours cell c) board

(cell can be used as a variable name even if it clashes with the corresponding type name).

Only later I removed type annotations (helped by some unit tests giving confidence that things still works).

Here is areNeighbours functions that checks for each cell of the board if it is close to the given cell, and this is done as follows:

    let areNeighbours (x1,y1,_) (x2,y2,_) =
            abs (x1 - x2) <=1 && abs (y1 - y2) <= 1 && not (samePosition (x1,y1) (x2,y2)) 


... avoiding to consider any cell as "neighbour" with itself (i.e. any cell at the same x,y position):

    let samePosition (x1,y1) (x2,y2) =
            x1 = x2 && y1 = y2

In the same way I used a filter to get the neighbours, I can use a filter to get only the ones that are alive from the neighbours:

    let neighboursAlive (x,y,s) grid  =
            List.filter (fun (_,_,s) -> s = Alive) (neighbours( (x,y,s),grid))


 and here I count them just using the length of the list of the neighbours alive:

    List.length(neighboursAlive (x,y,s) grid)
 

I can make all these functions internal to "numOfNeighborsAlive" (that actually returns the number of neighbours alive) so I'll have at the end of the day only two functions visibile from outside of the module.

    let numOfNeighboursAlive (x,y,s) grid  =
        let samePosition (x1,y1) (x2,y2) =
            x1 = x2 && y1 = y2

        let areNeighbours (x1,y1,_) (x2,y2,_) =
            abs (x1 - x2) <=1 && abs (y1 - y2) <= 1 && not (samePosition (x1,y1) (x2,y2)) 
                               
        let neighbours (acell, grid) =   
            List.filter(fun c -> areNeighbours acell c) grid                     

        let neighboursAlive (x,y,s) grid  =
            List.filter (fun (_,_,s) -> s = Alive) (neighbours( (x,y,s),grid))

        List.length(neighboursAlive (x,y,s) grid)
 

Now it's time to see the function that actually computes the next generation on the bases of the rules:

- an alive cell stay alive only if 2 or 3 neighbours are alive

- a dead cell become alive only if 3 neighbours are alive

    let nextGeneration board = 
        let rec nextGenerationIter (remainingCells, accumul) =
            match remainingCells with 
                |(x,y,Alive)::T -> ( match numOfNeighborsAlive(x,y,Alive) board with
                                    | (2|3) -> nextGenerationIter(T, accumul @ [(x,y,Alive)])
                                    | _ -> nextGenerationIter(T, accumul @ [(x,y,Dead)])
                                    )
                |(x,y,Dead)::T -> ( match numOfNeighborsAlive (x,y,Dead) board with
                                    | 3 -> nextGenerationIter(T, accumul @ [(x,y,Alive)])
                                    | _ -> nextGenerationIter(T, accumul @ [(x,y,Dead)])
                                    )
                | [] -> accumul

        nextGenerationIter (board, [])

Basically the board is passed (a list of cells) to the function which calls the internal nextGenerationIter adding a new "accumulator" list, that among tail-recursive calls is populated one cell at time with appropriate state Alive of Dead.

It looks to me that one benefit is that the game rule are somehow directly represented in the pattern matching mechanism (match ... with) that also allow to separate the case where the current cell (as the head of the board, as a cell list) is Dead or Alive (matching (x,y,Dead)::T or (x,y,Alive)::T), so then applying the appropriate rule (two alives, or two or three alives, to make the same cell at the next generation alive.

T matches the tail, and is used for the recursive calls (so its head will be actually the new cell evaluated with the same criteria now described).

EDIT:
I haven't show any unit test, and neither the real process (and in the real order) used to code the solution developing tests and code together. But unit tests are available with the solution, and they actually have been used during the process of developing the solution itself.
For more information start from the Test Driven Development on Wikipedia.
END EDIT

So concluding, the F# code is available here (perhaps some names are not the same as in this post), and here is the initial version in Standard ML. 

Tests are available for both the solutions: nunit tests for fsharp and plain boolean expressions for Standard ML.

Suggested references are the already mentioned Coursera Programming Languages course for Standard ML.  and... Google! Carnegie Mellon University provide a free manual for Standard ML, and the University of Edinburgh a tutorial introduction.

To learn the paradigm the first part of the Coursera course is great.

Literature for F# may be needed to find the small differences in the syntax between Standard ML and F#, and to learn how to write applications that fully benefits of the dot.net or mono platform (O.O., GUIs, ...). However approaching directly to F# I think can be quite confusing, in term of trying to learn just a style, because of the extra-features available (O.O.), or the assumption that you have to use an IDE (Monodevelop, Xamarin, or Visual Studio), instead of a plain Emacs/Vim, so I'm glad that I used Standard ML in the first place.

Edit: a live coding session recorded on youtube and commented in Italian: https://www.youtube.com/watch?v=FRH7Hawru78