Getting Started With Fsharp

03 November 2017

An introduction followed by 15 lectures on the functional aspects of F#

(by Martin Elsman)

F# is a programming language aimed at executing programs on the .NET platform. We will explore how to develop F# programs that run under Mono, an open-source implementation of Microsoft’s Common Intermediate Runtime (CLR). We will see that it is perfectly possible, with certain restrictions, to develop portable programs and code that runs on a variety of platforms, including MacOS, Microsoft Windows, Linux, and, last but not least, a large variety of mobile platforms out there.

We will, essentially, be using a number of open-source tools. The most essential tool is the terminal program, which allows the developer to navigate around the file system and to execute commands, which includes compiling and executing F# programs.

Next, we will assume that the user has installed an editor on the machine. Whereas, many different editors exist, we will recommend gedit, which is available on all platforms (on MacOS, it may be installed using Homebrew; just type brew install gedit).

Finally, the user needs to install Mono, which, under MacOS, also can be installed using Homebrew; just type brew install mono in a terminal.

After having installed these tools, we are ready to run the fsharpi program in the terminal. In your terminal window, simply write

$ fsharpi

The fsharpi program will launch with a greeting and will be ready to receive commands:

F# Interactive for F# 4.1
Freely distributed under the Apache 2.0 Open Source License

For help type #help;;

>

Expressions and Types

The fsharpi program accepts commands as input, but it is also possible to type in an F# expression. Here is an example:

> 4+2*8;;
val it : int = 20

Notice that expressions and commands need to be terminated with ;; to indicate that fsharpi can start processing the input. After fsharpi receives the input, a number of things happen. First, the input is analysed and it is determined that the input corresponds to an expression that has type int. Then the expression is compiled into CIL bytecode, and finally, the bytecode is executed and the result, together with its type int, is printed in the feedback message val it : int = 20. Notice here the distinction between analysing and compiling the expression and the process of executing the generated bytecode, resulting in a final value; the expression is evaluated only if the expression can be given a type (in this case int). Finally, notice also that the resulting value is bound to a so-called variable it, which the user can refer to later if the result is needed for another computation:

> (it+3)*2;;
val it : int = 46

From the above interaction, we see that F# remembers the value of the variable it when calculating the value of the new expression, but we also see that the variable it is now replaced with a new binding, which associates the variable it with the value 46. We shall see later that a programmer can easily bind values to new variables and that the programmer may choose names for variables almost arbitrarily. Notice also that the programmer may use parentheses to overrule the usual precedence rules of mathematics. To exit the F# interpreter, type the command #q;;.

F# has support for a large number of built-in types, including integers (int), double-precision floats (float), strings (string), and booleans (bool). As we shall see later, it is also possible for the developer to declare his or her own types. F# also has a number of built-in operations on values of the various types; we have seen how the operation + operates on two integers, resulting in a new integer. The fact that + behaves like this can be specified by saying that + has the (function) type int -> int -> int. In short, we shall often use the following syntax to specify this property:

val (+) : int -> int -> int

Similarly, other operations on integers are available as well:

val (-) : int -> int -> int
val (/) : int -> int -> int
val abs : int -> int
val max : int -> int -> int
val min : int -> int -> int

Exercise 1: Play around with various expressions in the fsharpi program and evaluate the result of computing the number of minutes it takes for a train to run from Copenhagen to Aarhus given that it runs on average 120km/hour and that the distance between Copenhagen and Aarhus is 290km.

Of course, it is possible to program with values other than integers, as indicated by the fact that F# supports other types than int. For instance, F# supports programming with 64-bit double-precision floating-point values, which have type float:

> sin(4.9+float(2*8));;
val it : float = 0.8871575287

The value resulting from evaluating the expression is determined to have type float and, again, the result of evaluating the expression is bound to the variable it. We also see that it is possible to use the float(...) function to convert an integer value into a value of type float. However, we can also see that F# is somewhat rigid in this respect; it does not allow you to mix integers and floats in operations without you using the float function:

> 4.9+8;;
  4.9+8;;
  ----^

...(2,5): error FS0001: The type 'int' does not match the type 'float'

Exercise 2: The formula for calculating the body-mass-index for a person is identical to the weight of the person (in kilos) divided by the height (in meters) squared. Calculate the body mass index of a person of height 205cm and weight 89 kilos.

