Types
Type List
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♯'sList
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 directlyno 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
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
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
Array
Signature: 'T array
(recommended) or 'T[]
or 'T []
Main differences compared to the List
:
Fixed-size
Fat square brackets
[| |]
for literalsMutable ❗
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
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 theArray
F♯ type.ResizeArray
is in F♯ a better name for the BCL genericList<T>
Closer semantically and in usage to an array than a list
Type Seq
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
functionWrite 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
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
⊖
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
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
dict
functionBuilds an
IDictionary<'k, 'v>
from a sequence of key/value pairsThe 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
readOnlyDict
functionBuilds an
IReadOnlyDictionary<'k, 'v>
from a sequence of key/value pairsThe 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
KeyValue
active patternUsed 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
Dictionary
vs Map
readOnlyDict
creates high-performance dictionaries
→ 10x faster than Map
for lookups
Dictionary
vs Array
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
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>
🤷
Last updated
Was this helpful?