Lecture 4 — Discriminated unions, lists and higher-order functions

Recall the match expression

match e with
| p_1 [ when c_1 ] -> e_1
| ...
| p_n [ when c_n ] -> e_n

Match e against the patterns from top to bottom. If p_i matches, evaluate the guard c_i (missing guard = when true). If c_i is true, then e_i is the result of the whole match. Otherwise continue with the next pattern. At most one e_i gets evaluated. The type of the match is the type of the e_i.

An example with "holes"

let rec foo (xs: int list) (n: int) : int =
  let y = ?1
  match xs with
  | []               -> ?2
  | x :: xs' when ?3 -> ?4
  | _                -> ?5

What are the "holes", and what can we fill them with? Two questions: the type the "hole" must have, and the names in scope there.

Part I: Discriminated unions

Motivation

We want a list of all addresses of a contact. An address can be:

type PhysAddr = string * string * string
type VirtAddr = string * string

let a1 : PhysAddr = "Ehitajate tee", "5", "Tallinn"
let a2 : VirtAddr = "juulius", "ttu.ee"

But a1 :: a2 :: [] does not type-check:

> a1 :: a2 :: [];;

  a1 :: a2 :: [];;
  ------^^
stdin(5,7): error FS0001: Type mismatch. Expecting a tuple of length 3 of type
    PhysAddr
but given a tuple of length 2 of type
    VirtAddr

Goal: a type in which we can combine the two address types. Informally:

type Address = PhysAddr + VirtAddr

The + is not valid F#. This is informal notation for the disjoint union of the values of the two types: a value of type Address is either a physical or a virtual address, not both.

Defining and constructing

A discriminated union is a type with distinct cases — the discriminating part. The general scheme:

type type_name =
  | case_identifier_1 of type_1_1 [ * type_1_2 ...]
  ...
  | case_identifier_n of type_n_1 [ * type_n_2 ...]

A concrete example, combining string * string, int and int:

type StringsOrInts =
  | Strings of string * string
  | Left of int
  | Right of int

A case identifier constructs a value of the type. Strings ("ab", "cd"), Left 17 and Right 17 all have type StringsOrInts:

let soi1 : StringsOrInts = Strings ("ab", "cd")
let soi2 : StringsOrInts = Left 17
let soi3 : StringsOrInts = Right 17

Strings 17 does not type-check:

> Strings 17;;

  Strings 17;;
  --------^^
stdin(8,9): error FS0001: This expression was expected to have type
    'string * string'
but here has type
    'int'

Left 17 <> Right 17 is true:

let leftNeRight = Left 17 <> Right 17

true

Deconstructing

A value soi : StringsOrInts had to be constructed by one of the constructors. To use the value, we must say what to do in each case: for Strings (s1, s2), for Left n and for Right n.

let foo (soi: StringsOrInts) : bool =
  match soi with
  | Strings (s1, s2) -> s1 = s2
  | Left n when n < 0 -> true
  | Left n -> n % 2 = 0
  | Right _ -> true

Case identifiers are patterns, and a case identifier only matches itself. The compiler tries to check that all possible cases are handled.

What is foo (Strings ("ab", "ab"))?

let fooStrings = foo (Strings ("ab", "ab"))

true

What is foo (Left (-3))?

let fooNeg = foo (Left (-3))

true

What is foo (Left 4)?

let fooEven = foo (Left 4)

true

What is foo (Right 17)?

let fooRight = foo (Right 17)

true

Leave out the Right case and the compiler tells you which value is not covered:

> let foo2 (soi: StringsOrInts) : bool =
    match soi with
    | Strings (s1, s2) -> s1 = s2
    | Left n -> n % 2 = 0;;

    match soi with
  --------^^^
stdin(9,9): warning FS0025: Incomplete pattern matches on this expression. For example,
the value 'Right (_)' may indicate a case not covered by the pattern(s).

Enumerations as discriminated unions

> type Colour = Red of unit
              | Green of unit
              | Blue of unit;;
type Colour =
  | Red of unit
  | Green of unit
  | Blue of unit

> let r : Colour = Red ();;
val r: Colour = Red ()

Recall that () is the only value of type unit. A constructor without an argument type is syntactic sugar for of unit.

type Colour = Red | Green | Blue
let b : Colour = Blue

let show (c: Colour) : string =
  match c with
  | Red -> "red"
  | Green -> "green"
  | Blue -> "blue"

let showB = show b

"blue"

A single constructor

type DifferentInt = DifferentInt of int

let di2int (di: DifferentInt) : int =
  match di with
  | DifferentInt n -> n

let di17 = di2int (DifferentInt 17)

17

Values of DifferentInt are just ints with a label.

