Lecture 3 — Lists, patterns and polymorphism

Lecture 1 was a lightning tour of F#; lecture 2 made the core constructs precise with evaluation and typing rules. This week we add the one data structure that every functional program leans on, the list, and take a further look at functions, tuples and patterns. On the way we meet polymorphism for the first time, so that by the end of the day you are acquainted with a major part of the F# language.

Introduction

The purpose of the first part of this lecture is to give you an (as short as possible) introduction to lists, so that you can solve a problem which illustrates some of F#'s high-level features.

This part is not intended as a comprehensive presentation on lists: next week's lecture is about lists and the higher-order functions on them, and we return to the topic again later in the course.

Lists

A list is a finite sequence of elements having the same type:

\[[v_1;\ \ldots;\ v_n] \qquad\qquad ([\,]\ \text{is called the empty list})\]

The elements are separated by semicolons. Any type of element will do — numbers, strings, functions, tuples, or lists again:

let ints = [ 2; 3; 6 ]
let strings = [ "a"; "ab"; "abc"; "" ]
let pairs = [ (1, true); (3, true) ]
let nested = [ []; [ 1 ]; [ 1; 2 ] ]

[2; 3; 6]

["a"; "ab"; "abc"; ""]

[(1, true); (3, true)]

[[]; [1]; [1; 2]]

The type of a list is written with the element type first: int list, string list, (int * bool) list, int list list. A list of functions is a list too — F# Interactive shows the elements as closures:

> [sin; cos];;
val it: (float -> float) list = [<fun:it@1>; <fun:it@1-1>]

A side note on ;;. The double semicolon is used in interactive scripting: it tells F# Interactive that the expression is complete and may be evaluated. There is no need to write ;; in an .fsx file — and you will not find it in this script, only in the transcripts of interactive sessions such as the one above.

The constructors [] and ::

Lists are generated by two constructors:

• [] is a list — the empty list;
• if x is an element and xs is a list, then x :: xs is a list — a non-empty list. Read :: as "cons".

:: associates to the right: \(x_1\ \mathtt{::}\ x_2\ \mathtt{::}\ xs\) means \(x_1\ \mathtt{::}\ (x_2\ \mathtt{::}\ xs)\). The list is therefore a tree of constructor applications:

Head and tail

A non-empty list \([x_1;\ x_2;\ \ldots;\ x_n]\), \(n \geq 1\), consists of

• a head \(x_1\), and
• a tail \([x_2;\ \ldots;\ x_n]\).

The list literal [2; 3; 2] is just a convenient way of writing 2 :: 3 :: 2 :: [], and [2] is 2 :: []:

The tree shows how the value is built. It is also worth seeing how it is stored: each :: becomes a cons cell with two compartments — the head, and a reference to the tail — and the empty list ends the chain. This is the box-and-pointer picture of the same list [2; 3; 2]:

We come back to this memory picture in the lecture on tail recursion, where it explains why some list functions are cheap and others are not.

Recursion on lists — a simple example

Consider the sum of a list of integers:

\[\mathtt{suml}\ [x_1;\ x_2;\ \ldots;\ x_n] \;=\; \sum_{i=1}^{n} x_i \;=\; x_1 + x_2 + \cdots + x_n \;=\; x_1 + \sum_{i=2}^{n} x_i\]

The last form is a recipe: the sum of a non-empty list is its head plus the sum of its tail, and the sum of the empty list is \(0\). The constructors are used in list patterns to tell the two cases apart:

let rec suml xs =
    match xs with
    | [] -> 0
    | x :: xs' -> x + suml xs'

Type: suml : int list -> int. Evaluation follows the reduction rules from lecture 2 — each step matches the argument against the patterns and substitutes into the chosen branch:

suml [1; 2]
~> 1 + suml [2]          // x is 1 and xs' is [2]
~> 1 + (2 + suml [])     // x is 2 and xs' is []
~> 1 + (2 + 0)           // the pattern [] matches the value []
~> 1 + 2
~> 3

let sumExample = suml [ 1; 2 ]

3

