F# · Lesson 3

Collections

Lists, arrays and lazy sequences, the List module (map, filter, fold, groupBy...) and data pipelines.

7 min read

In short

  • Lists by default: [ 1; 2; 3 ], :: to prepend, @ to join
  • Arrays for .NET APIs and fast indexing; seq for lazy data
  • Chain List functions with |>: the collection almost always comes last
  • List.fold is reduce; comprehensions build lists
  • try functions return options instead of throwing

Most day-to-day F# code is "take some data, transform it, summarise it". That's done with three collection types and a big library of functions that you chain with |>.

Lists

▶ Try
let prices = [ 4.5; 12.0; 7.25 ]      // float list
let empty : int list = []
let more = 1.0 :: prices              // prepend: [1.0; 4.5; 12.0; 7.25]
let all = prices @ [ 3.0; 9.0 ]       // concatenate two lists
let first = List.head prices          // 4.5 (throws on an empty list!)
▶ Try
const prices: number[] = [4.5, 12, 7.25];
const more = [1, ...prices];
const all = [...prices, 3, 9];

Line by line:

  • Elements are separated by semicolons, not commas. On separate lines you can drop the ;:
    ▶ Try
    let cities =
        [ "Lisbon"
          "Oslo"
          "Kyoto" ]
    
  • The type is written float list (or list<float>).
  • :: ("cons") puts one element in front of a list. It's O(1).
  • @ joins two lists. It copies the left list, so avoid it in tight loops.
  • F# lists are immutable singly-linked lists. "Adding" creates a new list that shares the old one's elements. Nothing is ever modified in place.

Ranges and comprehensions

▶ Try
let oneToFive = [ 1 .. 5 ]                       // [1; 2; 3; 4; 5]
let tens = [ 0 .. 10 .. 50 ]                     // [0; 10; 20; 30; 40; 50]
let countdown = [ 5 .. -1 .. 1 ]                 // [5; 4; 3; 2; 1]
let squares = [ for n in 1 .. 5 -> n * n ]       // [1; 4; 9; 16; 25]
let evens =
    [ for n in 1 .. 10 do
          if n % 2 = 0 then yield n ]            // [2; 4; 6; 8; 10]

[ for x in xs -> expr ] is a map; add do + if to filter. yield can usually be omitted. [ 1 .. 0 ] is simply [].

Arrays

▶ Try
let scores = [| 90; 75; 88 |]       // int array (also written int[])
let firstScore = scores[0]          // O(1) indexing
scores[1] <- 80                     // elements are mutable!
let len = scores.Length

Arrays are fixed-size, mutable, and fast to index: the same thing as a .NET array. You'll meet them constantly because .NET APIs return them ("a,b".Split(',') is a string[]). Convert with List.ofArray / Array.ofList.

Sequences (lazy)

▶ Try
let naturals = Seq.initInfinite id                 // 0, 1, 2, ... never ends
let firstEvens = naturals |> Seq.filter (fun n -> n % 2 = 0) |> Seq.take 3 |> List.ofSeq   // [0; 2; 4]
let lines = seq { for i in 1 .. 1000000 -> $"line {i}" }   // nothing computed yet

seq<'T> is .NET's IEnumerable<T>, the equivalent of a JS iterator or generator: items are produced on demand. Lists and arrays are also sequences, so any Seq function accepts them. Use seq for large or infinite data and streaming; use lists by default.

The List module

Almost every operation is a function in the List module (with twins in Array and Seq). The collection is almost always the last argument (List.foldBack is the exception), so they chain with |>.

F#What it doesTypeScript
List.map ftransform each item.map(f)
List.filter pkeep matching items.filter(p)
List.sum, List.sumBy fadd up.reduce((a, x) => a + f(x), 0)
List.averageBy fmean (throws on empty)
List.fold f initaccumulate a state.reduce(f, init)
List.reduce ffold without init (throws on empty).reduce(f)
List.sortBy f, List.sortByDescending fsorted copy[...xs].sort(...)
List.groupBy f(key, items) listObject.groupBy
List.countBy f(key, count) list
List.distinctremove duplicates[...new Set(xs)]
List.choose fmap to option, keep the Somes.flatMap(x => cond ? [y] : [])
List.collect fmap to lists, then flatten.flatMap(f)
List.tryFind pfirst match as an option.find(p)
List.exists p, List.forall pany / all.some(p), .every(p)
List.zip a bpair up two lists
List.truncate n, List.skip nfirst n / drop n.slice(0, n), .slice(n)
List.length, List.isEmpty, List.rev.length, .length === 0, .reverse()
List.maxBy f, List.minBy fbiggest / smallest item by key