type Meter = M of float
type Kilogram = Kg of float
type Second = S of float

Useful because the three types are different. let kg : Kilogram = S 1.0 does not typecheck:

> let kg : Kilogram = S 1.0;;

  let kg : Kilogram = S 1.0;;
  --------------------^^^^^
stdin(3,21): error FS0001: This expression was expected to have type
    'Kilogram'
but here has type
    'Second'

See also: units of measure.

Recursive discriminated unions

A constructor's argument types may refer to the type being defined (no rec needed).

type IntList = INil
             | ICons of int * IntList

let il1: IntList = INil
let il2: IntList = ICons (1, INil)
let il3: IntList = ICons (1, ICons (2, ICons (3, INil)))

Note the IntList argument to ICons, and no arguments to INil.

To use a value of a recursive DU we may need to use recursion.

let rec sumIntList (il: IntList) : int =
  match il with
  | INil -> 0
  | ICons (n, il') -> n + sumIntList il'

let sumIl3 = sumIntList il3

6

Standard lists

We draw the values ICons (1, ICons (2, ICons (3, INil))) and 1 :: 2 :: 3 :: [] as trees (of constructor applications). They represent the same thing.

The built-in list type is a recursive discriminated union with constructors [] and ::.

Parameterised discriminated unions

type StringList = SNil
                | SCons of string * StringList

StringList differs from IntList only in the type of the first Cons argument. We abstract it out as a type parameter.

type 'a PList = Nil                     // []
              | Cons of 'a * 'a PList   // ::

let onePList = Cons (1, Nil)            // int PList

Cons (1, Nil)

This is how lists are defined in F#.

PList itself is not a type; int PList is. PList is a function on types:

> let x : PList = Cons (1, Nil);;

  let x : PList = Cons (1, Nil);;
  --------^^^^^
stdin(17,9): error FS0033: The type 'PList<_>' expects 1 type argument(s) but is given 0

The type parameter can also be given in angle brackets: PList<int>.

let onePList' : PList<int> = Cons (1, Nil)

The option type

Intuitively, take an existing type and add an additional value to it, None. Used extensively in the standard library to represent the lack of a value of type 'a.

// in the standard library:
// type 'a option = None | Some of 'a

let noInt: int option = None
let anInt: int option = Some 11

In Java, the class Integer has as values all int values plus null. Every reference type has null as a value. With option we can be more precise.

Different point of view: 'a option is the type of lists of length ≤ 1. (How?)

let noInts = Option.toList noInt
let anInts = Option.toList anInt

[]

[11]

Example: indexOf

Find the index of the first occurrence of el in xs.

let rec indexOf (el : 'a) (xs : 'a list) : int option =
  match xs with
  | []       -> None
  | x :: xs' ->
    if x = el then
      Some 0
    else
      match indexOf el xs' with
      | None   -> None
      | Some i -> Some (i + 1)

let idxHit = indexOf 3 [5; 3; 8]
let idxMiss = indexOf 7 [5; 3; 8]

Some 1

None

Why return int option? What should the index of the first occurrence be when el is not in xs?

When xs is empty, then we know the result. Otherwise, el is the head, or, it is somewhere in the tail and we match on the result of the recursive call.

Why return Some (i + 1)?

A first look at records (the rest next week)

Records: aggregates of named values

type type_name = { label_1: type_1; ...; label_n: type_n }

Think of it as a tuple with named fields. Records are immutable: with copies a record with some updated fields.

type Person = { name: string; age: int }
let tõnu = { name = "Tõnu"; age = 12 }

Field access with a dot: the value of tõnu.age is

let tõnuAge = tõnu.age

12

Copy-and-update with with: mari is a copy of tõnu with the name field replaced, that is, the record

let mari = { tõnu with name = "Mari" }

{ name = "Mari"
  age = 12 }

Every field must be supplied when constructing a value; order is free; a label may be qualified with the type name.

let tõnu2 = { Person.age = 12; name = "Tõnu" }

> let bad = { age = 12 };;

  let bad = { age = 12 };;
  ----------^^^^^^^^^^^^
stdin(26,11): error FS0764: No assignment given for field 'name' of type 'Person'

tõnu2 is the same value as tõnu:

let sameTõnu = tõnu = tõnu2

true

More records

Record literals can be used as patterns.

let describe (p: Person) : string =
  match p with
  | { name = ""; age = _ } -> "empty string"
  | { name = n; age = a } ->
    $"Name is {n} and age is {a}"

let describeEmpty = describe { name = ""; age = 40 }
let describeMari = describe mari

"empty string"

"Name is Mari and age is 12"

Records can be recursive and parameterised. Every NotList has a tail that is again a NotList (which has a head element).

type 'a NotList = { head: 'a; tail: 'a NotList }

let rec x = { head = 1
              tail = { head = 2; tail = x } }

let x1 = x.head
let x2 = x.tail.head
let x3 = x.tail.tail.head

1

2

1

Not allowed for lists (but allowed with our PList):

> let rec xs = 1 :: 2 :: xs;;

  let rec xs = 1 :: 2 :: xs;;
  ------------------^^^^^^^
stdin(33,19): error FS0260: Recursive values cannot appear directly as a construction
of the type 'List`1' within a recursive binding. This feature has been removed from
the F# language. Consider using a record instead.

Part II: Lists

• Generating lists using range expressions
• Example functions on lists: append, reverse, isMember
• Typical recursion patterns on lists

Range expressions

A simple range expression \([b\ \mathtt{..}\ e]\), where \(e \geq b\), generates the list \([b;\ b+1;\ \ldots;\ b+n]\) where \(b + n \leq e < b + n + 1\). Empty when \(e < b\).

let rangeUp = [ -3 .. 5 ]
let rangeEmpty = [ 7 .. 4 ]

[-3; -2; -1; 0; 1; 2; 3; 4; 5]

[]

With specified step: \([b\ \mathtt{..}\ s\ \mathtt{..}\ e] = [b;\ b+s;\ \ldots;\ b+ns]\). The list is ascending if \(s > 0\) and descending if \(s < 0\).

let rangeDown = [ 6 .. -1 .. 2 ]
let rangeStep = [ 2 ..  2 .. 6 ]

[6; 5; 4; 3; 2]

[2; 4; 6]

Range expressions with floats

let rangePi = [ 0.0 .. System.Math.PI / 2.0 .. 2.0 * System.Math.PI ]

[0.0; 1.570796327; 3.141592654; 4.71238898; 6.283185307]

let rangeFloat = [ 2.4 .. 3.0 ** 1.7 ]
let upper = 3.0 ** 1.7

[2.4; 3.4; 4.4; 5.4; 6.4]

6.47300784

Beware of precision loss when summing floats:

let tenTenths = List.sum [ for _ in 1 .. 10 -> 0.1 ]
let tenTenthsIsOne = tenTenths = 1.0
let tenTenthsError = tenTenths - 1.0

false

-1.110223025e-16

Simple recursion on lists

Three simple functions — append, reverse, isMember — whose declarations follow the structure of the list argument:

let rec f ... xs ... =
  match xs with
  | []       -> v
  | x :: xs' -> ... f xs' ...

What is the structure of 1 :: 2 :: 3 :: 4 :: 5 :: []?

let xs = 1 :: (2 :: (3 :: (4 :: (5 :: []))))

List.head xs = 1
List.tail xs = 2 :: (3 :: (4 :: (5 :: [])))

The tail of a nonempty list is a recursive substructure.

Append

The infix operator @ joins two lists: \([x_1;\ldots;x_m]\ \mathtt{@}\ [y_1;\ldots;y_n] = [x_1;\ldots;x_m;\ y_1;\ldots;y_n]\)

Properties:

• \([\,]\ \mathtt{@}\ ys = ys\)
• \([x_1;\ \ldots;\ x_m]\ \mathtt{@}\ ys = x_1\ \mathtt{::}\ ([x_2;\ \ldots;\ x_m]\ \mathtt{@}\ ys)\)

let rec append xs ys =
  match xs with
  | [] -> ys
  | x :: xs' -> x :: append xs' ys

let appended = append [1; 2] [3; 4]

[1; 2; 3; 4]

(@) : 'a list -> 'a list -> 'a list is available in the standard library.

Append: evaluation

append [1; 2] [3; 4]
~> 1 :: (append [2] [3; 4])
~> 1 :: (2 :: (append [] [3; 4]))
~> 1 :: (2 :: [3; 4])
~> 1 :: [2; 3; 4]
~> [1; 2; 3; 4]

ys is never taken apart. Execution time is linear in the size of the first list. Be careful with usage like: xs @ [x].

Append: polymorphic type

The following are valid uses of append:

let intsAppended = [1; 2] @ [3; 4]
let listsAppended = [[1]; [2; 3]] @ [[4]]

[1; 2; 3; 4]

[[1]; [2; 3]; [4]]

This is because @ is polymorphic in the type of elements of the list.

val (@): 'a list -> 'a list -> 'a list

The 'a is the type parameter. For 'a = int, we have (@) : int list -> int list -> int list. For 'a = int list, we have (@) : int list list -> int list list -> int list list.

Reverse

let rec naiveRev lst =
  match lst with
  | [] -> []
  | x :: xs -> naiveRev xs @ [x]

// val naiveRev: 'a list -> 'a list

let reversed = naiveRev [1; 2; 3]

[3; 2; 1]

naiveRev [1; 2; 3]
~> naiveRev [2; 3] @ [1]
~> (naiveRev [3] @ [2]) @ [1]
~> ((naiveRev [] @ [3]) @ [2]) @ [1]
~> (([] @ [3]) @ [2]) @ [1]
~> ([3] @ [2]) @ [1]
~> ...
~> [3; 2; 1]

\(\mathtt{naiveRev}\ [x_1;\ x_2;\ \ldots;\ x_n] = [x_n;\ \ldots;\ x_2;\ x_1]\).

naiveRev performs an @ for every element in the list. Recall that @ is linear in the first argument. Therefore, naiveRev is \(O(n^2)\) time.

Built-in List.rev is \(O(n)\). See fold in Part III for another linear implementation.

List membership

\(\mathtt{isMember}\ x\ [y_1;\ \ldots;\ y_n] = (x = y_1) \lor \mathtt{isMember}\ x\ [y_2;\ \ldots;\ y_n]\)

let rec isMember x lst =
  match lst with
  | [] -> false
  | y :: ys -> x = y || isMember x ys

let memberPair = isMember (1, true) [(2, true); (1, false)]
let memberList = isMember [1; 2; 3] [[1]; []; [1; 2; 3]]

false

true

'a must satisfy equality: values of such types can be compared with =. Tuples and lists of comparable things are fine as equality is derived componentwise. Function types are not.

val isMember: x: 'a -> lst: 'a list -> bool when 'a: equality

> isMember sin [cos];;

  isMember sin [cos];;
  ---------^^^
stdin(44,10): error FS0001: The type ''a -> 'a' does not support the 'equality'
constraint because it is a function type

Match on results of the recursive call

let rec f ... xs ... =
  ...
  let pat(y) = f xs
  e(y)

Recall unzip from last week (lecture 3 notes): let (xs, ys) = unzip rest.

Two more examples: sumProd and split.

Example: sumProd

\(\mathtt{sumProd}\ [x_0;\ \ldots;\ x_{n-1}] = (x_0 + \cdots + x_{n-1},\ x_0 \cdots x_{n-1})\)

Recursion formula: \(\mathtt{sumProd}\ [x_0;\ \ldots;\ x_{n-1}] = (x_0 + \mathit{rSum},\ x_0 \cdot \mathit{rProd})\) where \((\mathit{rSum}, \mathit{rProd}) = \mathtt{sumProd}\ [x_1;\ \ldots;\ x_{n-1}]\).

Base case \((0, 1)\): the neutral elements.

let rec sumProd lst =
  match lst with
  | [] -> (0, 1)
  | x :: rest -> let (rSum, rProd) = sumProd rest
                 (x + rSum, x * rProd)
// val sumProd: int list -> int * int

let sumProd25 = sumProd [2; 5]

(7, 10)

Example: split

\(\mathtt{split}\ [x_0;\ x_1;\ x_2;\ x_3;\ \ldots] = ([x_0;\ x_2;\ \ldots],\ [x_1;\ x_3;\ \ldots])\)

let rec split lst =
  match lst with
  | [] -> ([], [])
  | [x] -> ([ x ], [])
  | x :: y :: xs -> let (xs1, xs2) = split xs
                    (x :: xs1, y :: xs2)

let split7 = split [1 .. 7]

([1; 3; 5; 7], [2; 4; 6])

Notice a convenient division into three cases, and the recursion formula \(\mathtt{split}\ [x_0;\ x_1;\ x_2;\ \ldots] = (x_0\ \mathtt{::}\ \mathit{xs1},\ x_1\ \mathtt{::}\ \mathit{xs2})\) where \((\mathit{xs1}, \mathit{xs2}) = \mathtt{split}\ [x_2;\ \ldots]\).

Part III: Higher-order list functions

Higher-order functions

Functions that accept a function as an argument or return a function as a result.

They are everywhere: \(\sum_{i=a}^{b} f(i),\quad \frac{df}{dx},\quad \{x \in A \mid P(x)\},\ \ldots\)

They are expressive and useful.

Now down to earth

Many recursive declarations follow the same schema:

let rec f xs =
  match xs with
  | []       -> ...
  | x :: xs' -> ... (f xs') ...