Variables

As mentioned, it is possible in F# for a programmer to bind a value to an identifier specified by the programmer. Such a binding is introduced with a so-called let construct:

> let myhousenumber = 24;;
val myhousenumber : int = 24
> let nexthousenumber = myhousenumber + 1;;
val nexthousenumber : int = 25
> let pi = 3.14;;
val pi : float = 3.14
> let height = sin pi;;
val height : float = 0.001592652916

As we can see, it is straightforward to create new bindings and to use the values associated to the introduced variables. In the above code, notice the use of the sine-function:

val sin : float -> float

Other functions (besides most of those available on integers) are available on floats as well. Such functions include cos, tan, exp, and so on.

Strings

Another essential data type available in F# is the string type:

> let hello = "Hello";;
val hello : string = "Hello"

> let mystring = hello + " World";;
val mystring : string = "Hello World"

Here we see that string constants are sequences of characters and that string constants are enclosed in double quotes (“). Moreover, the operator + is overloaded to also work for strings:

val (+) : string -> string -> string

The effect of “adding” to strings, which is also called catenation, is to create a new string that contains the argument strings put together in sequence. A number of other operations are available on strings, but to access most of them, it is required to access the, so-called, module containing string operations. Modules are referred to by name and, essentially (and for now), a module contains a number of variable bindings. The module containing string-operations is the module String and to access functionality within a module, we use the so-called dot-notation, which allows us, for instance, to get information about the length of a string:

> let mylen = String.length mystring;;
val mylen : int = 11

We see that the result of applying the String.length function to a concrete string is an integer, which we can also see by inspecting the function:

> String.length;;
val it : (string -> int) = <fun:it@24>

Whereas we can see the type of the function (it has type string -> int), we get no information about the function itself; that is, we cannot see its implementation.

Booleans and Conditional Expressions

The type bool represents the set of boolean values containing precisely the values true and false. Boolean values are, for instance, resulting from comparing values for equality and inequality:

> 2 < 3;;
val it : bool = true

> "hi" = "hello";;
val it : bool = false

Operations on booleans include boolean conjunction (&&) and boolean disjunction (||), which implements boolean “and” and boolean “or”, respectively. It is also possible to negate boolean values, using the function not:

val (&&) : bool -> bool -> bool
val (||) : bool -> bool -> bool
val not  : bool -> bool

Here is an example of a boolean expression:

> 2 < 3 && 5 >= 5;;
val it : bool = true

Notice that because the comparison operators (here < and >=) bind strong than &&, parentheses are not needed in this example.

Booleans may also be used for controlling program evaluation paths through the use of conditional expressions, also called if-then-else expressions:

let age = 17;;
val age : int = 17

> if age >= 18 then "you may drive a car" else "driving is not ok";;
val it : string = "driving is not ok"

Functions

We have already seen the use of some built-in functions, including functions for arithmetic (sine, addition, multiplication), for comparison testing, and for performing string operations.

In F#, it is straightforward to define your own functions built on top of previously defined functions or built in functions. In fact, the “F” in F# is really stands for the term functional.

Defining a function can be done by simply extending a let-expression to be parametric in an argument:

> let legal age =
    if age >= 18 then "you may drive a car"
    else "driving is not ok";;
val legal : age:int -> string

In this example, we define a function legal, which takes an integer as argument and produces a string as a result. This example is also the first example demonstrating that code may span several lines of text; once the first line is entered, fsharpi awaits further input and only when the ;; end-sequence appear will fsharpi attempt to make sense of the input. Once the function is defined, we can apply the function to different arguments and observe that the function behaves differently on different input:

> legal 14;;
val it : string = "driving is not ok"

> legal 28;;
val it : string = "you may drive a car"

Functions may take multiple parameters as input as exemplified in the following code that declares a function for determining the volume of a cylinder, given that the variable pi is bound already:

> let volume r h = h*pi*r*r;;
val volume : r:float -> h:float -> float

It is straightforward to call the function volume as can be seen in the following code:

> let vol1 = volume 1.0 10.0;;
val vol1 : float = 31.4

