A vocabulary for data
Most programs spend their time on collections: the marks of a class, the readings from a sensor, the lines of a file, the words of a document. In an imperative language you process them with loops and mutable accumulators, writing the same few patterns over and over: "keep the ones that...", "turn each into...", "add them all up", "group them by...". In F# each of those patterns is a named function in a module, and a computation is a pipeline of them.
F# has five everyday collections: lists, arrays, sequences, maps and sets. Each has a module of functions with mostly the same names (List.map, Array.map, Seq.map), so once you know the vocabulary, you can use it on all of them. The skill this lesson builds is to look at a problem and see the pipeline. It takes a little practice, and then it becomes the natural way to think: most F# developers find that the shape of the pipeline is the first thing they sketch, before writing any individual step.
Lists and the List module
An F# list is an immutable, singly linked list: [ 1; 2; 3 ], with elements separated by semicolons (or newlines). It is the default collection in F# code. Here is a set of exam marks, processed in several ways:
type Mark = { Student: string; Subject: string; Score: int }
let results =
[ { Student = "Aisha"; Subject = "Maths"; Score = 91 }
{ Student = "Aisha"; Subject = "History"; Score = 78 }
{ Student = "Bao"; Subject = "Maths"; Score = 64 }
{ Student = "Bao"; Subject = "History"; Score = 85 }
{ Student = "Carmen"; Subject = "Maths"; Score = 47 }
{ Student = "Carmen"; Subject = "History"; Score = 92 }
{ Student = "Dev"; Subject = "Maths"; Score = 88 } ]
// map, filter, sumBy, averageBy, maxBy
let mathsScores = results |> List.filter (fun r -> r.Subject = "Maths") |> List.map (fun r -> r.Score)
printfn "Maths scores: %A" mathsScores
printfn "Best overall: %s" (results |> List.maxBy (fun r -> r.Score)).Student
// groupBy returns (key, items) pairs
for subject, rs in results |> List.groupBy (fun r -> r.Subject) do
printfn "%-8s average %.1f from %d students" subject (rs |> List.averageBy (fun r -> float r.Score)) rs.Length
// partition splits into two lists; countBy counts per key
let passed, failed = results |> List.partition (fun r -> r.Score >= 50)
printfn "%d passed, %d failed: %A" passed.Length failed.Length (failed |> List.map (fun r -> r.Student))
printfn "%A" (results |> List.countBy (fun r -> r.Student) |> List.filter (fun (_, n) -> n < 2))
// choose = map + filter in one step, keeping only the Some results
let honours =
results |> List.choose (fun r -> if r.Score >= 90 then Some $"{r.Student} ({r.Subject})" else None)
printfn "Honours: %s" (String.concat ", " honours)
// fold: the general way to accumulate
let total = results |> List.fold (fun acc r -> acc + r.Score) 0
printfn "Total of all scores: %d" total
// Lists are built from the front with ::, and are immutable.
let original = [ 2; 3 ]
let extended = 1 :: original
printfn "%A %A %A" original extended (extended @ [ 4; 5 ])It prints:
Maths scores: [91; 64; 47; 88]
Best overall: Carmen
Maths average 72.5 from 4 students
History average 85.0 from 3 students
6 passed, 1 failed: ["Carmen"]
[("Dev", 1)]
Honours: Aisha (Maths), Carmen (History)
Total of all scores: 545
[2; 3] [1; 2; 3] [1; 2; 3; 4; 5]The functions used here make up most of what you need day to day:
| Function | What it does |
|---|---|
List.map f | apply f to every element |
List.filter p | keep the elements for which p is true |
List.choose f | apply f, keep only the Some results (map and filter at once) |
List.sumBy, List.averageBy, List.maxBy, List.minBy | aggregate by a projection |
List.groupBy key | group into (key, elements) pairs |
List.countBy key | count elements per key |
List.partition p | split into two lists: those that pass and those that fail |
List.fold f initial | the general accumulator: combine elements one by one into a result |
List.sortBy, List.distinct, List.truncate, List.exists, List.forall, List.tryFind | sort, deduplicate, take, test and search |
fold is the general case. Every aggregate can be written as a fold: start from an initial state, and combine it with each element in turn. List.fold (fun acc r -> acc + r.Score) 0 is a sum. When no specialised function fits, reach for fold; when one does, use it, because its name says what you mean.
Building lists. :: (pronounced "cons") puts one element in front of a list in constant time, sharing the rest: extended reuses all of original, which is safe because neither can change. @ appends two lists, which must copy the first, so it costs time proportional to its length. Build lists from the front, or with a comprehension; avoid appending one element at a time to the end in a loop.
Comprehensions, ranges and arrays
Comprehensions generate collections with for, if and yield inside brackets. They are often clearer than a chain of functions when there are several nested loops. Arrays, written [| ... |], are .NET arrays: fixed size, contiguous in memory, indexed in constant time, and mutable. Use them where performance matters or where an algorithm genuinely updates elements in place.
// List comprehensions: generate a list with for, if and yield.
let triples =
[ for a in 1..20 do
for b in a..20 do
for c in b..20 do
if a * a + b * b = c * c then
yield (a, b, c) ]
printfn "Pythagorean triples up to 20: %A" triples
// Ranges with steps
printfn "%A %A" [ 0..5..20 ] [ 10..-3..1 ]
// Arrays: fixed size, fast indexing, and mutable elements.
let temps = [| 18.5; 21.0; 24.5; 23.0; 19.5; 17.0; 16.5 |]
temps[0] <- 18.0
printfn "First reading corrected to %.1f; %d readings" temps[0] temps.Length
// Sliding windows: a three-day moving average.
let moving =
temps
|> Array.windowed 3
|> Array.map Array.average
printfn "Moving averages: %s" (moving |> Array.map (sprintf "%.1f") |> String.concat " ")
// pairwise: day-to-day changes
let changes = temps |> Array.pairwise |> Array.map (fun (a, b) -> b - a)
printfn "Biggest rise: %.1f" (Array.max changes)
// Array.init and 2D arrays
let squares = Array.init 6 (fun i -> i * i)
let grid = Array2D.init 3 4 (fun row col -> row * 4 + col)
printfn "%A, grid[2,3] = %d" squares grid[2, 3]It prints:
Pythagorean triples up to 20: [(3, 4, 5); (5, 12, 13); (6, 8, 10); (8, 15, 17); (9, 12, 15); (12, 16, 20)]
[0; 5; 10; 15; 20] [10; 7; 4; 1]
First reading corrected to 18.0; 7 readings
Moving averages: 21.2 22.8 22.3 19.8 17.7
Biggest rise: 3.5
[|0; 1; 4; 9; 16; 25|], grid[2,3] = 11[ 0..5..20 ]counts in steps of 5;[ 10..-3..1 ]counts down. Ranges work for lists, arrays and sequences.temps[0] <- 18.0mutates an array element. (Indexing withtemps[0]needs F# 6 or later; older code writestemps.[0].)Array.windowed 3produces every run of three consecutive elements, so averaging each gives a moving average;Array.pairwisegives consecutive pairs. These two functions replace a surprising number of index-juggling loops.sprintf "%.1f"partially applied is a function from float to string, ready forArray.map.Array2Dprovides rectangular two-dimensional arrays, indexed asgrid[row, column].
Arrays also have a parallel module: Array.Parallel.map and its siblings split the work across all processor cores, which can make CPU-heavy transformations of large arrays several times faster with a one-word change. Because the mapping function is pure, there is nothing to lock and nothing to go wrong.
The List, Array and Seq modules have nearly identical functions, so converting code between them is usually a matter of changing the module name. List.ofArray, Array.ofList, List.ofSeq and friends convert between the collections themselves.
Sequences, maps and sets
Definition— Sequence
A value of type seq<int> (or any element type) is F#'s name for .NET's IEnumerable: a sequence of elements produced on demand. A sequence expression, seq { ... }, describes how to produce them, but runs only as far as a consumer asks.
Definition— Map and Set
Map is an immutable dictionary from keys to values, and Set an immutable set of values. Both are balanced binary trees: look-up, insertion and removal take time, and "adding" returns a new map or set that shares most of its structure with the old one.
// Sequences are lazy: elements are computed only when they are needed.
let noisy =
seq {
for i in 1..5 do
printfn " computing %d" i
yield i * 10
}
printfn "Defined the sequence; nothing computed yet."
printfn "First two: %A" (noisy |> Seq.take 2 |> List.ofSeq)
// Infinite sequences are fine if you only take part of them.
let isPrime n =
n > 1 && Seq.forall (fun d -> n % d <> 0) (seq { 2 .. int (sqrt (float n)) })
let primes = Seq.initInfinite id |> Seq.filter isPrime
printfn "First ten primes: %A" (primes |> Seq.take 10 |> List.ofSeq)
// Seq.unfold builds a sequence from a state: here, Fibonacci numbers.
let fibs = Seq.unfold (fun (a, b) -> Some(a, (b, a + b))) (0L, 1L)
printfn "First Fibonacci number over a million: %d" (fibs |> Seq.find (fun f -> f > 1_000_000L))
// Map: an immutable dictionary. Set: an immutable set. Both are balanced trees.
let text = "the quick brown fox jumps over the lazy dog the end"
let counts =
text.Split ' '
|> Array.fold (fun (m: Map<string, int>) w -> m |> Map.change w (fun c -> Some(defaultArg c 0 + 1))) Map.empty
printfn "'the' appears %d times" counts["the"]
printfn "Has 'cat'? %b; tryFind 'cat': %A" (counts.ContainsKey "cat") (Map.tryFind "cat" counts)
printfn "Keys in order: %s" (counts |> Map.keys |> String.concat " ")
let vowels = set [ 'a'; 'e'; 'i'; 'o'; 'u' ]
let letters = text |> Seq.filter System.Char.IsLetter |> Set.ofSeq
printfn "Letters used: %d; vowels used: %A" letters.Count (Set.intersect letters vowels)
printfn "Pangram? %b" (letters.Count = 26)It prints:
Defined the sequence; nothing computed yet.
computing 1
computing 2
First two: [10; 20]
First ten primes: [2; 3; 5; 7; 11; 13; 17; 19; 23; 29]
First Fibonacci number over a million: 1346269
'the' appears 3 times
Has 'cat'? false; tryFind 'cat': None
Keys in order: brown dog end fox jumps lazy over quick the
Letters used: 26; vowels used: set ['a'; 'e'; 'i'; 'o'; 'u']
Pangram? trueThe first part makes laziness visible. Defining noisy computed nothing; Seq.take 2 asked for two elements, so exactly two "computing" lines appear, interleaved with the consumer. That is the same deferred execution that C#'s LINQ uses, because it is the same .NET interface underneath.
Laziness makes infinite sequences practical. Seq.initInfinite id is 0, 1, 2, ... forever; filtering it for primes and taking ten finishes, because each step asks only for what it needs. Seq.unfold generates a sequence from a state, here the pair of the last two Fibonacci numbers, and Seq.find stops at the first match. Like any IEnumerable, a sequence is recomputed every time it is enumerated; Seq.cache keeps the results if you need them more than once.
The word-count shows Map at work. Map.change updates one key with a function that receives the current value as an option (None if the key is new) and returns the new one. defaultArg c 0 means "the value inside c, or 0 if there is none". A map can be indexed like a dictionary, counts["the"], which throws if the key is absent; Map.tryFind returns an option instead. Keys come out in sorted order, because a map is a sorted tree. set [ ... ] creates a set, and Set.intersect, Set.union and Set.difference do set algebra. The sentence turns out to be a pangram, using all 26 letters.
Choosing a collection
| Collection | Strengths | Costs |
|---|---|---|
| list | immutable, pattern-matchable (head :: tail), cheap to add at the front | indexing and appending are |
| array | indexing, compact, fast to iterate, mutable when needed | fixed size; mutation must be managed carefully |
| seq | lazy, can be infinite, works with any .NET collection | recomputed on each enumeration; slower per element |
| Map, Set | immutable, sorted, look-up and update | slower than hash-based .NET collections for large data |
ResizeArray, Dictionary, HashSet (.NET) | fastest mutable growable list and hash-based look-up | mutable: keep them local, or behind a function |
The common default is: lists for modest amounts of data in domain code, arrays for numerical work and large data, sequences for streaming and for anything read from outside, and Map and Set for keyed data that is passed around. When profiling shows a hot spot, switch locally to arrays or the mutable .NET collections. (ResizeArray<'T> is F#'s abbreviation for .NET's growable System.Collections.Generic.List<'T>, renamed to avoid confusion with F#'s own list.)
From a loop to a fold
Newcomers to F# often know how to solve a problem with a loop and mutable variables, and wonder how to do it "functionally". There is a mechanical translation: the mutable variables become the state of a fold. Here is a problem, the longest run of dry days in a fortnight of rainfall readings, solved three ways:
// Daily rainfall in millimetres for two weeks (made-up data).
let rain = [ 0.0; 2.5; 0.0; 0.0; 0.0; 11.0; 0.0; 0.0; 0.0; 0.0; 0.4; 0.0; 0.0; 3.1 ]
// Imperative version: two mutable variables and a loop.
let longestDrySpellLoop (days: float list) =
let mutable best = 0
let mutable current = 0
for mm in days do
if mm = 0.0 then
current <- current + 1
best <- max best current
else
current <- 0
best
// Functional version: the same two variables become the state of a fold.
let longestDrySpellFold days =
days
|> List.fold (fun (best, current) mm ->
if mm = 0.0 then (max best (current + 1), current + 1) else (best, 0)) (0, 0)
|> fst
printfn "loop: %d, fold: %d" (longestDrySpellLoop rain) (longestDrySpellFold rain)
// A third way: describe the answer instead of computing it step by step.
let drySpells =
rain
|> List.fold (fun spells mm ->
match mm, spells with
| 0.0, current :: earlier -> (current + 1) :: earlier
| 0.0, [] -> [ 1 ]
| _, spells -> 0 :: spells) []
|> List.filter (fun n -> n > 0)
|> List.rev
printfn "dry spells: %A, longest %d, total dry days %d" drySpells (List.max drySpells) (List.sum drySpells)It prints:
loop: 4, fold: 4
dry spells: [1; 3; 4; 2], longest 4, total dry days 10The loop keeps two mutable variables, best and current. The fold keeps the same two values as a tuple, (best, current), and its lambda says how one day's reading turns the old pair into the new one. Nothing is mutated; at the end, fst takes the answer out of the final state. The two versions do the same work in the same order, and the compiler produces similar code for both.
The third version changes the question. Instead of tracking only the longest spell, it builds the list of all dry spells (newest first, so that each step only touches the front of the list, then reverses at the end), after which "longest", "total" and anything else are one function call each. This is a common move in functional design: compute a simple, complete intermediate result, then ask questions of it.
Which is best? In F# all three are acceptable. The loop, kept local inside a function, is perfectly idiomatic when it is the clearest expression of the idea; the fold is the standard functional form; the third is the most reusable. Choose for the reader.
Habits of fluent collection code
Prefer the specific function. List.sumBy over fold, List.exists over filter followed by a length check, List.choose over filter then map with an unsafe unwrap. The specific name tells the reader what is happening, and is usually faster too.
Mind the partial functions. List.head, List.max, List.find, List.reduce and indexing throw on empty or missing input. Their try versions (List.tryHead, List.tryFind, List.tryItem, List.tryLast) return an option instead; for functions with no try version, such as List.max, check for an empty list first. In code handling outside data, prefer the safe forms; the next lesson shows how to work with the options they return.
Keep pipelines one step per line, with a meaningful name for any intermediate result that deserves one.
Use Seq at the boundaries. Reading a large file with System.IO.File.ReadLines gives a sequence: process it lazily with Seq functions and only materialise what you need with List.ofSeq or Array.ofSeq. Remember that a sequence over a file re-reads the file each time it is enumerated.
Don't fear local mutation. A function that uses a mutable array or a Dictionary internally for speed, and returns an immutable result, is still a pure function from the outside. Plenty of FSharp.Core's own functions are written that way.
Common misconceptions
Misconception
"F# lists are like C#'s List." They are linked lists, not growable arrays. xs[1000] walks a thousand links; xs @ [ x ] copies the whole list. If you find yourself indexing a list or appending to its end, you probably want an array or a ResizeArray.
Misconception
"Immutable collections must copy everything on every change." Adding to the front of a list, or adding a key to a map, shares almost all of the old structure with the new one. Only the path to the change is new. This structural sharing is what makes immutable data practical.
Misconception
"A sequence remembers its elements." A seq is a recipe, run again every time you enumerate it, including any printing, file reading or expensive computation inside. Materialise it with List.ofSeq, or use Seq.cache, when you need the elements more than once.
Exercises
1. Lists, arrays, sequences, maps and sets
CoreComputationalWhat does this script print?
printfn "%d" (List.fold (fun acc bit -> acc * 2 + bit) 0 [ 1; 0; 1; 1 ])
2. Lists, arrays, sequences, maps and sets
CoreComputationalHow many lines starting with computing does this script print?
let noisy =
seq {
for i in 1..5 do
printfn "computing %d" i
yield i * 10
}
let found = noisy |> Seq.find (fun x -> x > 25)
printfn "found %d" found
3. Lists, arrays, sequences, maps and sets
Warm-upComputationalWhat does this script print?
let xs = [ for i in 1..3 do
yield i
yield i * 10 ]
printfn "%A" xs
4. Lists, arrays, sequences, maps and sets
CoreComputationalWhat does this script print?
Map.empty
|> Map.add "a" 1
|> Map.add "b" 2
|> Map.add "a" 3
|> Map.toList
|> printfn "%A"
5. Lists, arrays, sequences, maps and sets
CoreComputationalWhat does this script print?
let words = [ "kiwi"; "fig"; "plum"; "date"; "apple" ]
words |> List.groupBy String.length |> List.map (fun (len, ws) -> len, List.length ws) |> printfn "%A"
6. Lists, arrays, sequences, maps and sets
CoreHumanAn image filter reads a 4000 × 3000 grid of pixel brightness values, updates each value based on its neighbours, and does this many times. Which F# collection fits best?
Further reading and resources
- Lists · MicrosoftThe list type, its operators and comprehensions.
- Sequences · MicrosoftLazy sequences and sequence expressions.
- FSharp.Core API referenceEvery function in the List, Array, Seq, Map and Set modules, with examples.