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

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

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

type DifferentInt = DifferentInt of int

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

di2int (DifferentInt 17)       // 17

Values of DifferentInt are just ints with a label.

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.

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   // ::

Cons (1, Nil)                           // int PList

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 }
tõnu.age // 12
let tõnu2 = { Person.age = 12; name = "Tõnu" }
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 bad = { age = 12 };;
error FS0764: No assignment given for field
'name' of type 'Person'

The following are valid uses of append:

[1; 2] @ [3; 4]
// int list = [1; 2; 3; 4]

[[1]; [2; 3]] @ [[4]]
// int list list = [[1]; [2; 3]; [4]]

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

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

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

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

sumC     [ 1; 2;  3]   // 6
prodabsC [-2; 3; -4]   // 24

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

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

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.

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

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
rev [1; 2; 3]   // [3; 2; 1]

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

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

fold     (-) 0 [ 1; 2; 3 ]    // -6
foldBack (-) [ 1; 2; 3 ] 0    // 2

// ((0 - 1) - 2) - 3 = -6
// 1 - (2 - (3 - 0)) =  2

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'

exists (fun x -> x >= 2) [1; 3; 1; 4]   // true

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

forall (fun x -> x >= 2) [ 1; 3; 1; 4 ]   // false

Many recursive list functions follow the same pattern:

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

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)

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)

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

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