Tic Tac Toe in F# – Part 2

Posted by: Yacoub Massad , on 5/16/2021, in Category C#
Views: 3776
Abstract: F# is a.NET based functional-first programming language. In the second part of the tutorial series, I will continue exploring the F# language, by using an example of the Tic Tac Toe game.

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:

let getRow index board =
    board.Rows |> Map.tryFind index |> Option.defaultValue emptyRow

The following expression:

board.Rows |> Map.tryFind index

..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:

let getCell rowIndex columnIndex board = 
    let row = getRow rowIndex board
    getCellInRow columnIndex row

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:

let allCellsInRow row =
    seq {
        yield getCellInRow One row
        yield getCellInRow Two row
        yield getCellInRow Three row
        }

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:

let allCells board =
    seq {
        yield! getRow One board |> allCellsInRow
        yield! getRow Two board |> allCellsInRow
        yield! getRow Three board |> allCellsInRow
        }

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:

public static IEnumerable<CellStatus> AllCells(Board board)
{
    foreach (var item in AllCellsInRow(GetRow(Index.One, board)))
        yield return item;

    foreach (var item in AllCellsInRow(GetRow(Index.Two, board)))
        yield return item;

    foreach (var item in AllCellsInRow(GetRow(Index.Three, board)))
        yield return item;
}

Here is the next function:

let updateCellInRow row index newStatus =
    {Cells = Map.add index newStatus row.Cells}

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:

let isFull board =
    board |> allCells |> Seq.forall (fun c -> c = HasX || c = HasO)

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:

let hasXOrO c = c = HasX || c = HasO

let isFull board =
    board |> allCells |> Seq.forall hasXOrO

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:

let formatCell cell =
    match cell with
    | HasX -> "X"
    | HasO -> "O"
    | Empty -> "_"

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:

let writeBoard board write =
    let writeRow rowIndex =
        let row = getRow rowIndex board
        getCellInRow One row |> formatCell |> write
        write " "
        getCellInRow Two row |> formatCell |> write
        write " "
        getCellInRow Three row |> formatCell |> write
    writeRow One
    write Environment.NewLine
    writeRow Two
    write Environment.NewLine
    writeRow Three
    write Environment.NewLine

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:

(string -> unit)

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:

let allLinesIndexes =
    seq {
            //Horizontal
            yield [One, One; One, Two; One, Three ]
            yield [Two, One; Two, Two; Two, Three ]
            yield [Three, One; Three, Two; Three, Three ]

            //Vertical
            yield [One, One; Two, One; Three, One ]
            yield [One, Two; Two, Two; Three, Two ]
            yield [One, Three; Two, Three; Three, Three ]

            //Diagonal
            yield [One, One; Two, Two; Three, Three ]
            yield [One, Three; Two, Two; Three, One ]
        }

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

seq<(Index * Index) list>

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

(Index * Index) list //this can also be written as list<(Index * Index)>

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

(Index * Index)

..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:

yield [One, One; One, Two; One, Three ]

..represents the following line in the board:

tictactoe-fsharp-example-first-horizontal line

The yielded expression is a list containing three elements:

One, One
One, Two
One, Three

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:

let allLineValues board =
    let cell rowIndex columnIndex = getCell rowIndex columnIndex board
    allLinesIndexes |> Seq.map (fun line -> line |> List.map (fun (r, c) -> cell r c))

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:

allLinesIndexes |> Seq.map (fun line -> line |> List.map (fun (r, c) -> cell r c))

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:

(fun line -> line |> List.map (fun (r, c) -> cell r c))

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:

let lineIsFullOf line status =
    line |> List.forall (fun s -> s = status)

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:

lines-full-of-intellisense

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:

(fun s -> s = status)

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:

let lineIsFullOf<'a when 'a :equality> (line: 'a list) (status : 'a)  =
    line |> List.forall (fun s -> s = status)

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:

let anyLineIsFullOf board status =
    board |> allLineValues |> Seq.exists (fun line -> lineIsFullOf line status)

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.

This article has been editorially reviewed by Suprotim Agarwal.

Absolutely Awesome Book on C# and .NET

C# and .NET have been around for a very long time, but their constant growth means there’s always more to learn.

We at DotNetCurry are very excited to announce The Absolutely Awesome Book on C# and .NET. This is a 500 pages concise technical eBook available in PDF, ePub (iPad), and Mobi (Kindle).

Organized around concepts, this Book aims to provide a concise, yet solid foundation in C# and .NET, covering C# 6.0, C# 7.0 and .NET Core, with chapters on the latest .NET Core 3.0, .NET Standard and C# 8.0 (final release) too. Use these concepts to deepen your existing knowledge of C# and .NET, to have a solid grasp of the latest in C# and .NET OR to crack your next .NET Interview.

Click here to Explore the Table of Contents or Download Sample Chapters!

What Others Are Reading!
Was this article worth reading? Share it with fellow developers too. Thanks!
Share on LinkedIn
Share on Google+

Author
Yacoub Massad is a software developer and works mainly on Microsoft technologies. Currently, he works at Zeva International where he uses C#, .NET, and other technologies to create eDiscovery solutions. He is interested in learning and writing about software design principles that aim at creating maintainable software. You can view his blog posts at criticalsoftwareblog.com. He is also the creator of DIVEX(https://divex.dev), a dependency injection tool that allows you to compose objects and functions in C# in a way that makes your code more maintainable. Recently he started a YouTube channel about Roslyn, the .NET compiler.



Page copy protected against web site content infringement 	by Copyscape




Feedback - Leave us some adulation, criticism and everything in between!

Categories

JOIN OUR COMMUNITY

POPULAR ARTICLES

Tags

JQUERY COOKBOOK

jQuery CookBook