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:

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

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

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

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))
```

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

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))
```

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) ]
```

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
```

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]
```

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

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.