jonnifyfsharp

Dive C1.07.1

List, array & seq

Three sequence types, three cost profiles — and choosing one is choosing what should be cheap.

F# gives three ways to hold an ordered sequence of values, and they are not interchangeable. The list [1; 2; 3] is an immutable singly-linked chain: prepending 0 :: xs is constant time, but reaching the i-th element walks the chain. The array [|1; 2; 3|] is mutable and contiguous: indexing arr.[0] is constant time, and an element can be assigned in place. The seq seq { 1..5 } is a lazy IEnumerable<'T>: its elements are produced on demand, so it can stand for a stream too large to hold at once. The right container is the one whose cheap operation matches the work you do most.

Compare the costs Module hub
C1.07.1 · part 1

The list: a chain you prepend to

A list literal is written with semicolons inside square brackets. Under it is a singly-linked chain: each cell holds one value and a reference to the rest. Adding to the front with the cons operator :: is constant time — the new cell points at the old chain, which is left untouched. Joining two lists with @ copies the left one, so it costs as much as that list is long.

let xs = [1; 2; 3]            // val xs : int list = [1; 2; 3]

0 :: xs                        // val it : int list = [0; 1; 2; 3]   prepend, O(1)
[1; 2] @ [3; 4]                // val it : int list = [1; 2; 3; 4]   append, O(n)
xs.Head                        // val it : int = 1                   the first cell, O(1)
[1; 2; 3]
a list literal — values separated by semicolons (a comma builds a tuple).
(::)
cons: 0 :: xs adds one element to the front in O(1).
(@)
append: xs @ ys joins two lists, copying the left in O(n).
int list
the element type plus list — a homogeneous, immutable chain.

The list is immutable. 0 :: xs does not change xs; it produces a new list that shares xs as its tail. Nothing was copied to prepend, and the old value is still [1; 2; 3].

C1.07.1 · part 2

The array, and the lazy seq

An array literal uses the bar-bracket form [|...|]. It is a contiguous block of fixed size: indexing is one step, and — unlike the list — an element can be assigned with <-. Reach for the array when you index by position or mutate in a tight loop.

let arr = [|1; 2; 3|]          // val arr : int [] = [|1; 2; 3|]

arr.[0]                        // val it : int = 1        index, O(1)
arr.[0] <- 9                   // mutate in place — arr is now [|9; 2; 3|]
arr |> Array.sum               // val it : int = 14

A seq is a lazy IEnumerable<'T>. The elements are not stored — they are produced one at a time when something pulls them. FSI signals this by printing only the first few and then an ellipsis: it has not run the whole sequence to show you the value.

let s = seq { 1..5 }            // val s : seq<int>
s                              // val it : int seq = seq [1; 2; 3; 4; ...]   lazy

seq { for x in 1..3 -> x * x }  // produces 1, 4, 9 on demand
[|1; 2; 3|]
an array literal — contiguous, fixed-size, indexable in O(1).
arr.[0] <- 9
element assignment — arrays are mutable; lists are not.
seq { 1..5 }
a sequence expression — a lazy IEnumerable<'T>.
seq [1; 2; …]
FSI prints a seq with an ellipsis: only the head is forced, not the whole sequence.

Which container makes this cheap

Choosing a container is choosing which operation is constant-time. Pick an operation below; the table and the diagram light each container's cost — O(1) where it is cheap, O(n) where it walks the whole structure. The full cost table is shown for every operation; selecting one highlights its row.

Operation × container · cost

list O(1) array O(n) seq O(n)
Cost by operation and container (n = the number of elements)
operationlistarrayseq
prepend 0 :: xsO(1)O(n)O(1)
index xs.[i]O(n)O(1)O(n)
append xs @ ysO(n)O(n)O(1)
length List.lengthO(n)O(1)O(n)
prepend 0 :: xs · list O(1) · array O(n) · seq O(1) · the list and seq prepend cheaply; the array must shift every element

No container is fastest at everything. The list prepends, the array indexes, the seq holds what it cannot store — pick by the operation you repeat.

The cost model

Each container is best at one operation: prepend for the list, index for the array, on-demand production for the seq.

F# default

The list is the functional default; reach for array or seq when its cost says so.

Where this leads

The cost model settles where to store values; the next dive turns to what to do with all of them at once. The List module supplies functions — map, filter, fold — that transform a whole collection and return a new one. The same names live in the Array and Seq modules, so the technique carries across all three.

↑ C1.07 · Collections C1.07.2 · Transforming collections → C1.07.3 · Map & Set

References

Sources

Related in this course