Types

Type List

Implemented as a linked list:

• 1 list = 1 element (Head) + 1 sub-list (Tail)

• Construction using :: Cons operator

To avoid infinite recursion, we need an "exit" case: → Empty list named Empty and noted []

👉 Generic and recursive union type:

type List<'T> =
  | ( [] )
  | ( :: ) of head: 'T * tail: List<'T>

☝️ Note: this syntax with cases as operator is only allowed in FSharp.Core.

Type alias

• List (big L) refers to the F♯ type or its companion module.

• list (small l) is an alias of F♯'s List type, often used with OCaml notation: → let l : string list = ...

⚠️ Warnings:

• ❗ After open System.Collections.Generic:

  • List is the C♯ mutable list, hiding the F♯ type!

  • The List F♯ companion module remains available → confusion!

• 💡 Use the ResizeArray alias to reference the C♯ list directly

  • no need for open System.Collections.Generic 👍

Immutability

A List is immutable: → It is not possible to modify an existing list.

Adding an element in the list: = Cheap operation with the Cons operator (::) → Creates a new list with: • Head = given element • Tail = existing list

🏷️ Related concepts:

• linked list

• recursive type

Literals

#	Notation	Equivalent	Meaning (*)
0	[]	[]	Empty
1	[1]	1 :: []	Cons (1, Empty)
2	[2; 1]	2 :: 1 :: []	Cons (2, Cons (1, Empty))
3	[3; 2; 1]	3 :: 2 :: 1 :: []	Cons (3, Cons (2, Cons (1, Empty)))

(*) We can verify it with SharpLab.io :

//...
v1@2 = FSharpList<int>.Cons(1, FSharpList<int>.Empty);
v2@3 = FSharpList<int>.Cons(2, FSharpList<int>.Cons(1, FSharpList<int>.Empty));
//...

Initialisation

// Range: Start..End (Step=1)
let numFromOneToFive = [1..5]     // [1; 2; 3; 4; 5]

// Range: Start..Step..End
let oddFromOneToNine = [1..2..9]  // [1; 3; 5; 7; 9]

// Comprehension
let pairsWithDistinctItems =
    [ for i in [1..3] do
      for j in [1..3] do
        if i <> j then
            i, j ]
// [(1; 2); (1; 3); (2, 1); (2, 3); (3, 1); (3, 2)]

Exercices 🕹️

1. Implement the rev function → Inverts a list: rev [1; 2; 3] ≡ [3; 2; 1]

2. Implement the map function → Transforms each element: [1; 2; 3] |> map ((+) 1) ≡ [2; 3; 4]

💡 Hints → Use empty list [] or Cons head :: tail patterns → Write a recursive function

Solution

let rev list =
    let rec loop acc rest =
        match rest with
        | [] -> acc
        | x :: xs -> loop (x :: acc) xs
    loop [] list

let map f list =
    let rec loop acc rest =
        match rest with
        | [] -> acc
        | x :: xs -> loop (f x :: acc) xs
    list |> loop [] |> rev

We can verify that it's working in FSI console:

let (=!) actual expected =
    if actual = expected
    then printfn $"✅ {actual}"
    else printfn $"❌ {actual} != {expected}"

[1..3] |> rev =! [3; 2; 1];;
// ✅ [3; 2; 1]

[1..3] |> map ((+) 1) =! [2; 3; 4];;
// ✅ [2; 3; 4]

💡 Bonus: verify the tail recursion with sharplab.io

Type Array

Signature: 'T array (recommended) or 'T[] or 'T []

Main differences compared to the List:

• Fixed-size

• Fat square brackets [| |] for literals

• Mutable ❗

• Access by index in O(1) 👍

// Literal
[| 1; 2; 3; 4; 5 |]  // val it : int [] = [|1; 2; 3; 4; 5|]

// Range
[| 1 .. 5 |] = [| 1; 2; 3; 4; 5 |]  // true
[| 1 .. 3 .. 10 |] = [| 1; 4; 7; 10 |] // true

// Comprehension
[| for i in 1 .. 5 -> i, i * 2 |]
// [|(1, 2); (2, 4); (3, 6); (4, 8); (5, 10)|]

// Slicing: sub-array between the given `(start)..(end)` indices
let names =    [|"0: Alice"; "1: Jim"; "2: Rachel"; "3: Sophia"; "4: Tony"|]

names[1..3] // [|            "1: Jim"; "2: Rachel"; "3: Sophia"           |]
names[2..]  // [|                      "2: Rachel"; "3: Sophia"; "4: Tony"|]
names[..3]  // [|"0: Alice"; "1: Jim"; "2: Rachel"; "3: Sophia"           |]

