Lists, patterns and polymorphism

ITT8060 Advanced Programming · Autumn 2026

Tallinn University of Technology

Full prose version with runnable examples: notes.html

ITT8060

Overview

  • Lists: values and constructors
  • Recursion following the structure of lists

The purpose: 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 a comprehensive presentation on lists — next week is about lists and higher-order functions, and we return to the topic again later.

ITT8060

Lists

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

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

Lists

A finite sequence of elements of the same type: \([v_1;\ \ldots;\ v_n]\), and [] is the empty list.

Types:
int list,
string list,
(int * bool) list,
int list list — and
(float -> float) list.

;; ends an expression in F# Interactive only. Never needed in an .fsx file.

ITT8060

The constructors [] and ::

  • [] is a list — the empty list
  • if x is an element and xs a list, x :: xs is a list

:: associates to the right:

\(x_1\ \mathtt{::}\ x_2\ \mathtt{::}\ xs\) means \(x_1\ \mathtt{::}\ (x_2\ \mathtt{::}\ xs)\)

ITT8060

Head and tail

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

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

[2; 3; 2] is 2 :: 3 :: 2 :: [], and [2] is 2 :: [].

ITT8060

How a list is stored

The tree shows how [2; 3; 2] is built.

In memory each :: is a cons cell: the head, and a reference to the tail. The empty list ends the chain.

Lecture 8 (tail recursion) builds on this picture.

ITT8060

Recursion on lists

a simple example

ITT8060

Summing a list

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

The sum of a non-empty list is its head plus the sum of its tail; the sum of [] is 0.

Constructors are used in list patterns.

ITT8060

Recursion follows the structure of lists

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

// val suml: xs: int list -> int

suml [1; 2]
~> 1 + suml [2]        // x is 1, xs' is [2]
~> 1 + (2 + suml [])   // x is 2, xs' is []
~> 1 + (2 + 0)         // [] matches []
~> 1 + 2
~> 3

A list is either [] or x :: xs. One case for each; the recursive call is on the tail.

ITT8060

Outline for the rest of the lecture

  • A further look at functions, including higher-order (curried) functions
  • A further look at basic types, including characters, equality and ordering
  • A first look at polymorphism
  • A further look at tuples and patterns
  • A further look at lists and list recursion

Goal: by the end of the day you are acquainted with a major part of the F# language.

ITT8060

Functions

ITT8060

From lecture 2

fun x -> e, match, and let f x = e ≡ let f = fun x -> e — with their evaluation and typing rules — are in the lecture 2 notes.

Currying: \(\mathtt{fun}\ x\ y\ \cdots\ z \to e\) means \(\mathtt{fun}\ x \to (\mathtt{fun}\ y \to (\cdots(\mathtt{fun}\ z \to e)\cdots))\)

Today: using them — pattern-matching functions, partial application, operators as functions, composition.

ITT8060

Anonymous functions with patterns

let daysIn =
    fun x ->
        match x with
        | 2 -> 28              // February
        | 4 | 6 | 9 | 11 -> 30 // Apr Jun Sep Nov
        | _ -> 31              // all others

let daysInF =
    function
    | 2 -> 28              // February
    | 4 | 6 | 9 | 11 -> 30 // Apr Jun Sep Nov
    | _ -> 31              // all others

function is shorthand for fun x -> match x with.

daysIn 2 → 28, daysInF 4 → 30.

ITT8060
let circleArea = fun r -> System.Math.PI * r * r
let circleAreaOf2 = circleArea 2.0
// val circleAreaOf2: float = 12.56637061

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

> it 2.0;;
val it: float = 12.56637061

Simple function expressions

A fun is a value — give it a name, or apply it directly.

In F# Interactive it names the last result.

ITT8060
> 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

Currying

The function takes an integer and returns a function of type int -> int as its value.

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

ITT8060

Function declarations

let circleArea r = System.Math.PI * r * r

// means

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