Recursion follows the structure of lists. A list is either [] or x :: xs; a recursive function on lists has a case for each, and the recursive call is on the tail. You will write dozens of functions of this shape.

The rest of the lecture

With lists in hand, the rest of the lecture takes a further look at things you have already met:

• functions, including higher-order (curried) functions and partial application;
• basic types, including characters, equality and ordering;
• a first look at polymorphism;
• tuples and patterns;
• local declarations, type abbreviations and exceptions;
• and a small case study, rational numbers, that puts it all together.

Functions

From lecture 2. Anonymous functions fun x -> e, match, the equivalence let f x = e ≡ let f = fun x -> e, and currying — a function of two arguments is a function returning a function — were defined with their evaluation and typing rules in the lecture 2 notes. Here we use them.

Anonymous functions

An anonymous function may pattern-match on its argument directly:

let daysIn =
    fun x ->
        match x with
        | 2 -> 28 // February
        | 4 | 6 | 9 | 11 -> 30 // April, June, September, November
        | _ -> 31 // all other months

let daysInFebruary = daysIn 2

28

fun x -> match x with is so common that F# has a shorthand for it: the function keyword introduces an anonymous function whose body is a match on its (implicit) argument:

let daysInF =
    function
    | 2 -> 28 // February
    | 4 | 6 | 9 | 11 -> 30 // April, June, September, November
    | _ -> 31 // all other months

let daysInApril = daysInF 4

30

A simple function expression, given a name and applied:

let circleArea = fun r -> System.Math.PI * r * r
let circleAreaOf2 = circleArea 2.0

12.56637061

In F# Interactive the function expression alone is a value, and it names the last result, so you can apply it right away:

> fun r -> System.Math.PI * r * r;;
val it: r: float -> float

> it 2.0;;
val it: float = 12.56637061

Currying

\(\mathtt{fun}\ x\ y\ \cdots\ z \to e\) has the same meaning as \(\mathtt{fun}\ x \to (\mathtt{fun}\ y \to (\cdots (\mathtt{fun}\ z \to e)\cdots))\). The function below takes an integer and returns a function of type int -> int as its value — F# Interactive prints the type with the arrows, and applying the result to one argument gives a function:

> fun x y -> x + x*y;;
val it: x: int -> y: int -> int

> let f = it 2;;
val f: (int -> int)

> f 3;;
val it: int = 8

Functions are first-class citizens: the argument and the value of a function may themselves be functions.

Function declarations

A simple function declaration \(\mathtt{let}\ f\ x = e\) means \(\mathtt{let}\ f = \mathtt{fun}\ x \to e\). For example, let circleArea r = … is the declaration form of the fun above. In the same way a declaration of a curried function \(\mathtt{let}\ f\ x\ y\ \cdots\ z = e\) means \(\mathtt{let}\ f = \mathtt{fun}\ x \to (\mathtt{fun}\ y \to (\cdots(\mathtt{fun}\ z \to e)\cdots))\):

let addMult x y = x + x * y
let addMult2 = addMult 2
let addMultExample = addMult2 3

8

Type: addMult : int -> int -> int, and addMult2 : int -> int.

Partial application

Suppose that we have a cube with side length \(s\) containing a liquid with density \(\rho\). The weight of the liquid is \(\rho \cdot s^3\):

let weight rho s = rho * s ** 3.0

Type: weight : float -> float -> float. We can partially apply the function to define functions for computing the weight of a cube of either water or methanol:

let waterWeight = weight 1000.0
let methanolWeight = weight 786.5

let waterExample = waterWeight 2.0
let methanolExample = methanolWeight 2.0

8000.0

6292.0

Both have type float -> float. Nothing was recomputed or copied: waterWeight is weight with its first argument fixed.

Patterns

From lecture 2. A match expression evaluates its scrutinee and continues with the first branch whose pattern matches; matching yields bindings (lecture 2 notes).

We have exploited pattern matching in function expressions:

\[\mathtt{function}\ \ |\ pat_1 \to e_1\ \ \cdots\ \ |\ pat_n \to e_n\]

and a match expression has the same pattern-matching feature:

