Introduction

In the first two installments of our functional programming series we had a look at immutability and functional transformations. These crucial features of functional programming languages can somehow be expressed in modern object oriented languages, even though use of them in non-functional languages requires discipline and adopting a different programming style. In this installment we will present a feature that can't be brought to the languages that were not originally designed for it and that is one of the main reasons for a terse syntax. Enter type inference.

Implicit type declaration

The articles and presentations about functional programming usually list such FP advantages as high order functions, data immutability by default, pattern matching and terse syntax. Some functional languages are also capable of implicit type declaration, known as type inference. Type inference has also been available for local variables in C# since the version 3.0, as shown in this statement:

C#
var n = 42;

It works in a similar way in F#:

F#
let n = 42

But in F# type inference goes far longer than that. You can infer function arguments in the same way:

F#
let sum x y = x + y

Execute the above line in F# Interactive, and it will show how it resolved parameter types for the function "sum":

F#
val sum : x:int -> y:int -> int

In this case the arithmetic operator "+" gave F# Interactive a hint that it's dealing with numbers, and it chose "int" type for them. If the code doesn't provide any hint about parameter data types, then the arguments stay generic and the function can be used with any type:

F#
let make_tuple x y = (x, y)

Response from F# Interactive:

F#
val make_tuple : x:'a -> y:'b -> 'a * 'b

More power-ups

So far it looks like a code typing convenience: when defining F# functions, we don't need to be explicit about its parameter types (unless we want to override default behavior), so we will end up with more compact code which is a well-known advantage of most functional languages. But there's much more power in type inference than possibility to omit type definitions. Unlike object oriented languages where generic algorithms and data structures require writing code in a certain way, type inference in functional languages allows generics happen implicitly, without special effort or attention. And this may lead to interesting discoveries.

Let's look at an F# implementation of the Conway's Game of Life – a zero player game that models evolution of life within a two-dimensional board. The game is played according to the following rules (taken from Wikipedia):

  1. Any live cell with fewer than two live neighbours dies, as if caused by under-population.
  2. Any live cell with two or three live neighbours lives on to the next generation.
  3. Any live cell with more than three live neighbours dies, as if by overcrowding.
  4. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

Below is a possible F# implementation of the game: let neighbours (x, y) = [ for i in x-1..x+1 do for j in y-1..y+1 do if not (i = x && j = y) then yield (i,j) ]

F#
let isAlive pattern cell =
    pattern |> List.exists ((=) cell)

let aliveNeighbours pattern cell =
    neighbours cell |> List.filter (isAlive pattern)

let survives pattern cell =
    aliveNeighbours pattern cell
    |> List.length |> fun x -> x >= 2 && x <= 3

let reproducible pattern cell =
    aliveNeighbours pattern cell
    |> List.length = 3

let allDeadNeighbours pattern =
    pattern
    |> List.collect neighbours
    |> Set.ofList |> Set.toList
    |> List.filter (not << isAlive pattern)

let nextGeneration pattern =
    List.append
        (pattern |> List.filter (survives pattern))
        (allDeadNeighbours pattern |> List.filter (reproducible pattern))

Now to test the implementation we need to define a test pattern:

F#
let pattern = [(1,1);(1,2);(2,3);(2,4)]

So if we now execute nextGeneration function:

F#
nextGeneration pattern

we will receive the following output:

F#
val it : (int * int) list = [(1, 2); (2, 3); (1, 3); (2, 2)]

Define the meaning of a neighbour

Have a closer look at the implementation. Can you spot a place where it says that it's an implementation for a two-dimensional board? When I talk about Conway's Game of Life at a live presentation, I usually ask this question after scrolling down the page a little to hide the "neighbours" function. And it takes some time before somebody from the audience says "but you hid the "neighbours"! That is the only function which exposes number of board dimensions."

Yes it is. There is no other place in the algorithm that says anything about whether we are implementing the Conway's Game of Life for two-dimensional board, three-dimensional board or maybe even the space without geometrical dimensions. The algorithm can be used for any space abstraction as long as we define the meaning of a neighbour. Here's how it will look for three-dimensional board:

F#
let neighbours (x, y, z) =
    [ for i in x-1..x+1 do
        for j in y-1..y+1 do
        for k in z-1..z+1 do
        if not (i = x && j = y && k = z) then yield (i,j,k) ]