let addMult x y = x + x * y
// val addMult: x: int -> y: int -> int

let addMult2 = addMult 2
// val addMult2: (int -> int)

addMult2 3          // 8

\(\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))\)

ITT8060
let weight rho s = rho * s ** 3.0
// val weight: rho: float -> s: float -> float

let waterWeight = weight 1000.0
let methanolWeight = weight 786.5
// both: (float -> float)

waterWeight 2.0      // 8000.0
methanolWeight 2.0   // 6292.0

Partial application

A cube with side \(s\) containing a liquid of density \(\rho\) weighs \(\rho \cdot s^3\).

Partially apply weight to get the weight function for one particular liquid.

Nothing is recomputed: waterWeight is weight with its first argument fixed.

ITT8060

Patterns

ITT8060

Pattern matching in functions and in match

From lecture 2: the first matching pattern wins, and matching yields bindings (notes).

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

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

The value of \(e\) is computed and the \(e_i\) of the first matching pattern is evaluated.

ITT8060
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)

// all three: float * int -> float
// powerF (2.0, 3) = 8.0, likewise powerM, power

Three declarations of power

With function; with match on the pair; with match on the exponent only.

In fsi each could be called power — the new one shadows the old.

In a file, a second top-level power is a duplicate definition error.

ITT8060

Operators as functions

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

let plusThree = (+) 3
// val plusThree: (int -> int)

plusThree 5          // 8

Infix operators are curried functions

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

Arguments can be supplied one by one.

ITT8060
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
// val h: (int -> int)

h 4                        // 19

((fun y -> y + 3) << (fun x -> x * x)) 4   // 19

Function composition

\((f \circ g)(x) = f(g(x))\): with \(f(y) = y + 3\) and \(g(x) = x^2\), \((f \circ g)(z) = z^2 + 3\).

<< is F#'s composition operator.

Type of <<?

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

The type of <<

Given f : 'a -> 'b and g : 'c -> 'a, the composition f << g has type 'c -> 'b.

'a, 'b, 'c are type variables — more in a moment.

ITT8060

Basic types

equality and ordering

ITT8060
compare 7.4 2.0        // 1
compare "abc" "def"    // -3
compare 1 4            // -1

Equality and ordering

For the basic types — and many others — equality and ordering are defined.

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

Only the sign is specified.

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

ordText "abc" "Abc"    // "greater"

Pattern matching with guards

The first clause is only taken when t > 0 evaluates to true.

when guards: a pattern plus a condition.

ITT8060
val ordText: x: 'a -> y: 'a -> string
  when 'a: comparison

ordText true false          // "greater"
ordText (1, true) (1, false) // "greater"

Polymorphism and comparison

The type contains a type variable 'a and a type constraint 'a : comparison.

'a can be instantiated to any type — provided comparison is defined for it. A polymorphic type.

ITT8060
> 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

Comparison is not defined for functions

The constraint makes the compiler reject the application — rather than let it fail at run time.

ITT8060

Characters

and type annotations

ITT8060
let isLowerCaseVowel ch =
    System.Char.IsLower ch
    && (ch = 'a' || ch = 'e' || ch = 'i'
        || ch = 'o' || ch = 'u')
// val isLowerCaseVowel: ch: char -> bool

isLowerCaseVowel 'i'   // true
isLowerCaseVowel 'I'   // false

"abc"[0]               // 'a'

Characters

Type char; values 'a', ' ', '\''.

The \(i\)-th character of a string: s[i].