• Goal: avoid repeating (almost) identical code fragments
• Solution: capture frequently occurring patterns as higher-order functions
• Result: more succinct and reusable declarations

Today: map, filter, fold, foldBack, exists, forall, tryFind. All of these are available in the List module; we try to define each one of them.

Two simple list functions

let rec add n xs =
  match xs with
  | []       -> []
  | x :: xs' -> n + x :: add n xs'

// add: int -> int list -> int list

let added = add 5 [-2; -1; 0; 1; 2]

[3; 4; 5; 6; 7]

let rec flip xs =
  match xs with
  | []       -> []
  | x :: xs' -> -1 * x :: flip xs'

// flip: int list -> int list

let flipped = flip [-2; -1; 0; 1; 2]

[2; 1; 0; -1; -2]

The only difference: what happens to the elements (n + x vs -1 * x). The lists are processed in exactly the same way.

How to represent what happens to an element in the list? With a function of type int -> int: fun x -> n + x vs fun x -> -1 * x.

The map pattern

Take the element function int -> int as a parameter.

let rec mapInts (f: int -> int) (xs: int list) : int list =
  match xs with
  | []       -> []
  | x :: xs' -> f x :: mapInts f xs'

let addM n xs = mapInts (fun x -> n  + x) xs
let flipM  xs = mapInts (fun x -> -1 * x) xs

