F# Language Features - Part 1 (Tic Tac Toe Example)

Posted by: Yacoub Massad , on 2/22/2021, in Category C#
Views: 1888
Abstract: F# is a .NET based functional-first programming language. In this article series, we will explore the F# language by using the example of the Tic Tac Toe game.

Functional programming has been gaining popularity in the last few years.

C#, which is the most used language when targeting .NET, has been getting many functional language features. However, there is another language that targets .NET and is functional-first. This language is called F#.

F# is a multi-paradigm programming language. This means that you can, for example, write programs in an object-oriented style if you want. However, the focus in F# is on the functional style of programming.

Editorial Note: To explore some functional features in C#, check this tutorial Functional Programming (F#) for C# Developers.

In the Writing Pure Code in C# article, I used the Tic Tac Toe game as an example for writing pure code in C#. I will use the same example in this tutorial. However, please remember that the focus of this article is F#, not pure code.

If you are not familiar with the Tic-Tac-Toe game, please read about it here: https://en.wikipedia.org/wiki/Tic-tac-toe. Or spend a few minutes playing it online. You can find many versions online. If you want, you can play it using the example game I put on Github.

F# Example (Tic-Tac-Toe)

You can find the source code here: https://github.com/ymassad/TicTacToeFSharp. This should also help if you want to try everything yourself.

In this article series, although I will discuss the code in detail, the series is not structured as step-by-step tutorials. Still, I think you can manage to create the game yourself from scratch if you want. To get started with that, you need to create a new Console Application with the language set to F#.

Note that you need to make sure that you got F# installed. If not, you can add it to your Visual Studio installation using the Visual Studio Installer.

Once you create the new project, the program.fs file gets added automatically by Visual Studio. To add a new file, you can right click on the project -> Add -> New Item -> Source File.

The Board module in F#

In F#, it is idiomatic to separate data and behavior.

Therefore, I will define types to model the Board and then define functions to act on the board. I will define these types and functions in a new file called BoardModule.fs. If you create a new file with this name in the project, the file will contain the following by default:

module BoardModule

This code declares a module called BoardModule. Any types and functions we define after the above line will belong to the BoardModule module. Modules help us group related types and functions together.

I start by defining the CellStatus type like this:

type CellStatus = Empty | HasX | HasO

This code declares what is called in F# as a discriminated union. This is somewhat like Enums in C#.

However, F# discriminated unions are more advanced!!

I will show you a more advanced usage in another part of the series. For now, what we can understand from the line of code above is that we are declaring a CellStatus type to represent the status of a cell in the board. A cell can be empty, contain an X, or contain an O. Unlike Enums in C# where any integer value can be used, only valid values can be used in F# discriminated unions.

I define another discriminated union to model the index of a cell:

type Index = One | Two | Three

While we can use a normal integer to model the row or column index of a cell, using a discriminated union allows us to make invalid states unrepresentable and therefore make the application more robust.

I then define a record to model a single row in the board:

type Row = {Cells: Map<Index, CellStatus>}

The Row record has a single element labeled Cells. The type of this element is Map<Index, CellStatus>.

A Map is an immutable dictionary. In this case, the dictionary can contain a CellStatus for each possible Index (for each column index). Note that a Map does not necessarily have a value for each key. In the way I modeled the Row, I assume that if there is no value for a specific Index, then the value is CellStatus.Empty. More on this later.

Of course, you can create records with more than one element, I will show you an example in another part of this series.

I am also using a record to model the Board like this:

type Board = {Rows: Map<Index, Row>}

The Board record has a single element labeled Rows. It has a type of Map<Index,Row>. So, for each possible row index, we have a Row. Again, in the way I modeled this, when there is no value for a specific Index, I assume that we have an empty row. Next, I define emptyRow:

let emptyRow = {Cells = Map.empty}

The let keyword binds the value {Cells = Map.empty} to the name emptyRow. You can think of emptyRow as a variable. However, in F#, values are immutable by default. So, we cannot change the value bound to emptyRow after this line.

{Cells = Map.empty} is called a record expression. It is an expression that creates a record value. In this case, we are creating a Row record value. The compiler infers this because we are using the Cells label. We don’t have to specify that this is a Row record.

I use Map.empty here to create an empty Map<Index, CellStatus>.

Let us define the getRow function:

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