\[\mathtt{match}\ e\ \mathtt{with}\ \ |\ pat_1 \to e_1\ \ \cdots\ \ |\ pat_n \to e_n\]

The value of \(e\) is computed and the expression \(e_i\) corresponding to the first matching pattern is chosen for further evaluation. Here are three equivalent declarations of the power function \(x^n\) on floats — with function, with match on the pair, and with match on the exponent only:

let rec powerF =
    function
    | (_, 0) -> 1.0
    | (x, n) -> x * powerF (x, n - 1)

let rec powerM a =
    match a with
    | (_, 0) -> 1.0
    | (x, n) -> x * powerM (x, n - 1)

let rec power (x, n) =
    match n with
    | 0 -> 1.0
    | n' -> x * power (x, n' - 1)

let powerFExample = powerF (2.0, 3)
let powerMExample = powerM (2.0, 3)
let powerExample = power (2.0, 3)

8.0

8.0

8.0

All three have type float * int -> float. In F# Interactive you could declare each of them as power in turn — the newer declaration shadows the older one. In a script file compiled as a whole, a second top-level power is a duplicate definition error, which is why the three carry different names here.

Operators as functions

The prefix version \((\oplus)\) of an infix operator \(\oplus\) is a curried function:

> (+);;
val it: (int -> int -> int) = <fun:it@5-2>

Arguments can therefore be supplied one by one — (+) 3 is the function that adds three:

let plusThree = (+) 3
let plusThreeExample = plusThree 5

8

Function composition

Mathematically, \((f \circ g)(x) = f(g(x))\). For example, if \(f(y) = y + 3\) and \(g(x) = x^2\), then \((f \circ g)(z) = z^2 + 3\).

The infix operator << in F# denotes function composition:

let addThree y = y + 3 // f(y) = y + 3
let square x = x * x // g(x) = x * x
let h = addThree << square // h = f ∘ g

let hExample = h 4 // h(4) = (f ∘ g)(4) = 4² + 3

19

Using just anonymous functions:

let anonComposeExample = ((fun y -> y + 3) << (fun x -> x * x)) 4

19

What is the type of <<? It takes two functions and returns a function; the only constraint is that the result type of the second matches the argument type of the first. F# Interactive says:

> (<<);;
val it: (('a -> 'b) -> ('c -> 'a) -> 'c -> 'b)

Read it as: given f : 'a -> 'b and g : 'c -> 'a, the composition f << g has type 'c -> 'b. The letters 'a, 'b, 'c are type variables — we return to them in a moment.

Equality and ordering

The basic types — integers, floats, booleans and strings — were covered last week; characters follow below. For these types (and many others) equality and ordering are defined. In particular, there is a function compare with

\[\mathtt{compare}\ x\ y \;=\; \begin{cases} > 0 & \text{if } x > y \\ 0 & \text{if } x = y \\ < 0 & \text{if } x < y \end{cases}\]

For example:

let cmpFloat = compare 7.4 2.0
let cmpString = compare "abc" "def"
let cmpInt = compare 1 4

1

-3

-1

Only the sign of the result is specified — for strings the value is the difference between the first characters that differ.

Guards

It is often useful to have when guards in patterns. The first clause below is only taken when t > 0 evaluates to true:

let ordText x y =
    match compare x y with
    | t when t > 0 -> "greater"
    | 0 -> "equal"
    | _ -> "less"

let ordStrings = ordText "abc" "Abc"

"greater"

(Upper-case letters come before lower-case letters in the character ordering, so "abc" is greater than "Abc".)

Polymorphism and the comparison constraint

Look at the type F# infers for ordText:

> let ordText x y = ...;;
val ordText: x: 'a -> y: 'a -> string when 'a: comparison

It contains

• a type variable 'a, and
• a type constraint 'a : comparison.

The type variable can be instantiated to any type — provided comparison is defined for that type. Such a type is called a polymorphic type, and ordText works unchanged on booleans, on pairs, and on anything else that can be compared:

let ordBools = ordText true false
let ordPairs = ordText (1, true) (1, false)

"greater"

"greater"