let addedM = addM 5 [-2; -1; 0; 1; 2]
let flippedM = flipM [-2; -1; 0; 1; 2]

[3; 4; 5; 6; 7]

[2; 1; 0; -1; -2]

Nothing in mapInts is specific to int. If we drop the annotations, then the inferred type is the most general type for map.

let rec map f xs =
  match xs with
  | []       -> []
  | x :: xs' -> f x :: map f xs'

// val map: f: ('a -> 'b) -> xs: 'a list -> 'b list

More examples

map : ('a -> 'b) -> 'a list -> 'b list applies the same transformation to every element: \(\mathtt{map}\ f\ [v_1;\ \ldots;\ v_n] = [f\ v_1;\ \ldots;\ f\ v_n]\)

The transformation may transform the type of the element which is why there are two type parameters.

let arePositive xs = map (fun x      -> x > 0) xs   // int         list -> bool list
let addFstSnd  xys = map (fun (x, y) -> x + y) xys  // (int * int) list -> int  list

let positives = arePositive [-1; 0; 1]
let sums = addFstSnd [(-1, 2); (1, 3); (2, 4)]

[false; false; true]

[1; 4; 6]

Another point of view: given f : 'a -> 'b construct 'a list -> 'b list:

map : ('a -> 'b) -> ('a list -> 'b list)