Exercise 3: Write a function bmi of type float -> float -> float that takes as input the weight and the height of a person and returns the body mass index for the person. You will probably need to apply a so-called type constraint to one of the function parameters in order not to have F# infer that the type of the function is int -> int -> int. The way to do this is to put parentheses around one of the arguments and specify that it should be of type float (as in (w:float)). When applying the bmi function to a weight of 83kg and a height of 2.05m, you should obtain a body mass index of approximately 19.75, which is considered slightly below normal.

Exercise 4: Using your newly defined function, create a new function bmi_msg that, as the bmi function takes a weight and a height as arguments, but now tests (using two conditional expressions) whether the person has a body mass index below or above normal. The result of the function should be a string telling the user if the body mass index is above normal, below normal, or within normal (a body mass index in the range 20-25 is considered normal). Test your function on various inputs.

Pairs and Tuples

It is often advantageous to think of a type as a set of values. In this way we can think of the type int as the set of all integers and the type bool as the set {true,false} containing the two possible boolean values. Understanding types as sets opens up the possibility for extending the universe of types. In this section, we shall consider product types. As an example, the product type of int and float, written int*float, is the type representing the set of pairs where the first component is an integer and the second component is a floating point value. In F#, pair values are simply constructed using a ,:

> let p = 34, 2.7;;
val p : int * float = (34, 2.7)

To access the components of a pair, we can use the functions fst and snd:

val fst : 'a * 'b -> 'a
val snd : 'a * 'b -> 'b

Here we see the first instance of so-called generic types, which are used in the types of the functions fst and snd to indicate that the functions can be applied to pairs of any type.

An important feature here is that the product type is just as good as any other type meaning that functions can be declared to take pairs as arguments and return pairs as results just as well as they can accept integers and return strings. As an example, here is a function that, given a radius value, returns a pair containing the circumference and the area of a circle:

> let circle_props r = (2.0*pi*r, pi*r*r);;
val circle_props : r:float -> float * float

Now that the function is declared, we can apply it to a particular radius and extract the area value:

> let area = snd(circle_props 5.0);;
val area : float = 78.5

Recursive Functions

Let us consider how we could write a function that adds up the numbers between 1 and 100. Clearly, we do not want to write up an expression 1+2+3+...+100. Even if this approach would work for summing up the values between 1 and 100, what if someone asked us to add up the numbers between 1 and 1000? Instead, we somehow need a way to repeat computations.

There are different kinds of programming languages that emphasize different programming paradigms. One paradigm is the imperative programming paradigm, which emphasizes the use of destructive updates, which, together with looping constructs, opens a possibility for arbitrary computing, which, for instance could be to sum up a range of numbers. Here we will follow another paradigm, which is the functional programming paradigm, a paradigm that celebrates immutability whenever possible and which features a number of reasoning principles that allow programmers to better specify and reason about properties of the program. An essential part of functional programming has to do with recursive functions, which are simply functions that call themselves.

Now consider again the task of writing a function that sums the integers between 0 and 100. Here is a recursive F# function that does the job for integers between 0 and a positive given argument n:

> let rec sum n = if n <= 0 then 0
                  else n + sum (n-1);;
val sum : n:int -> int

Notice the special keyword rec appearing after the let keyword. The rec keyword specifies that it is ok for the function to call itself inside the function’s own body. Now, let us look at the function in more detail. If the function is called with an argument of 0, clearly, the function will return 0 as a result, which we can easily check:

> sum 0;;
val it : int = 0

However, if the function is called with the argument 1, the immediate result is that the else-branch is taken. What this branch will do is to call sum recursively on n-1 and because n is 1, we have that sum is called with an argument of 0. After this call returns, 1 is added to the result of the call and the resulting value, which is 1, is returned.

Exercise 5: Write a recursive function called fac that takes an integer n as argument and computes the value 1*2*...*n. Test your function on a number of input values.

Exercise 6: Write a recursive function called power that takes two arguments, a float a and an integer n, and computes the value a^n. That is, it should compute the value 1.0*a*a*...*a, with n multiplications. Test your function on a number of input values. Notice that calling the function with the arguments 2.0 and 0 should result in the value 1.0 and calling the function with the arguments 3.0 and 4 should result in the value produced by the expression 1.0*3.0*3.0*3.0*3.0.

Working with Programs

