Skip to content
Tutorials Center
My learning

Topics

Lesson 15 of 37 ยท Collections and Sequences

F# Lists: Immutable Linked Lists, Cons, Append and the List Module

Learn F# lists: literals, ranges, cons (::) and append (@), head/tail, indexing costs, the List module functions, sorting, grouping, zip, and how immutable lists share memory.

The list is F#'s everyday collection: an ordered, immutable, singly linked sequence of items of the same type. Lists are the natural partner of recursion and pattern matching, and the List module contains dozens of functions you will pipe data through constantly. This lesson covers creating lists, the cons and append operators, how lists are stored, and the most useful List functions.

Creating lists

FSHARP
let empty = []                          // 'a list
let numbers = [ 1; 2; 3; 4; 5 ]         // int list
let words = [ "red"; "green"; "blue" ]  // string list
let range = [ 1 .. 5 ]                  // [1; 2; 3; 4; 5]
let stepped = [ 0 .. 5 .. 20 ]          // [0; 5; 10; 15; 20]
let letters = [ 'a' .. 'e' ]

Items are separated by semicolons (a comma would create a one-element list holding a tuple!). On separate lines, newlines replace the semicolons:

FSHARP
let shopping =
    [ "milk"
      "bread"
      "eggs" ]

[1, 2, 3] is not a list of three ints: it is a list containing the single tuple (1, 2, 3), of type (int * int * int) list. This is the number one F# list mistake.

How lists are stored

A list is either empty or a head (the first item) and a tail (another list):

flowchart LR
    A["1"] --> B["2"] --> C["3"] --> D["[]"]

The list [1; 2; 3] is the head 1 followed by the list [2; 3].

Because lists are immutable, different lists can share their tails. Adding to the front never copies anything:

FSHARP
let tail = [ 2; 3 ]
let a = 1 :: tail      // [1; 2; 3]
let b = 0 :: tail      // [0; 2; 3]

Both a and b reuse the same [2; 3] in memory. That is why prepending is O(1) and why immutability is cheap here.

Cons and append

  • x :: list (cons) adds an element at the front: O(1).
  • list1 @ list2 (append) joins two lists: O(n) in the length of list1.
FSHARP
let l1 = 0 :: [ 1; 2 ]            // [0; 1; 2]
let l2 = [ 1; 2 ] @ [ 3; 4 ]       // [1; 2; 3; 4]
let l3 = List.append [ 1 ] [ 2 ]   // [1; 2]

Appending to the end of a long list repeatedly is slow (each @ copies the left list). Build the list backward with :: and reverse at the end, or use a comprehension.

Reading from a list

FSHARP
let xs = [ 10; 20; 30 ]
List.head xs        // 10
List.tail xs        // [20; 30]
xs[1]               // 20 (O(n): the list must be walked)
List.length xs      // 3
List.isEmpty xs     // false
List.tryHead []     // None

List.head [] throws an exception. When emptiness is possible use List.tryHead, List.tryFind, List.tryItem, which return option. Indexing a list is O(n); if you need fast random access, use an array (Arrays).

Pattern matching is the safest way to look inside:

FSHARP
let describe xs =
    match xs with
    | [] -> "empty"
    | [ x ] -> $"one item: {x}"
    | first :: rest -> $"starts with {first}, then {List.length rest} more"

Core List functions

FSHARP
let nums = [ 5; 3; 8; 1; 9; 2 ]

nums |> List.sort                         // [1; 2; 3; 5; 8; 9]
nums |> List.sortDescending               // [9; 8; 5; 3; 2; 1]
nums |> List.rev                          // [2; 9; 1; 8; 3; 5]
nums |> List.filter (fun n -> n > 4)      // [5; 8; 9]
nums |> List.map (fun n -> n * 2)         // [10; 6; 16; 2; 18; 4]
nums |> List.sum                          // 28
nums |> List.max                          // 9
nums |> List.take 2                       // [5; 3]
nums |> List.skip 4                       // [9; 2]
nums |> List.truncate 100                 // all six items: truncate never throws
nums |> List.contains 8                   // true
nums |> List.exists (fun n -> n > 8)      // true
nums |> List.forall (fun n -> n > 0)      // true
nums |> List.tryFind (fun n -> n > 5)     // Some 8
nums |> List.findIndex (fun n -> n = 1)   // 3