Comparison is not defined for types involving functions, and the constraint makes the compiler reject the application rather than let it fail at run time:

> ordText sin cos;;

  ordText sin cos;;
  --------^^^
stdin(13,9): error FS0001: The type ''a -> 'a' does not support the 'comparison' constraint. For example, it does not support the 'System.IComparable' interface

Characters

Type name: char. Values are written between single quotes — the letter a is 'a', the space is ' ', and the quote character itself is written with a backslash escape.

let isLowerCaseVowel ch =
    System.Char.IsLower ch && (ch = 'a' || ch = 'e' || ch = 'i' || ch = 'o' || ch = 'u')

let vowelI = isLowerCaseVowel 'i'
let vowelUpperI = isLowerCaseVowel 'I'

true

false

Type: isLowerCaseVowel : char -> bool. The \(i\)-th character of a string is obtained by indexing:

let firstChar = "abc"[0]

'a'

Legacy note. Until F# 6 the indexing syntax was "abc".[0] — with a dot. You will meet it in older books and code, and it still compiles. Write s[i] in new code.

Overloaded operators and type annotations

The operators +, *, … are overloaded: they work on int, on float, and on other numeric types. When nothing else decides, F# defaults to int. The squaring function declared above, let square x = x * x, therefore has type int -> int:

> let square x = x * x;;
val square: x: int -> int

To get a squaring function on floats, square : float -> float, we add a type annotation. There are four places to put it — and you can mix them:

let squareArg (x: float) = x * x // type the argument
let squareRes x : float = x * x // type the result
let squareExpr x = (x * x: float) // type the expression for the result
let squareVar x = (x: float) * x // type a variable

let squareArgExample = squareArg 1.5
let squareResExample = squareRes 1.5
let squareExprExample = squareExpr 1.5
let squareVarExample = squareVar 1.5

2.25

2.25

2.25

2.25

All four have type float -> float: one annotation anywhere in the declaration is enough for type inference to fix the overload.

Tuples

From lecture 2. An ordered collection of \(n\) values \((v_1, v_2, \ldots, v_n)\) is an \(n\)-tuple; pairs have type t1 * t2, and tuples are evaluated left to right (lecture 2 notes).

What is new this week is how tuples compare. Equality is defined componentwise, ordering lexicographically — provided equality and ordering are defined on the components:

let tupleEq = (1, 2.0, true) = (2 - 1, 2.0 * 1.0, 1 < 2)
let tupleCmp = compare (1, 2.0, true) (2 - 1, 3.0, false)

true

-1

The comparison stops at the first component that differs: 1 = 2 - 1, then 2.0 < 3.0 decides, and the booleans are never looked at.

Tuple patterns

Patterns extract the components of tuples, and pattern matching yields bindings. Patterns nest, and _ skips a component:

let ((x, _), (_, y, _)) = ((1, true), ("a", "b", false))

1

"b"

Restriction: a variable may occur only once in a pattern. A pattern cannot say "two equal components":

> let (x,x) = (1,1);;

  let (x,x) = (1,1);;
  -------^
stdin(14,8): error FS0038: 'x' is bound twice in this pattern

(Use a guard — | (x, x2) when x = x2 -> … — if that is what you mean.)

Local declarations

From lecture 2. A let inside a function body is a local declaration, visible only until the end of that body (lecture 2 notes).

let g x =
    let a = 6
    let f y = y + a
    x + f x

let g1 = g 1

8

Type: g : int -> int. Note that a and f are not visible outside of g. Local declarations are how you name intermediate results — the next section shows why that matters.

Type abbreviations and exceptions

Example: solve \(a x^2 + b x + c = 0\). We first give names to the types involved, and declare an exception for the case where there is no real solution:

type Equation = float * float * float
type Solution = float * float

exception Solve // declares an exception

let solve (a, b, c) =
    if b * b - 4.0 * a * c < 0.0 || a = 0.0 then
        raise Solve
    else
        ((-b + sqrt (b * b - 4.0 * a * c)) / (2.0 * a),
         (-b - sqrt (b * b - 4.0 * a * c)) / (2.0 * a))