Exercise

Declare a function \(\mathtt{g}\ [x_1;\ \ldots;\ x_n] = [x_1^2 + 1;\ \ldots;\ x_n^2 + 1]\).

Remember \(\mathtt{map}\ f\ [v_1;\ \ldots;\ v_n] = [f\ v_1;\ \ldots;\ f\ v_n]\).

There is also a map for option types. What does it do?

Option.map : ('a -> 'b) -> 'a option -> 'b option

let optSome = Option.map (fun x -> x + 1) (Some 2)
let optNone = Option.map (fun x -> x + 1) None

Some 3

None

Something similar to map

List.map : ('a -> 'b) -> ('a list -> 'b list)

map constructs a function 'a list -> 'b list from 'a -> 'b.

List.collect : ('a -> 'b list) -> ('a list -> 'b list)

List.collect constructs a function of the same type from a function that transforms an element into a list. What does it do?

let collected = List.collect (fun x -> [0; x]) [1 .. 5]

[0; 1; 0; 2; 0; 3; 0; 4; 0; 5]

Filtering

Set comprehension: \(\{x \in xs : p(x)\}\)

filter p xs is the sublist of those elements x in xs for which p x = true. Library function: List.filter.

let rec filter p xs =
  match xs with
  | [] -> []
  | x :: xs' -> if p x
                then x :: filter p xs'
                else filter p xs'

// val filter: ('a -> bool) -> 'a list -> 'a list

let letters = filter System.Char.IsLetter [ '2'; 'p'; 'F'; '-' ]

['p'; 'F']

System.Char.IsLetter c is true iff c is a letter.

Combining a list into one value

let rec sum (xs: int list) : int =
  match xs with
  | []       -> 0
  | x :: xs' -> x + sum xs'

let sum123 = sum [1; 2; 3]

6

let rec prodabs (xs: int list) : int =
  match xs with
  | []       -> 1
  | x :: xs' -> abs x * prodabs xs'

let prodabs234 = prodabs [-2; 3; -4]

24

The two functions are very similar. Differences: base value (0 vs 1), and how to combine the element x with the recursive result (let's call it r).

What do the following functions represent?

• fun x r -> x + r
• fun x r -> abs x * r

A first generalisation

Abstract out the concrete details: the base value b, and the function f combining an element x with a partial result r become parameters.

let rec combineInts (f: int -> int -> int) (xs: int list) (b: int) : int =
  match xs with
  | []       -> b
  | x :: xs' -> f x (combineInts f xs' b)