Legacy syntax s.[i] (before F# 6) still compiles; write s[i].

ITT8060
let square x = x * x        // int -> int, default

let squareArg (x: float) = x * x  // the argument
let squareRes x : float = x * x   // the result
let squareExpr x = (x * x: float) // expression
let squareVar x = (x: float) * x  // a variable
// all four: float -> float

Overloaded operators and type inference

* is overloaded; with nothing to decide, F# defaults to int.

One type annotation anywhere fixes the overload — and you can mix the four placements.

ITT8060

Tuples

ITT8060
(1, 2.0, true) = (2 - 1, 2.0 * 1.0, 1 < 2)
// true

compare (1, 2.0, true) (2 - 1, 3.0, false)
// -1

Tuples: equality and ordering

From lecture 2: an ordered collection of \(n\) values is an \(n\)-tuple (notes).

Equality componentwise, ordering lexicographically — provided they are defined on the components.

The comparison stops at the first component that differs.

ITT8060

Tuple patterns

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

// val x: int = 1
// val y: string = "b"

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

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

Pattern matching yields bindings; patterns nest, _ skips.

Restriction: a variable occurs at most once in a pattern.

ITT8060

Local declarations

type abbreviations, exceptions

ITT8060
let g x =
    let a = 6
    let f y = y + a
    x + f x
// val g: x: int -> int

g 1                    // 8

Local declarations

From lecture 2: a let inside a body is local to that body (notes).

a and f are not visible outside of g.

ITT8060
type Equation = float * float * float
type Solution = float * float
exception Solve

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))

solve (1.0, -3.0, 2.0)    // (2.0, 1.0)

Types and exceptions

Solve \(a x^2 + b x + c = 0\).

solve : Equation -> Solution — a type abbreviation is a new name, not a new type.

raise Solve when there is no real solution.

ITT8060

Solution using local declarations

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 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))

d declared once, used three times: readability, efficiency.

Indentation matters.

ITT8060

Example

rational numbers

ITT8060

A signature

type qnum = int * int             rational numbers
exception QDiv                    division by zero
mkQ      : int * int  -> qnum     construction
.+.      : 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

Operations and their types, before any code.

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

toString q4            // "-2/15"

// without infix notation:
let q3' = (.-.) ((.*.) (mkQ (-1, 4)) q2) q1

Intended use

  • \(q_1 = \frac23\)
  • \(q_2 = -\frac{12}{27} = -\frac49\)
  • \(q_3 = -\frac14 \cdot q_2 - q_1 = -\frac59\)
  • \(q_4 = q_1 - q_2 / q_3 = -\frac{2}{15}\)

Operators are infix with the usual precedences.

ITT8060
type qnum = int * int

let rec gcd = function
    | (0, n) -> n
    | (m, n) -> gcd (n % m, m)
// gcd (12, 27) = 3

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)
// canc (12, -27) = (-4, 9)

Representation

\((a, b)\) with \(b > 0\) and \(\gcd(a, b) = 1\) — the representation invariant. \(-\frac{12}{27}\) is represented by \((-4, 9)\).

gcd: Euclid's algorithm. canc: cancel common divisors, fix the sign.

ITT8060

Program for rational numbers

a/b + c/d = (ad + bc) / bd
a/b - c/d = (ad - bc) / bd
a/b * c/d = ac / bd
a/b / c/d = a/b * d/c        (c <> 0)
a/b = c/d  iff  ad = bc

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

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}"

The program corresponds directly to the rules.

Functions must preserve the invariant of the representation — every operator ends in canc.

ITT8060

Pattern matching and recursion

unzip

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

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

unzip

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

  • pattern matching on the result of the recursive call
  • unzip is polymorphic. Type?
  • List.unzip is in the library
ITT8060
val unzip: ('a * 'b) list -> 'a list * 'b list

The type of unzip

Nothing in the declaration depends on the element types — so they are type variables.

Most of the functions you write this week exist in List. Writing them yourself first is how you learn to read the library.

ITT8060

Summary

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

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

Next

Reading: Hansen & Rischel, chapter 3 and the beginning of chapter 4.

Homework 2 is issued this week: operations on lists and tuples, recursion.

Next week: discriminated unions, lists, higher-order functions on lists.

Full prose version with runnable examples: notes.html. The script is 03-lists-functions-tuples.fsx in course-materials.

ITT8060