Until now, we have only played around in the F# interpreter fsharpi. We shall now see how we can construct a self-contained program that, when executed, will run our F# code. To do so we will need to have our F# source program stored in a file somewhere on the machine. Using the terminal program, first create a directory mycode in your home directory on your machine:

$ cd ~
$ mkdir mycode
$ cd mycode

If you have not already installed gedit (or are using another text editor), now is the time to do so. The gedit program can be installed using Howebrew; just execute the command brew install gedit.

Once installed, open gedit from the terminal program:

$ gedit &

You can now type in your program in the gedit editor and save the program using the “Save As…” functionality in the menu. As an example, type in the following code in the editor, select F# as a language under “View->Highlight Mode…”, and save the file under the name sum.fs using the “Save As…” functionality:

let rec sum n = if n <= 0 then 0
                else n + sum (n-1);;

do printfn "%A" (sum 0)
do printfn "%A" (sum 10)

You are now ready to compile your first program using the F# compiler fsharpc. Again, from your terminal prompt, execute the following command:

$ fsharpc sum.fs

The command will generate a file called sum.exe, which can be executed using the mono program:

$ mono sum.exe
0
55

Notice the effects of the last two lines of the program. These lines print the results of evaluating the expressions sum 0 and sum 10 to the output. In each of the lines, the function printfn is evaluated to have an effect, which is to print a value to the program’s standard output. The function also prints the special new line character \n, which has the effect that the terminal program will show the two numbers on separate lines. The first argument to the printfn function is a so-called format string, which, in this case, specifies that the value should be printed using F#’s internal value formatter.

Reading Input Lines

We have seen how we can write a program that can write to the standard output, but we have not seen how we can get a program to read input from a user (or another program). Luckily, F# features a function for doing just this. The function is called System.Console.ReadLine and its type is unit -> string, where unit is a built-in type containing only one value, namely ().

We can now write a program, say sumN.fs, that asks the user to type an integer n and prints the value sum n:

let rec sum n = if n <= 0 then 0
                else n + sum (n-1);;

do printfn "Input a number, please:"
let n : string = System.Console.ReadLine()

do printfn "Sum(0..%s) = %A" n (sum (int(n)))