The getRow function takes two parameters: index and board (functions in F# actually take a single parameter. More on this later). This function returns the row at the specified index.

The index parameter is of type Index, and the board parameter is of type Board. I did not have to specify the types manually (although I can). The compiler inferred the types automatically. It was able to do so not because of the names of the parameters, but because of the usage of these parameters in the body.

The first hint to the compiler is the board.Rows expression. From this, the compiler infers that the board parameter must be of type Board because the Board record has the label Rows. It will become clear how the compiler inferred the type of the index parameter in about a minute.

Inside the getRow function, we define a value: possibleRow. You can think of this as a variable, but an immutable one.

Please note the indentation! In F#, indentation is significant.

The application might fail to compile if you use the wrong indentation. In the getRow function above, there are no curly brackets (like in C#) to tell us where this function begins and where it ends. The indentation has this job! If you remove the four spaces before “let possibleRow =..”, you will get a compilation error.

The following is the value bound to the possibleRow identifier:

Map.tryFind index board.Rows

This is a function call. The function name is tryFind and it lives in the Map module. We pass two arguments to the function: index and board.Rows. Note that unlike C#, we don’t need to use parentheses around the arguments.

This function attempts to find a value for the given index in the given Map. It’s return type is Option<T> where T is the type of the value. In this case, it is Option<Row>. In F#, this type is also expressed as “Row option”. This Option type is sometimes called Maybe in other programming languages/libraries. It represents a value that may or may not exist. You can read more about it here: https://www.dotnetcurry.com/patterns-practices/1510/maybe-monad-csharp

In the next line, we have this (also with indentation):

Option.defaultValue emptyRow possibleRow

This is also a function call. The function name is defaultValue and it lives in the Option module. This function returns the value inside possibleRow if there is a value inside it, or it returns emptyRow if there isn’t.

Note that there is no return keyword used here. In F#, functions don’t need to use the return keyword. F# treats the last expression in the function as the return value.

 

So basically, the getRow function returns the row specified by the index from the Map stored inside board.Rows. If there is no Row for the specified index, the getRow function returns an empty row.

If you look at the source code in GitHub, this is not how I define the getRow function. Here is how it is defined there:

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

The |> operator is called the forward pipe operator. It allows us to call the function on the right side of the operator using the value at the left side of the operator as an argument. This means that the following:

x |> f

Is similar to:

f x

Q. Both pass x as an argument to the function f. So why the extra syntax?

The pipe operator allows us to chain function calls as successive operations. This is what is happening in the body of the getRow function. We are passing board.Rows as an argument to the Map.tryFind function (passing also index as the first argument). Then, we are passing the return value of Map.tryFind as an argument to the Option.defaultValue function (passing also emptyRow as the first argument).

Without the forward pipe operator, we could define getRow like we did before, or we could also define it like this:

let getRow index board =
     Option.defaultValue emptyRow (Map.tryFind index board.Rows)

The parentheses used here are not the argument list parentheses that we are used to in C#. Here, the parentheses control the order of evaluation. This means that the Map.tryFind function is called first (using index and board.Rows as arguments), and then the result of that is passed as the second argument to the Option.defaultValue function.

Again, why the forward pipe operator? In the version where the forward pipe operator is used, the order of evaluation is from left to right, unlike the last version here where the evaluation is from right to left. Having function call evaluation be from left to right is more intuitive because functions appear in the same order that they will be evaluated in.

Let go back to the version that uses the forward pipe operator:

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

Let’s talk in detail about the following expression:

board.Rows |> Map.tryFind index

You can think of this expression as passing board.Rows as the second argument for the Map.tryFind function (and having index as the first argument). However, this is not exactly what is going on. Let’s dive deeper.

In this article, I hinted at two things which are:

  1. Functions in F# take exactly one parameter.
  2. The expression on the right side of the forward pipe operator is function.

Based on point #1, the Map.tryFind function should be taking a single parameter, not two. And that is really the case.

Let us look at what IntelliSense tells us about this function (when used in the context of the getRow function):

 

fsharp-function-intellisense

We can think of this function as one that takes both a key and a table (the dictionary or Map) parameter, and returns a possible value. This is one useful way to think about this function.

The other way to think about it is that this function takes only the key parameter and returns another function. Let me write a succinct version of the signature for tryFind here to explain:

tryFind: key -> table -> ‘T option

You can think of the -> symbol to mean returns.

So, the tryFind function takes a key parameter and returns the following:

table -> ‘T option

..which is another function that takes table (a dictionary) and returns ‘T option.

By the way, ‘ in F# is used to indicate that this is a generic type parameter. ‘T option means Option<’T>.

We say that the tryFind function is a curried function (after the mathematician Haskell Curry). This means that it is structured in a way that we call it one parameter at a time.

In C#, a curried tryFind function can be written like this:

public static class DictionaryFunctions<TKey, TValue>
{
    public static Func<TKey, Func<Dictionary<TKey, TValue>, Option<TValue>>> TryFind =
        key =>
        {
            return dictionary =>
            {
                if (dictionary.TryGetValue(key, out var value))
                {
                    return Option<TValue>.Some(value);
                }
                else
                {
                    return Option<TValue>.None;
                }
            };
        };
}

And can be called one parameter at a time like this:

var dictionary = new Dictionary<int, string>();

dictionary.Add(1, "asd");

var result1 = DictionaryFunctions<int, string>.TryFind(1)(dictionary);

var result2 = DictionaryFunctions<int, string>.TryFind(2)(dictionary);

Please take a minute to digest this.

Let us go back to the expression I want to discuss:

board.Rows |> Map.tryFind index

Earlier, I said that the expression on the right of the forward pipe operator should be a function. Now, it should be clear that this is true for the expression above. Map.tryFind index is a function. It is a function of type: (Map<Index, CellStatus>) -> CellStatus option. That is, it is a function that takes a Map (or dictionary) and possibly returns a CellStatus.

Calling a “multi-parameter” function with a single argument is called partial application. So, in the above expression (Map.tryFind index), we partially apply Map.tryFind using the argument index.

In general, when a function is designed in F#, the order of parameters is important. This is true because if you want to use the forward pipe operator, only the “last” argument of the function can be passed using the operator. We must partially apply the function by passing values for all but the last parameter. Only then we can use the forward pipe operator to pass the value for the last parameter, from the expression on the left of the operator.

This is a lot to digest, so I will stop here.

In the next part of our F# series, I will build on what we have discussed so far. I suggest you open the source code and try to play with the code to understand it.

Use IntelliSense to help you understand the type of values. You can take an expression in the middle of some code and bind it to a name by using the let operator and then use IntelliSense to understand the type of that expression. For example, you can bind the Map.tryFind index expression to a name like this:

let f1 = Map.tryFind index

…and then examine the type of f1 using IntelliSense. Just be careful with the indentation!

Conclusion:

F# is a .NET based functional-first programming language.

In this article series, I explored the F# language features by using the example of the Tic Tac Toe game.

In this part, I demonstrated simple discriminated unions, simple records, functions, and the forward pipe operator. I also talked about the concepts of currying and partial application.

In Part 2 of this article series, I will explore:

  • 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 Dobromir Nikolov.

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