// Mutation
let names = [| "Juliet"; "Tony" |]
names[1] <- "Bob"
names;;  // [| "Juliet"; "Bob" |]

💡 Slicing works also with string: "012345"[1..3] ≡ "123"

Alias ResizeArray

Alias for System.Collections.Generic.List<T> BCL type

let rev items = items |> Seq.rev |> ResizeArray
let initial = ResizeArray [ 1..5 ]
let reversed = rev initial // ResizeArray [ 5..-1..0 ]

Advantages 👍

• No need for open System.Collections.Generic

• No name conflicts on List

Notes ☝️

• Do not confuse the alias ResizeArray with the Array F♯ type.

• ResizeArray is in F♯ a better name for the BCL generic List<T>

  • Closer semantically and in usage to an array than a list

Type Seq

Definition: Series of elements of the same type

't seq ≡ Seq<'T> ≡ IEnumerable<'T>

Lazy: sequence built gradually as it is iterated ≠ All other collections built entirely from their declaration

Syntax

seq { items | range | comprehension }

seq { yield 1; yield 2 }   // 'yield' explicit 😕
seq { 1; 2; 3; 5; 8; 13 }  // 'yield' omitted 👍

// Range
seq { 1 .. 10 }       // seq [1; 2; 3; 4; ...]
seq { 1 .. 2 .. 10 }  // seq [1; 3; 5; 7; ...]

// Comprehension
seq { for i in 1 .. 5 do i, i * 2 }
// seq [(1, 2); (2, 4); (3, 6); (4, 8); ...]

Infinite sequence

2 options to write an infinite sequence

• Use Seq.initInfinite function

• Write a recursive function to generate the sequence

Option 1

Seq.initInfinite function