Notice the use of the : string type annotation in the let-binding for n; this annotation allows us to express our intention that n should contain a string. If we, for instance, had forgotten to give System.Console.ReadLine the unit` value as argument, the F# compiler would complain.

Here is the result of compiling the program and executing it with the number 11 as input:

$ fsharpc --nologo sumN.fs
$ mono sumN.exe
Input a number, please:
11
Sum(0..11) = 66

Exercise 7: Use the body mass index calculation function bmi_msg from Exercise 4 and combine it with code that reads the user’s weight and height from the terminal input and reports a message on the terminal output as a result.

Imperative Programming with Mutable Variables

We shall now see how we can use so-called mutable variables for storing values that change during the evaluation of a program. Whereas recursion is often better for encoding repetition, we shall also introduce the concepts of while-loops and for-loops.

Here is a program, called multableN.fs that outputs a multiplication table on the terminal output:

do printfn "Enter an integer:"
let x = System.Console.ReadLine()
do printfn "Table:"
let mutable i = 1
while i <= 10 do
  printfn "%A" (i*(int(x)))
  i <- i + 1

When the program executes, the body of the while-loop, which consists of the two indented lines of code, is executed 10 times and within the body, the variable i takes on different values for each iteration, caused by the statement i <- i + 1. Here is an example interaction with the program:

$ fsharpc --nologo multableN.fs
$ mono multableN.exe
bash-3.2$ mono multableN.exe
Enter an integer:
3
Table:
3
6
9
12
15
18
21
24
27
30

Exercise 8: Write a program christmas that reads an integer n and prints out a Christmas tree of height n. The program may use the function printf to print a string without printing a newline character. Here is what the program should output when the number 3 is given as input:

$ mono christmas.exe
Enter an integer:
3
   *
  ***
 *****

More F# Topics

Programming in F#, and functional programming in general, has much more to it than what we have seen here. In the referenced material below, we cover a number of topics, including programming with lists and arrays, recursion in depth, type-full programming with records and discriminated unions, and, finally, the topic of higher-order functional programming (to come). All of the examples given in the slides can be compiled and executed under Mono (you need to copy the code from the slides, though). Some of the examples utilize the ImgUtil library, which is comprised by an img_util.fsi file (an interface file) and the implementation file img_util.fs. For details about how to compile and use the library, please consult the README file.

Please be aware that the slides are all in danish; they have been developed as part of the introductory programming course for the Computer Science BSc degree at the Department of Computer Science, University of Copenhagen.

Programming with Lists. We introduce the reader to list programming and demonstrate how a programmer may use the built-in list functions to construct larger functions.
Programming with Lists (continued) and Arrays. We continue with the introduction of list programming and demonstrate also how programmers may use arrays of different dimensions to solve various tasks.
Recursion. We illustrate the concept of recursion by introducing a number of basic functions on integers and lists.
Recursion and Sorting. We illustrate recursive programming through the definition of a number of sorting routines over lists of integers. The sorting routines include bubble sort, insertion sort, selection sort, merge sort and quick sort.
Recursion, Games, and Drawing. We demonstrate how we can implement functionality (rules) that allow for a human to play the “Towers of Hanoi” game in the F# shell. We then present the Hanoi algorithm, which allows the computer to play (and win) the game for any number of pegs, by applying a recursive algorithm. We also show how we can use recursion to draw simple fractals on a canvas using the ImgUtil library.
Types and Pattern Matching. We present the concept of types in more details and show how F# allows the programmer to declare, even generic, type abbreviations and how a programmer may use the concept of pattern-matching to, for instance, define functions over lists.
Discriminated Unions and a Turtle EDSL. We present the concept of discriminated unions and show how a programmer may implement a small Turtle EDSL (Embedded Domain Specific Language), which allows for specifying simple turtle movements and drawings. We show how the recursive features of a host language (in this case F#) can be used to generate instructions for drawing complex fractals. We also demonstrate how the drawings can be effectuated by writing an interpreter for the turtle EDSL that converts instructions into bitmap lines, which can be shown on a canvas.
Stacks, Queues, and Recursion Revisited. We give a solution to the classical maximum segment sum problem, using recursion. We also define interfaces for stacks and queues and provide efficient implementations of both.
Search Trees and Catenable Strings. We look at different tree structures and provide definitions of trees that are good for binary searching and definition of trees that are good for implementing catenable strings, that is, strings that can be catenated in O(1) time.
Tree Traversals. We classify a number of different ways to traverse (binary) trees, including depth-first tree traversals (preorder, postorder, and inorder) and breath-first traversal, and provide F# implementations of them all.
Expression Trees and Symbolic Differentiation. We show how we can define the concept of expression trees (of one variable) in F# using a simple, recursively defined, discriminated union type. We demonstrate how we can generate LaTeX code for such expressions and how we can completely define, using high-school math rules, how such expressions are differentiated. An expression simplifier makes for prettier printing of results.
Higher-Order Functions. We revisit the definition of functions in F# and give a proper foundation in terms of the notion of closures. We give examples of how higher-order functions allow for functions to receive functions as parameters and how functions can also be returned as the result of calling a function. We define the notions of currying and partial applications, and we give an extensive example of how functions can be used to define so-called functional images.
Exceptions. We introduce the concept of exceptions and present the difference between exception values and the concept of raising an exception. We describe how exceptions can be handled at different levels in a program and give an alternative model for programming with errors based on Yoda’s statement that “there is no try; either you do or you don’t”.
Input and Output. In this lecture, we describe how F# programs may interact with the console (e.g., the terminal) through command-line arguments and by reading from stdin and by writing to stdout and stderr. We also demonstrate how programs may read and write to files and how we can perform HTTP requests to servers on the internet asking for web-page content. As an example, we demonstrate how we can apply the concept of regular expressions to extract the FX rate from a web-site and use it in an F# application.
Parsing with Higher-Order Functions. We present the concepts of lexing and parsing and demonstrate how we can make use of the concept of higher-order functions to define the notion of parser combinators. We demonstrate how the parser combinators can be used to define parsers for expression trees and turtle-graphics commands that each will convert strings of characters to manageable F# data structures.

License

Getting Started with FSharp by Martin Elsman is licensed under a Creative Commons Attribution-NoDerivatives 4.0 International License.

lessons 3