take and skip throw when the list is too short; truncate does not (and List.chunkBySize, List.windowed slice into groups).

Combining and reshaping

FSHARP
List.zip [ 1; 2; 3 ] [ "a"; "b"; "c" ]       // [(1, "a"); (2, "b"); (3, "c")]
List.indexed [ "x"; "y" ]                    // [(0, "x"); (1, "y")]
List.concat [ [ 1; 2 ]; [ 3 ] ]              // [1; 2; 3]
List.collect (fun n -> [ n; n * 10 ]) [ 1; 2 ]  // [1; 10; 2; 20]  (map then flatten)
List.partition (fun n -> n % 2 = 0) [ 1; 2; 3; 4 ]   // ([2; 4], [1; 3])
List.distinct [ 1; 2; 2; 3; 1 ]              // [1; 2; 3]
List.pairwise [ 1; 2; 3; 4 ]                 // [(1, 2); (2, 3); (3, 4)]
List.windowed 2 [ 1; 2; 3; 4 ]               // [[1; 2]; [2; 3]; [3; 4]]
List.chunkBySize 2 [ 1; 2; 3; 4; 5 ]         // [[1; 2]; [3; 4]; [5]]

Grouping and aggregating

FSHARP
let people = [ ("Ada", "UK"); ("Alan", "UK"); ("Grace", "US") ]

people
|> List.groupBy snd
|> List.map (fun (country, group) -> country, List.length group)
// [("UK", 2); ("US", 1)]

[ "pear"; "fig"; "banana" ] |> List.sumBy String.length     // 13
[ "pear"; "fig"; "banana" ] |> List.maxBy String.length      // "banana"
[ 1.0; 2.0; 6.0 ] |> List.average                            // 3.0
[ 1; 2; 6 ] |> List.averageBy float                          // 3.0

List.average requires floating-point elements, so for ints write List.averageBy float.

iter and iteri

List.iter runs an action for each element (returns unit):

FSHARP
[ "a"; "b" ] |> List.iter (printfn "item %s")
[ "a"; "b" ] |> List.iteri (fun i s -> printfn "%d=%s" i s)

Equality and printing

Lists compare structurally: [1; 2] = [1; 2] is true. printfn "%A" xs prints them in a readable form.

Choosing between list, array and seq

Need Choose
Pattern matching, recursion, prepend list
Fast indexing, mutation, interop array
Lazy or very large/infinite data seq

C# stand-ins

C# has List<T> (mutable, array-backed) rather than linked immutable lists, but LINQ provides the same operations. These stand-ins reproduce several results from above.

C# C# stand-in: sort, filter, map, sum

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

C# C# stand-in: group, zip and partition

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the type of [1, 2, 3] in F#?

    Commas build a tuple, so the list has one item which is a tuple. Use semicolons for three items.
  2. 2. Which operation is O(1) for a list?

    Cons just creates one new node pointing at the existing list.
  3. 3. What does List.head [] do?

    Use List.tryHead, which returns an option, when the list may be empty.
  4. 4. Which function turns a list of lists into one flat list?

    List.concat joins the inner lists in order.

Summary

  • Lists are immutable, singly linked and homogeneous; separate items with ;.
  • :: prepends in O(1), @ appends in O(n); lists share structure.
  • Prefer pattern matching and try... functions over List.head on possibly empty lists.
  • The List module offers map, filter, fold, sort, groupBy, zip, partition, distinct, windowed and many more.

Next: Arrays