Module C1.07
Collections list, array, seq
A small family of containers, each with one cost it is best at — pick by the cost, not by habit.
A program holds many values, not one, so F# supplies a small family of immutable-first containers. The list is the functional default — a singly-linked chain that prepends in constant time. The array is mutable and contiguous, the one to reach for when you index by position. The seq is lazy — it produces elements on demand and need never be fully in memory. And Map and Set are immutable trees for key lookup and set algebra. The containers differ in their cost: choosing the right one is choosing which operation should be cheap. This module covers the family in three dives — the three sequence types and their cost model, the module functions that transform a whole collection in a pipeline, and Map and Set for lookup and membership.
The family, in three dives
You have shaped values from the records and unions of the previous module. Programs hold many of them, and the container you store them in is a cost decision. The three dives below build that decision. Select one to read its summary and the one idea it adds.
The first dive sets the cost model — why a list prepends in
O(1) but indexes in O(n), why an
array indexes in O(1), and what it means for a
seq to be lazy. The second covers transforming: the module
functions List.map, List.filter, and
List.fold that each return a new collection and chain with |>.
The third is Map and Set — an immutable key→value tree and an immutable set, for lookup and
for union, intersection, and membership.
The three dives · select one
The three sequence types and their cost model: list prepends in O(1), array indexes in O(1), seq is lazy and produces elements on demand.
Open this dive · or pick another above
One family, three cost profiles. The container you reach for is the one whose cheap operation is the one you do most.
The three dives
Read them in order. Each stands on valid, runnable F#: every list literal, every module function, and every
FSI line below can be typed into dotnet fsi and produces exactly what the page shows.
List, array & seq
The three sequence types and the cost model: 0 :: xs is O(1), arr.[0] is O(1), seq is lazy.
- costwhich container makes which operation cheap
Transforming collections
The module functions — map, filter, fold, sum — each non-mutating, chained with |>.
- pipea whole collection through a pipeline
Map & Set
Immutable key→value lookup with Map.tryFind, and set algebra with Set.union, Set.intersect.
- treeslookup by key, membership, set algebra
References
Sources
- Microsoft — F# documentation — the language guide: lists, arrays, sequences, maps, and sets.
- FSharp.Core API reference — the
List,Array,Seq,Map, andSetmodules. - The F# Language Specification — list and array expressions, sequence expressions, and the cons operator.
Related in this course
- C1.07.1 — List, array & seq — the cost model the rest of the module builds on.
- C1.03 — Functions — the functions that
List.mapandList.filtertake. - Elixir — Folds — folding over collections on the BEAM.