Tic Tac Toe in F# – Part 2

Tic Tac Toe in F# – Part 2

In the Tic Tac Toe in F# – Part 1 (Part 1 of this tutorial series), I talked about F# and explored some of its features using the Tic Tac Toe game as an example. In this part, I am going to continue exploring some other features. Here is the link to the source code to help you follow along:

https://github.com/ymassad/TicTacToeFSharp/blob/master/src/BoardModule.fs

In the previous tutorial, I explained the following function:

The following expression:

..gives us the row in the board at the specified index. The tryFind function in this case returns a value of type Row option. It will either contain a Row value, or no value in case the map does not have a value at the specified index.

The result is then passed (using the forward pipe operator “|”) as the “second” argument to the Option.defaultValue function. This function is used to return an alternative value (emptyRow in this case) if no Row was found.

Here is the definition of the next function, getCell:

It takes the location of a cell in the board as row and column indexes including the board itself, and returns the cell value in the board. Based on the knowledge of F# you learned so far, you should be able to understand this function.

Editorial Note: Reading the first part of this tutorial series is highly recommended to understand the rest of the tutorial in this series. In case you haven’t already, read it here Tic Tac Toe in F# – Part 1.

The next function is more interesting:

As you might have guessed, the job of the allCellsInRow function is to return all cells in a row! It takes a Row and returns a sequence of CellStatus values.

More specifically, the return type of this function is seq<CellStatus>. A sequence in F# is like IEnumerable in C#. Actually, if you use an IL decompiler to view the allCellsInRow function, you will see that the return type of this function is IEnumerable<CellStatus>.

Items in an F# sequence is evaluated as the sequence is consumed. For example, if you use only a single element from the sequence returned by getCellInRow, only a single invocation of getCellInRow will be made (instead of three).

The body of this function is a sequence expression. A sequence expression is created using the seq { } syntax. If you ever created an iterator method in C#, then you might have guessed what the F# yield keyword does in this function. Here, yield describes the intention to return an item. However, only when an item is requested by the consumer, does the expression that follows the yield keyword gets evaluated.

It is worth noting here that the yield keyword in F# is not designed only for sequence expressions. A sequence expression is just one type of a computation expression. Computation expressions allow us to do very interesting things in F# but they are out of scope of this introductory article series.

An even more interesting function is the allCells function:

This function returns all the cells in a board as a sequence. For each row index, it obtains the corresponding Row in the board and then it calls allCellsInRow to obtain the cells in that row.

All of this is done inside a sequence expression. And here, yield! is used instead of yield. If we used yield instead of yield!, then the return type of allCells would be seq<seq<CellStatus>> (a sequence of sequences). This is because the return type of allCellsInRow is seq<CellStatus>.

yield! has the effect of flattening the yielded sequence into individual items. In C#, there is no corresponding feature. An AllCells function in C# would look like this:

Here is the next function:

The updateCellInRow function “updates” the status of a cell in a specific Row. Of course, when I say updates, I mean return a new Row with the updated cell.

As explained in part 1 of this tutorial series, the return value of this function is called a record expression. In this case, we are creating a Row value. For Cells, we are “updating” the original row cells to modify the cell in the specified index. The Map.add function will either add a new entry to the map or will “replace” the existing entry with a new value.

The next function updateRowInBoard updates a row in a board. It is very similar to updateCellInRow.

With the knowledge you have so far about F#, you should easily be able to understand the updateCell function (which updates a specific cell in a board), and the emptyBoard value (which represents a brand-new board).

Notice how updateCell uses updateCellInRow and updateRowInBoard to do its job.

Next is the isFull function:

You give this function a board and it tells you whether the board is full, i.e., whether all cells have been used.

Notice the forward pipe operator (|>) in this function. We start with the board and give it to the allCells function. This will give a sequence of all cells in the board.

Then I give this sequence to the Seq.forall function. Seq.forall will test each cell in the sequence to see if it matches a certain condition. In this case, we use a lambda expression for such a test. The lambda returns true if the cell status is HasX or HasO. The keyword fun is used to express a lambda expression.

The Seq.forall function takes two parameters, a test function (or a predicate), and a sequence. In the isFull function, we are passing the lambda as the first parameter of Seq.forall. For the second parameter, we are passing the return value of allCells (using the forward pipe operator).

It is worth noting that instead of a lambda, we can use a function value like this:

The first parameter of Seq.forall which is the predicate parameter is of type (‘T -> bool). The type of this parameter is a function. So, when we call Seq.forall, we pass a function. The first time, we did so using a lambda expression, and the second time using a function value.

It is worth noting that functions like Seq.forall are called higher-order functions. More specifically, higher-order functions are functions that have parameters of type function, and/or that return a function.

Let’s look at the formatCell function:

The body of this function is a match expression. A match expression is very similar to the switch expression introduced in C# 8. It allows for branching based on comparing a value (cell in the formatCell function) with multiple patterns. In the case of the formatCell function, the function evaluates to “X” when the cell value is HasX, “O” when it is HasO, and “_” when it is Empty. There is much more to pattern matching in F# than this, but this is the extent I will talk about it in this article.