• Signature: (initializer: (index: int) -> 'T) -> seq<'T>

• Parameter: initializer is used to create the specified index element (>= 0)

let seqOfSquares = Seq.initInfinite (fun i -> i * i)

seqOfSquares |> Seq.take 5 |> List.ofSeq;;
// val it: int list = [0; 1; 4; 9; 16]

Option 2

Recursive function to generate the sequence

[<TailCall>]
let rec private squaresStartingAt n =
    seq {
        yield n * n
        yield! squaresStartingAt (n + 1) // 🔄️
    }

let squares = squaresStartingAt 0

squares |> Seq.take 10 |> List.ofSeq;;
// val it: int list = [0; 1; 4; 9; 16; 25; 36; 49; 64; 81]

Type Set

• Self-ordering collection of unique elements (without duplicates)

• Implemented as a binary tree

// Construct
set [ 2; 9; 4; 2 ]          // set [2; 4; 9]  // ☝ Only one '2' in the set
Set.ofArray [| 1; 3 |]      // set [1; 3]
Set.ofList [ 1; 3 ]         // set [1; 3]
seq { 1; 3 } |> Set.ofSeq   // set [1; 3]

// Add/remove element
Set.empty         // set []
|> Set.add 2      // set [2]
|> Set.remove 9   // set [2]    // ☝ No exception
|> Set.add 9      // set [2; 9]
|> Set.remove 9   // set [2]

Informations

→ count, minElement, maxElement

let oneToFive = set [1..5]          // set [1; 2; 3; 4; 5]

// Number of elements: `Count` property or `Set.count` function - ⚠️ O(N)
// ☝ Do not confuse with `Xxx.length` for Array, List, Seq
let nb = Set.count oneToFive // 5

// Element min, max
let min = oneToFive |> Set.minElement   // 1
let max = oneToFive |> Set.maxElement   // 5

Operations

	Operation	Operator	Function for 2 sets	Function for N sets
⊖	Difference	-	Set.difference	Set.differenceMany
∪	Union	+	Set.union	Set.unionMany
∩	Intersection	×	Set.intersect	Set.intersectMany

Examples:

| Union             | Difference        | Intersection      |
|-------------------|-------------------|-------------------|
|   [ 1 2 3 4 5   ] |   [ 1 2 3 4 5   ] |   [ 1 2 3 4 5   ] |
| + [   2   4   6 ] | - [   2   4   6 ] | ∩ [   2   4   6 ] |
| = [ 1 2 3 4 5 6 ] | = [ 1   3   5   ] | = [   2   4     ] |

Type Map

Associative array { Key → Value } ≃ C♯ immutable dictionary

// Construct: from collection of (key, val) pairs
// → `Map.ofXxx` function • Xxx = Array, List, Seq
let map1 = seq { (2, "A"); (1, "B") } |> Map.ofSeq
// → `Map(tuples)` constructor
let map2 = Map [ (2, "A"); (1, "B"); (3, "C"); (3, "D") ]
// map [(1, "B"); (2, "A"); (3, "D")]
// 👉 Ordered by key (1, 2, 3) and deduplicated in last win - see '(3, "D")'

// Add/remove entry
Map.empty         // map []
|> Map.add 2 "A"  // map [(2, "A")]
|> Map.remove 5   // map [(2, "A")] // ☝ No exception if key not found
|> Map.add 9 "B"  // map [(2, "A"); (9, "B")]
|> Map.remove 2   // map [(9, "B")]

Access/Lookup by key

let table = Map [ ("A", "Abc"); ("G", "Ghi"); ("Z", "Zzz") ]

// Indexer by key
table["A"];;  // val it: string = "Abc"
table["-"];;  // 💣 KeyNotFoundException

// `Map.find`: return the matching value or 💣 if the key is not found
table |> Map.find "G";; // val it: string = "Ghi"

// `Map.tryFind`: return the matching value in an option
table |> Map.tryFind "Z";;  // val it: string option = Some "Zzz"
table |> Map.tryFind "-";;  // val it: string option = None

Dictionaries

dict function

• Builds an IDictionary<'k, 'v> from a sequence of key/value pairs

• The interface is error prone: the dictionary is immutable ❗

let table = dict [ (1, 100); (2, 200) ]
// val table: System.Collections.Generic.IDictionary<int,int>

table[1];;          // val it: int = 100

table[99];;         // 💣 KeyNotFoundException

table[1] <- 111;;   // 💣 NotSupportedException: This value cannot be mutated
table.Add(3, 300);; // 💣 NotSupportedException: This value cannot be mutated

readOnlyDict function

• Builds an IReadOnlyDictionary<'k, 'v> from a sequence of key/value pairs

• The interface is honest: the dictionary is immutable

let table = readOnlyDict [ (1, 100); (2, 200) ]
// val table: System.Collections.Generic.IReadOnlyDictionary<int,int>

table[1];;          // val it: int = 100

table[99];;         // 💣 KeyNotFoundException

do table[1] <- 111;;
// ~~~~~~~~ 💥 Error FS0810: Property 'Item' cannot be set

do table.Add(3, 300);;
//       ~~~ 💥 Error FS0039:
// The type 'IReadOnlyDictionary<_,_>' does not define the field, constructor or member 'Add'.

Recommendation

dict returns an object that does not implement fully IDictionary<'k, 'v> → Violate the Liskov's substitution principle❗

readOnlyDict returns an object that respects IReadOnlyDictionary<'k, 'v>

👉 Prefer readOnlyDict to dict when possible

KeyValue active pattern

Used to deconstruct a KeyValuePair dictionary entry to a (key, value) pair

// FSharp.Core / prim-types.fs#4983
let (|KeyValue|) (kvp: KeyValuePair<'k, 'v>) : 'k * 'v =
    kvp.Key, kvp.Value

let table =
    readOnlyDict
        [ (1, 100)
          (2, 200)
          (3, 300) ]

// Iterate through the dictionary
for kv in table do // kv: KeyValuePair<int,int>
    printfn $"{kv.Key}, {kv.Value}"

// Same with the active pattern
for KeyValue (key, value) in table do
    printfn $"{key}, {value}"

Lookup performance

🔗 High Performance Collections in F♯ • Compositional IT (2021)

Dictionary vs Map

readOnlyDict creates high-performance dictionaries → 10x faster than Map for lookups

Dictionary vs Array

~ Rough heuristics

→ The Array type is OK for few lookups (< 100) and few elements (< 100) → Use a Dictionary otherwise

Map and Set vs IComparable

Only works if elements (of a Set) or keys (of a Map) are comparable!

Examples:

// Classes are not comparable by default, so you cannot use them in a set or a map
type NameClass(name: string) =
    member val Value = name

let namesClass = set [NameClass("Alice"); NameClass("Bob")]
//                    ~~~~~~~~~~~~~~~~~~
// 💥 Error FS0193: The type 'NameClass' does not support the 'comparison' constraint.
//     For example, it does not support the 'System.IComparable' interface

F# functional type: tuple, record, union

// Example: single-case union
type Name = Name of string

let names = set [Name "Alice"; Name "Bob"]

Structs:

[<Struct>]
type NameStruct(name: string) =
    member this.Name = name

let namesStruct = set [NameStruct("Alice"); NameStruct("Bob")]

Classes implementing IComparable... but not IComparable<'T> 🤷