let sumC     xs = combineInts (fun x r -> x     + r) xs 0
let prodabsC xs = combineInts (fun x r -> abs x * r) xs 1

let sumC123 = sumC [ 1; 2;  3]
let prodabsC234 = prodabsC [-2; 3; -4]

6

24

Here we have sum and prodabs defined without (explicit) rec.

Again, nothing in the body of combineInts is specific to integers. No reason to restrict this list recursion pattern to int list via type annotations.

Folding a list from the right ("backwards")

let rec foldBack (f: 'a -> 'b -> 'b) (xs: 'a list) (b: 'b) : 'b =
  match xs with
  | []       -> b
  | x :: xs' -> f x (foldBack f xs' b)

let sumB     xs = foldBack (fun x r -> x     + r) xs 0
let prodabsB xs = foldBack (fun x r -> abs x * r) xs 1

let sumB123 = sumB [1; 2; 3]
let prodabsB234 = prodabsB [-2; 3; -4]

6

24

sumB [1; 2; 3]
= foldBack (+) [1; 2; 3] 0
~> 1 + (foldBack (+) [2; 3] 0)
~> 1 + (2 + (foldBack (+) [3] 0))
~> 1 + (2 + (3 + (foldBack (+) [] 0)))
~> 1 + (2 + (3 + 0))
~> 6

We fold back (from the right): the base value "goes" to the right of the list and we move from right to left.

foldBack

For an infix \(\otimes\): \(\mathtt{foldBack}\ (\otimes)\ [a_0;\ \ldots;\ a_{n-1}]\ e = a_0 \otimes (a_1 \otimes (\cdots (a_{n-1} \otimes e)))\)

Many functions can be defined via foldBack (including append and map from today).

let conj xs = foldBack (&&) xs true
let conjFT = conj [true; false; true]

false

let appendB xs ys = foldBack (fun x r -> x :: r) xs ys
let appendedB = appendB [1; 2] [3; 4]

[1; 2; 3; 4]

let lengthB xs = foldBack (fun _ r -> 1 + r) xs 0
let lengthABC = lengthB ['a'; 'b'; 'c']

3

let mapB f xs = foldBack (fun x r -> f x :: r) xs []
let mappedB = mapB abs [-1; 2; -3]

[1; 2; 3]

A map via foldBack, evaluated

let fn = fun x r -> abs x :: r

mapB abs [-1; 2; -3]
=  foldBack fn [-1; 2; -3] []
~> abs -1 :: foldBack fn [2; -3] []
~> abs -1 :: abs 2 :: foldBack fn [-3] []
~> abs -1 :: abs 2 :: abs -3 :: foldBack fn [] []
~> abs -1 :: abs 2 :: abs -3 :: []
~> 1      :: 2     :: 3      :: []

Each element is combined with the recursive result (folded tail) using the function fn. As fn applies the function abs to the element and cons-es it in front of the recursive result, we have map.

Folding from the left