let isAlive pattern cell =
    pattern |> List.exists ((=) cell)

let aliveNeighbours pattern cell =
    neighbours cell |> List.filter (isAlive pattern)

let survives pattern cell =
    aliveNeighbours pattern cell
    |> List.length |> fun x -> x >= 2 && x <= 3

let reproducible pattern cell =
    aliveNeighbours pattern cell
    |> List.length = 3

let allDeadNeighbours pattern =
    pattern
    |> List.collect neighbours
    |> Set.ofList |> Set.toList
    |> List.filter (not << isAlive pattern)

let nextGeneration pattern =
    List.append
        (pattern |> List.filter (survives pattern))
        (allDeadNeighbours pattern |> List.filter (reproducible pattern))

Note what's changed: only the "neighbours" function! The rest is identical. But can we rewrite the algorithm to support multiple board dimensions at the same time? Yes we can. Enter F# discriminated unions and pattern matching:

F#
type Cell =
    | Line of int
    | Surface of int * int
    | Space of int * int * int
    | Spacetime of int * int * int * int

let neighbours cell =
    match cell with
    | Line(a) -> [ for i in a-1..a+1 do
        if not (i = a) then
            yield Line(i) ]
    | Surface(a,b) -> [ for i in a-1..a+1 do
        for j in b-1..b+1 do
        if not (i = a && j = b) then
            yield Surface(i,j) ]
    | Space(a,b,c) -> [ for i in a-1..a+1 do
        for j in b-1..b+1 do
        for k in c-1..c+1 do
        if not (i = a && j = b && k = c) then
            yield Space(i,j,k) ]
    | Spacetime(a,b,c,d) -> [ for i in a-1..a+1 do
        for j in b-1..b+1 do
        for k in c-1..c+1 do
        for l in d-1..d+1 do
        if not (i = a && j = b && k = c && l = d) then
            yield Spacetime(i,j,k,l) ]

I skipped the rest of the algorithm – it's identical to previous implementations. Now we can write unit tests for our multi-dimensional implementation that will verify behavior for both 2D and 3D boards:

F#
[<Test>]
    member this."Square in 3d should not change"() =
        let pattern = [Space(1,1,0); Space(1,2,0); Space(2,1,0); Space(2,2,0)]
        pattern
        |> nextGeneration
        |> should equal pattern

[<Test>]
    member this."Cube in 3d should die"() =
        let pattern = [Space(1,1,1); Space(1,2,1); Space(2,1,1); Space(2,2,1); Space(1,1,2); Space(1,2,2); Space(2,1,2); Space(2,2,2)]
        pattern
        |> nextGeneration
        |> should equal List.empty

But wait – we don't need to restrict us to geometrical distances between cells. We can implement Conway's Game of Life for colors! We just need to throw a definition of neighouring colors:

F#
type Color = Red | Green | Blue | White | Gray | Black | Orange | Yellow | Brown
let neighbours color =
    match color with
    | Red -> [Red;Orange;Brown]
    | Green -> [Green;Blue;Yellow]
    | Blue -> [Blue;Green]
    | White -> [White;Gray]
    | Black -> [Black;Gray]
    | Gray -> [Gray;Black;White]
    | Orange -> [Orange;Red;Yellow]
    | Yellow -> [Yellow;Orange;Green]
    | Brown -> [Brown;Red]

Again, the remaining part of the algorithm is a verbatim copy of our original definition, so I skipped that. To test the implementation, we'll define a test pattern:

F#
let pattern = [Red;Green;Orange;Black]

...and execute the "nextGeneration" function:

F#
nextGeneration pattern

Here's the result of the execution:

F#
val it : Color list = [Red; Orange]

Initially generic functions

While you have support for generics in C#, you don't have the same implementation transparency due to lack of type interference. Specialized implementations in C# are more straightforward (and smaller in size) than generic ones, so developers usually begin with specialized algorithms and data structures and only convert them to generic implementations once they have needs for that. In F# it's opposite: the functions are initially generic with type constraints applied only where they refer to functions with arguments or return values of specific types. And as we saw in examples above, such language capability leads to very high level of code reuse, including applicability to data types that we haven't originally thought of.

UP NEXT…

In the next and last installment of this article series we will look at pattern matching that serves as a foundation for symbolic computation where functional languages are especially efficient.

Publisert 12/02/2014 av

Vagif Abilov