Next is the writeBoard function:

The writeBoard function takes a board and writes it. Instead of writing it directly to the console, the writeBoard function takes another parameter called write that it will use when it wants to write a specific string. The caller of writeBoard can pass an argument for write that writes to the console, or to any other destination.

If you use IntelliSense to see the type of the write parameter, it looks like this:

This means that the write parameter is a function that takes a string and returns unit.

Unit is basically like void in C#. However, unlike void, unit is a real type.

Unit exists in many functional programming languages to make all functions return something – even if that something is nothing (pun intended)!

In C#, the type of the write parameter would be Action<string>. If C# had unit instead of void, then the type of this parameter in C# would be Func<string,unit> which would remove the need to have any Action delegates (like Action<T>) in the .NET frameworks.

Because the writeBoard function takes a parameter of type function, it is another example of a higher-order function.

Inside writeBoard, another function called writeRow is defined. This function takes a rowIndex, fetches the row from the board, and then writes it.

Functions defined inside functions have access to the parameters of the parent functions. They also have access to values (functions or otherwise) defined before themselves. For example, the writeRow function has access to (and uses) the board parameter of writeBoard.

Since version 7.0, C# has a similar feature called local functions.

After defining the writeRow function, the writeBoard function uses it to write the three rows of the board.

Next, I am defining the allLinesIndexes value:

This is a value, not a function. The value here is a sequence expression. Here is the type of this value:

This is a sequence. Each element of the sequence has the following type:

..which is a list, with each element in the list having the following type:

..which is a tuple containing two elements, each of type Index.

Here, I am trying to encode the 8 possible lines that a player can fill in the game in order to win. There are three horizontal lines, three vertical lines, and two diagonal lines.

I am encoding each line as a list of tuples (the list will contain three elements), each tuple contains the row and column indexes of the cell. For example, the following code:

..represents the following line in the board:

The yielded expression is a list containing three elements:

A semicolon is used to separate elements of a list. Square brackets are used to denote the list.

Each of the three elements in the list is a tuple. The comma is used to separate the two items in each tuple.

Let’s now look at the allLineValues function:

The allLineValues function takes a board and returns a seq<CellStatus list> representing the cell values for each of the eight different lines in the board.

Inside the body of the allLinesValues function, the cell function is defined. This function returns the status of a cell given its row and column indexes.

The allLineValues function returns the following expression:

The allLinesIndexes sequence (the 8 lines indexes) is given as the second argument to the Seq.map function. The Seq.map function is like the LINQ Select method in C#. The Seq.map function translates each line in allLinesIndexes to a list of CellStatus representing the status of cells in that line.

The first argument of Seq.map is a mapping function that will be used to transform each item in the source sequence. The mapping function passed to Seq.map is this function:

This is a lambda expression.

The lambda takes each line and then uses List.map to transform each cell in the line from a tuple of row and column indexes (Index * Index) to CellStatus. List.map is like Seq.map but for lists, not sequences.

In C#, we use the same Select method for all types of collections (e.g. List<T> or T[] or ImmutableArray<T>), but the result of the Select method is always IEnumerable<T>. In F# we can use specialized map methods to return a collection of the same input collection type. We can always use Seq.map for any kind of collection (like F# lists) if we want, but this will cause the resulting collection to be of type sequence.

The next function, lineIsFullOf, looks like this:

This function takes some line as a list of CellStatus, and a specific status value, and then checks whether all cells in the line contain that specific status. For example, we can use it to check if one of the diagonal lines is full of Os. At least, that was my intention when I wrote this function.

However, if we use IntelliSense to see the type of this function, it looks like this:

The type of the line parameter is ‘a list. And the type of the status parameter is ‘a.

And to remind you, ‘a is a generic type parameter.

There is also an interesting “(requires equality)” at the end.

If you think about it, there is nothing in the body of the lineIsFullOf function to indicate to the compiler that the line parameter is a list of CellStatus. There is only an indication (in the body) that line must be a list of something. And for this “something”, there is an indication that it must support equality, for the following expression to make sense:

That is, because in this lambda expression, we are checking equality between s and status, the type of s must support equality checking. Also, because we are checking equality between s and status, then status must have the same type as s.

If we are to manually write the types of the parameters and the equality constraint, the function would look like this:

Notice how we use angle brackets to specify type parameters along with any constraints (‘a :equality in this case).

F# tries hard to infer the types of parameters without us having to specify them manually.

Here is the last function in the BoardModule module:

I leave this one for you to figure out.

Can you guess what this function does? What Seq.exists does? Tweet your response at @yacoubmassad or leave a comment.

This was the last function in BoardModule. In the next part of this tutorial series, I will talk about the GameModule.

Conclusion:

F# is a .NET based functional-first programming language. In this article series, I continued exploring the language by using an example of the Tic Tac Toe game.

In this part, I demonstrated sequence expressions, lambda expressions, higher-order functions, match expressions, functions defined inside functions, F# lists and tuples, the map functions, type parameters and how the F# compiler tries hard to infer the types of parameters without us having to specify them.

This article was technically reviewed by Damir Arh.