let solveExample = solve (1.0, -3.0, 2.0) // x² - 3x + 2 = (x - 1)(x - 2)

(2.0, 1.0)

The type of solve is float * float * float -> float * float, which is (the expansion of) Equation -> Solution. A type abbreviation introduces a new name, not a new type — Equation and float * float * float are interchangeable.

Applying solve to an equation without real roots raises the exception, which terminates the evaluation:

> solve (1.0, 0.0, 1.0);;
FSI_0022+Solve: Solve
   at FSI_0022.solve(Double a, Double b, Double c) in stdin:line 31
   ...
Stopped due to error

Solution using local declarations

In solve the discriminant b*b - 4.0*a*c is written three times. A local declaration computes it once — better for readability and for efficiency:

let solveD (a, b, c) =
    let d = b * b - 4.0 * a * c
    if d < 0.0 || a = 0.0 then
        raise Solve
    else
        ((-b + sqrt d) / (2.0 * a), (-b - sqrt d) / (2.0 * a))

let solveDExample = solveD (1.0, -3.0, 2.0)

(2.0, 1.0)

Local declarations nest. Here the square root of the discriminant is computed by a local block that also does the checking:

let solveSqrt (a, b, c) =
    let sqrtD =
        let d = b * b - 4.0 * a * c
        if d < 0.0 || a = 0.0 then raise Solve else sqrt d
    ((-b + sqrtD) / (2.0 * a), (-b - sqrtD) / (2.0 * a))

let solveSqrtExample = solveSqrt (1.0, -3.0, 2.0)

(2.0, 1.0)

Indentation matters: the extent of a local declaration is given by the layout of the code, so the inner let d belongs to sqrtD and the final tuple expression belongs to the function body.

Rational numbers

We close with a small case study that combines tuples, type abbreviations, exceptions, patterns, local declarations and operator declarations. Consider the following signature, specifying the operations on rational numbers and their types:

type qnum = int * int             rational numbers
exception QDiv                    division by zero
mkQ      : int * int  -> qnum     construction of rational numbers
.+.      : qnum * qnum -> qnum    addition
.-.      : qnum * qnum -> qnum    subtraction
.*.      : qnum * qnum -> qnum    multiplication
./.      : qnum * qnum -> qnum    division
.=.      : qnum * qnum -> bool    equality
toString : qnum -> string         string representation

Intended use

The operators are infix with the usual precedences — .*. and ./. bind tighter than .+. and .-., because an operator's precedence is determined by its leading character after the dots:

• let q1 = mkQ (2, 3) — \(q_1 = \frac{2}{3}\)
• let q2 = mkQ (12, -27) — \(q_2 = -\frac{12}{27} = -\frac{4}{9}\)
• let q3 = mkQ (-1, 4) .*. q2 .-. q1 — \(q_3 = -\frac14 \cdot q_2 - q_1 = -\frac59\)
• let q4 = q1 .-. q2 ./. q3 — \(q_4 = q_1 - q_2 / q_3 = \frac23 - \frac{-4}{9} \big/ \frac{-5}{9} = -\frac{2}{15}\)
• toString q4 — "-2/15"

Without infix notation the third line would read let q3 = (.-.) ((.*.) (mkQ (-1, 4)) q2) q1 — correct, and unreadable.

Representation

We represent a rational number by a pair \((a, b)\) with \(b > 0\) and \(\gcd(a, b) = 1\). For example, \(-\frac{12}{27}\) is represented by \((-4, 9)\). This is the representation invariant: every value of type qnum that our functions produce satisfies it, and every function may assume it of its arguments.

The greatest common divisor, by Euclid's algorithm:

type qnum = int * int

let rec gcd =
    function
    | (0, n) -> n
    | (m, n) -> gcd (n % m, m)

let gcdExample = gcd (12, 27)

3

Type: gcd : int * int -> int. A function to cancel common divisors and normalise the sign — it works on absolute values, so the remainder operator % only ever sees non-negative operands:

let canc (p, q) =
    let sign = if p * q < 0 then -1 else 1
    let ap = abs p
    let aq = abs q
    let d = gcd (ap, aq)
    (sign * (ap / d), aq / d)