let rec fold (f: 'b -> 'a -> 'b) (r: 'b) (xs: 'a list) : 'b =
  match xs with
  | []       -> r
  | x :: xs' -> fold f (f r x) xs'

let rev xs = fold (fun rs x -> x :: rs) [] xs
let rev123 = rev [1; 2; 3]

[3; 2; 1]

The accumulated result r is a parameter. We "update" the accumulated result with every recursive call.

Using cons (::) with fold gives a linear time list reverse. How? One cons per element, no append.

rev [1; 2; 3]
=  fold fn []                  [1; 2; 3]
~> fold fn (1 :: [])           [2; 3]
~> fold fn (2 :: 1 :: [])      [3]
~> fold fn (3 :: 2 :: 1 :: []) []
~> 3 :: 2 :: 1 :: []

foldBack versus fold

\(\mathtt{foldBack}\ (\otimes)\ [a_0;\ a_1;\ a_2]\ e\) — note how the tree leans to the right. Why? What does this mean?

\(\mathtt{fold}\ (\oplus)\ e\ [a_0;\ a_1;\ a_2]\) — note how the tree leans to the left. Why?

Comparing the two

There are functions for which fold and foldBack give different results. For example, (-).

let foldMinus = fold (-) 0 [ 1; 2; 3 ]        // ((0 - 1) - 2) - 3
let foldBackMinus = foldBack (-) [ 1; 2; 3 ] 0  // 1 - (2 - (3 - 0))

-6

2

With cons: one reverses, the other copies. Why?

let foldCons = fold (fun r x -> x :: r) [] [1; 2; 3; 4; 5]
let foldBackCons = foldBack (fun x r -> x :: r) [1; 2; 3; 4; 5] []

[5; 4; 3; 2; 1]

[1; 2; 3; 4; 5]

What properties must be satisfied so that fold f b xs = foldBack f xs b?

exists

Here is the function exists : ('a -> bool) -> 'a list -> bool that checks (decides) whether there exists an element in the list that satisfies the predicate. In other words, exists p xs = true precisely when there is some x in xs such that p x = true.

let rec exists p xs =
  match xs with
  | []       -> false
  | x :: xs' -> p x || exists p xs'

let existsGe2 = exists (fun x -> x >= 2) [1; 3; 1; 4]

true

Note that || is lazy (short-circuiting). What does that mean for exists? The predicate is not applied to the elements after the first hit — here 10 / 0 is never evaluated:

let existsLazy = exists (fun x -> 10 / x > 1) [5; 0]

true

Exercise: define exists as a fold. Compare its behaviour to the given (direct) definition.

Exercise

Define the function isMember (that decides list membership) in terms of exists.

let isMember x ys = exists ??? ???
val isMember: 'a -> 'a list -> bool when 'a: equality

Remember: exists p xs = true precisely when there is some x in xs such that p x = true.

forall

Here is the function forall : ('a -> bool) -> 'a list -> bool that checks (decides) whether every element in the list satisfies the predicate. In other words, forall p xs = true precisely when for every x in xs we have p x = true.

let rec forall p xs =
  match xs with
  | [] -> true
  | x :: xs' -> p x && forall p xs'
// val forall: ('a -> bool) -> 'a list -> bool

let forallGe2 = forall (fun x -> x >= 2) [ 1; 3; 1; 4 ]

false

Note that (&&) is also lazy. What does that mean for the definition of forall? Again 10 / 0 is never evaluated:

let forallLazy = forall (fun x -> 10 / x > 1) [20; 0]

false

Why is it that the base case ([]) of exists is false and forall is true?

let existsEmpty = exists (fun x -> x >= 2) []
let forallEmpty = forall (fun x -> x >= 2) []

false

true

Exercise: define forall as a fold. Compare it to the given definition.

Exercises

Define the function disjoint : 'a list -> 'a list -> bool so that disjoint xs ys is true when there are no common elements in xs and ys, and false otherwise.

Define the function subset : 'a list -> 'a list -> bool so that subset xs ys is true when every element of xs is also an element of ys, and false otherwise.

Define the function inter : 'a list -> 'a list -> 'a list so that x is an element of inter xs ys precisely when x is an element of both xs and ys.

Note that inter produces a list. How should the elements be ordered? Are duplicates allowed?

When appropriate, try to use the functions defined earlier.

tryFind

Given a predicate p, find an element x from a list xs such that p x = true.

let rec tryFind p xs =
  match xs with
  | []                -> None
  | x :: xs' when p x -> Some x
  | _ :: xs'          -> tryFind p xs'
// val tryFind: ('a -> bool) -> 'a list -> 'a option

let found = tryFind (fun x -> x > 3) [ 1; 5; -2; 8 ]
let notFound = tryFind (fun x -> x > 10) [ 1; 5; -2; 8 ]

Some 5

None

The result type is 'a option. Why? When is the result None and when is it Some x?

Exercise: union of sets

We represent a set as a list with unique elements (without duplicates).

Uniqueness is an invariant that the operations must preserve: if xs and ys are sets (lists without duplicates) and f is a set-operation, then f xs ys must also be a set (list without duplicates).

Define the set-operation insert : 'a -> 'a list -> 'a list that corresponds to the following operation on sets: \(x \cup X\). In other words, insert x xs should represent the set \(x \cup X\) where \(X\) is represented by the list xs.

What should be the result when x is already in xs? Does the order of elements matter?

Define the set-operation union : 'a list -> 'a list -> 'a list.

Summary

Many recursive list functions follow the same pattern:

let rec f xs =
  match xs with
  | []       -> ...
  | x :: xs' -> ... (f xs') ...

Higher-order functions allow us to represent/capture such repeating patterns and thus avoid repetition.

Use well-known patterns to communicate your intent. (Similar: why do we prefer for-loops to explicit use of goto?)

Question

We know map : ('a -> 'b) -> 'a list -> 'b list. With 'a = int and 'b = int its type is (int -> int) -> int list -> int list.

Not every function of type (int -> int) -> int list -> int list can be defined as map f xs where f : int -> int and xs : int list.

Is this good or bad?

Next

Reading (mandatory): Hansen & Rischel, chapter 3 (tagged values and records), chapter 4, and the beginning of chapter 5 (lists).

Homework 3 is issued this week.

Appendix I: Some algebraic laws for higher-order functions

Where we assume that functions are pure.

map

Mapping the identity function is the same as doing nothing:

map id = id

Mapping twice (composition of mappings) is the same as mapping once with the composition of the functions:

map f << map g = map (f << g)

Example:

let f x = x + 1
let g x = 2 * x

let mapIdLhs = (map id) [1; 2; 3]
let mapIdRhs = id [1; 2; 3]

[1; 2; 3]

[1; 2; 3]

let mapTwice = (map f << map g) [1; 2; 3]
let mapOnce = (map (f << g)) [1; 2; 3]

[3; 5; 7]

[3; 5; 7]

The second mapping does not compute the intermediate list map g [1; 2; 3].

filter

Define conjunction of predicates 'a -> bool as:

let (.&&.) p q x = p x && q x   // if p x then q x else false

Filtering twice is the same as filtering once with the combined predicate:

filter p << filter q = filter (p .&&. q)

Example:

let p x = x > 0
let q x = x % 2 = 0

let filterTwice = (filter p << filter q) [-2 .. 2]
let filterOnce = (filter (p .&&. q)) [-2 .. 2]

[2]

[2]

The second filtering does not compute the intermediate list filter q [-2 .. 2].

map and foldBack

Swap arguments:

let swap f x y = f y x

foldBack after map is a single foldBack:

swap (foldBack f) b << map g = swap (foldBack (f << g)) b

Example, with double x = 2 * x standing for the operator section on the slide:

let double x = 2 * x

let foldAfterMap = (swap (foldBack (+)) 0 << map double) [1; 2; 3]
let foldMapped = (swap (foldBack ((+) << double)) 0) [1; 2; 3]

12

12

Unfolding the definitions of << and swap removes swap from both sides:

(f << g) x = f (g x)
swap f x y = f y x

(swap (foldBack (+)) 0 << map double) [1; 2; 3]
= swap (foldBack (+)) 0 (map double [1; 2; 3])    // definition of <<
= foldBack (+) (map double [1; 2; 3]) 0           // definition of swap

(swap (foldBack ((+) << double)) 0) [1; 2; 3]
= foldBack ((+) << double) [1; 2; 3] 0            // definition of swap

So the law says foldBack f (map g xs) b = foldBack (f << g) xs b.

The second one does not compute the intermediate list produced by map; it directly folds the list [1; 2; 3].

filter and foldBack

Define guarded combine function (combine x and r using f only when p holds):

let guard p f x r = if p x then f x r else r

foldBack after filter is a guarded foldBack:

swap (foldBack f) b << filter p = swap (foldBack (guard p f)) b

Example:

let foldAfterFilter = (swap (foldBack (+)) 0 << filter ((>=) 3)) [1 .. 5]
let foldGuarded = (swap (foldBack (guard ((>=) 3) (+))) 0) [1 .. 5]

6

6

Again unfolding << and swap:

(swap (foldBack (+)) 0 << filter ((>=) 3)) [1 .. 5]
= swap (foldBack (+)) 0 (filter ((>=) 3) [1 .. 5])    // definition of <<
= foldBack (+) (filter ((>=) 3) [1 .. 5]) 0           // definition of swap

(swap (foldBack (guard ((>=) 3) (+))) 0) [1 .. 5]
= foldBack (guard ((>=) 3) (+)) [1 .. 5] 0            // definition of swap

So the law says foldBack f (filter p xs) b = foldBack (guard p f) xs b.

The second one does not compute the intermediate list filter ((>=) 3) [1 .. 5]; it directly folds the list [1 .. 5].

Appendix II: shapes as a disjoint union

A shape is either a circle, a square or a triangle — the union of three disjoint sets. The tags Circle, Square and Triangle are constructors.

type Shape =
  | Circle of float
  | Square of float
  | Triangle of float * float * float

let shape1 = Circle 2.0                     // Shape
let shape2 = Triangle (1.0, 2.0, 3.0)       // Shape
let shape3 = Square 4.0                     // Shape

A shape-area function, declared following the structure of shapes.

let area s =
  match s with
  | Circle r -> System.Math.PI * r * r
  | Square a -> a * a
  | Triangle (a, b, c) ->
    let s = (a + b + c) / 2.0
    sqrt (s * (s - a) * (s - b) * (s - c))

// val area: s: Shape -> float

let areaCircle = area (Circle 1.2)

4.523893421

A constructor only matches itself; matching binds the carried values:

area (Circle 1.2)
~> System.Math.PI * r * r   // r ↦ 1.2
~> ...