List.fold deserves a closer look, because it's the general tool behind most of the others:

▶ Try
let total = [ 3; 5; 2 ] |> List.fold (fun acc x -> acc + x) 0      // 10
▶ Try
const total = [3, 5, 2].reduce((acc, x) => acc + x, 0);

Options in 60 seconds

List.tryFind, List.tryHead and List.choose use the option type: a value that may be missing.

▶ Try
let found = [ 3; 8; 12 ] |> List.tryFind (fun n -> n > 5)    // Some 8
let missing = [ 3 ] |> List.tryFind (fun n -> n > 5)          // None

let describe (result: int option) : string =
    match result with
    | Some n -> $"found {n}"
    | None -> "nothing"

let orZero = missing |> Option.defaultValue 0                 // 0

Think number | undefined, except the compiler forces you to handle None before you can use the number. match is covered in depth later. For now, read it as a switch over the two cases.

Tuples, briefly

Grouping and counting functions return tuples: ("ERROR", 3) has type string * int (TypeScript [string, number]). Take them apart with fst/snd or in a lambda: fun (level, count) -> .... The next topic covers them properly.

Pipelines over data

Here's a realistic pipeline: top customers by spend, ignoring small orders.

▶ Try
let orders = [ ("alice", 120.0); ("bob", 35.5); ("alice", 18.0); ("carol", 99.9); ("bob", 80.0) ]

let topCustomers =
    orders
    |> List.filter (fun (_, amount) -> amount >= 20.0)
    |> List.groupBy fst
    |> List.map (fun (customer, items) -> customer, items |> List.sumBy snd)
    |> List.sortByDescending snd
// [("alice", 120.0); ("bob", 115.5); ("carol", 99.9)]
▶ Try
const totals = new Map<string, number>();
for (const [customer, amount] of orders.filter(([, a]) => a >= 20)) {
  totals.set(customer, (totals.get(customer) ?? 0) + amount);
}
const topCustomers = [...totals].sort((a, b) => b[1] - a[1]);

Each step is a pure function of the previous result, so you can comment out the tail and look at any intermediate value. That's how F# developers debug pipelines.

Common beginner mistakes

  • Commas in list literals. [1, 2, 3] is a list containing one tuple (1, 2, 3). Use [1; 2; 3].
  • :: with the list on the left. xs :: 4 doesn't compile; :: adds one item at the front. To append, use xs @ [ 4 ] (or build the list backwards and List.rev it once).
  • Functions that throw on empty lists: List.head, List.reduce, List.average, List.max, List.maxBy. Check for empty first (List.isEmpty), or use the try versions where they exist (List.tryHead, List.tryFind, List.tryItem...). There is no List.tryMax; guard with if List.isEmpty xs then ... else List.max xs.
  • Argument order. It's List.map f xs, not List.map xs f. With a pipe: xs |> List.map f.
  • Lambda can't see the type. List.map (fun s -> s.Length) words may fail with "Lookup on object of indeterminate type". Write words |> List.map (fun s -> s.Length): the pipe lets inference see words first.
  • List.average on ints. It only works on floats/decimals. Use List.averageBy float.
  • Indexing lists in a loop. xs[i] on a list is O(i). Use List functions or an array.
  • Forgetting laziness. A seq re-runs its work (and side effects) every time it's enumerated. Materialise it with List.ofSeq if you need it twice.
  • List.skip / List.take throw if there aren't enough items. List.truncate is the safe "at most n".

Cheat sheet

▶ Try
[ 1; 2; 3 ]  [| 1; 2; 3 |]  seq { 1 .. 3 }        // list, array, lazy seq
x :: xs      xs @ ys        [ 1 .. 10 ]           // cons, append, range
[ for x in xs do if x > 0 then x * 2 ]           // comprehension
xs |> List.map f |> List.filter p |> List.sum     // pipeline
xs |> List.fold (fun acc x -> acc + x) 0          // reduce with initial state
xs |> List.groupBy key |> List.map (fun (k, items) -> k, List.length items)
xs |> List.countBy key                            // (key * int) list
xs |> List.sortByDescending snd |> List.truncate 3
xs |> List.tryFind p |> Option.defaultValue fallback
xs |> List.choose tryParse                        // keep only successful parses
List.ofArray arr   Array.ofList xs   List.ofSeq s // conversions

Practise this lesson

In the app: a short video, 6 exercises checked by real tests and a 12-question concept check. Free with a GitHub account. Running the exercises against their tests needs Pro.

Open in the app