let cancExample = canc (12, -27)

(-4, 9)

Program for rational numbers

The constructor rejects a zero denominator and establishes the invariant by cancelling:

exception QDiv

let mkQ =
    function
    | (_, 0) -> raise QDiv
    | pr -> canc pr

Rules of arithmetic:

\[\frac{a}{b} + \frac{c}{d} = \frac{ad + bc}{bd} \qquad \frac{a}{b} - \frac{c}{d} = \frac{ad - bc}{bd} \qquad \frac{a}{b} \cdot \frac{c}{d} = \frac{ac}{bd}\]

\[\frac{a}{b} \Big/ \frac{c}{d} = \frac{a}{b} \cdot \frac{d}{c}\ \ (c \neq 0) \qquad \frac{a}{b} = \frac{c}{d} \iff ad = bc\]

The program corresponds directly to these rules. An operator is declared like any other function, with the operator symbol in parentheses:

let (.+.) (a, b) (c, d) = canc (a * d + b * c, b * d)
let (.-.) (a, b) (c, d) = canc (a * d - b * c, b * d)
let (.*.) (a, b) (c, d) = canc (a * c, b * d)
let (./.) (a, b) (c, d) = (a, b) .*. mkQ (d, c)
let (.=.) (a, b) (c, d) = (a, b) = (c, d)

let toString ((a, b): qnum) = $"{a}/{b}"

Note how ./. delegates to mkQ, so that division by zero raises QDiv, and how .=. can simply compare the pairs: because both arguments satisfy the invariant, equal rationals have equal representations. Functions must preserve the invariant of the representation — every operator ends in canc. This is the first example in the course of a theme the syllabus insists on: state what a correct value looks like, and make every function keep it that way, so that incorrect values cannot be produced at all.

The intended use, evaluated:

let q1 = mkQ (2, 3)
let q2 = mkQ (12, -27)
let q3 = mkQ (-1, 4) .*. q2 .-. q1
let q4 = q1 .-. q2 ./. q3
let q4Text = toString q4

(2, 3)

(-4, 9)

(-5, 9)

(-2, 15)

"-2/15"

Pattern matching and recursion: unzip

Consider unzip that maps a list of pairs to a pair of lists:

\[\mathtt{unzip}\ [(x_0, y_0);\ (x_1, y_1);\ \ldots;\ (x_{n-1}, y_{n-1})] = ([x_0;\ x_1;\ \ldots;\ x_{n-1}],\ [y_0;\ y_1;\ \ldots;\ y_{n-1}])\]

with the declaration:

let rec unzip =
    function
    | [] -> ([], [])
    | (x, y) :: rest ->
        let (xs, ys) = unzip rest
        (x :: xs, y :: ys)

let unzipExample = unzip [ (1, "a"); (2, "b") ]

([1; 2], ["a"; "b"])

Notice:

• pattern matching on the result of the recursive call — the local let (xs, ys) = unzip rest takes the pair apart;

• unzip is polymorphic: nothing in it depends on the element types. Its type, as F# Interactive infers it, is

  val unzip: ('a * 'b) list -> 'a list * 'b list

• unzip is available in the List library as List.unzip — as are most of the functions you will write this week. Writing them yourself first is how you learn to read the library.

Summary

You are now acquainted with a major part of the F# language:

• lists, their constructors [] and ::, and recursion that follows the structure of lists;
• higher-order (curried) functions and partial application;
• operators as functions, and function composition with <<;
• basic types, equality and ordering with compare, and when guards;
• polymorphism and the comparison constraint;
• characters, and type annotations for overloaded operators;
• tuples, their ordering, and tuple patterns;
• local declarations, type abbreviations and exceptions;
• a representation invariant, and functions that preserve it.

Where next

Reading: Hansen & Rischel, chapter 3 (tuples and records — records come next week) and the beginning of chapter 4 (lists). Homework 2 is issued this week: operations on lists and tuples, recursion — exactly the shapes of function you met today. Next week: discriminated unions, lists, and the higher-order functions on lists.