Fold, sort and group

The fold

List.fold answers one value from many. It takes three things: a function that folds one element into the state so far, a starting state, and the list. List.fold (fun acc n -> acc + n) 0 is a sum, and "start at zero and add each one" is the whole idea.

The state can be anything, not just a number: start from [] and put each element on the front and you have reversed the list; start from an empty string and join each line and you have a report. A fold is the loop you would have written, with the changing part made explicit.

The folds you do not have to write

The standard library ships the common ones: List.sum, List.sumBy (which sums a number picked out of each element), List.maxBy, List.length. Reach for those first, and write a fold when the answer is not one of them — a running total, a longest word, a sentence assembled as it goes.

Sorting, counting, grouping

List.sortBy takes a function that produces the key to sort on, which is why List.sortBy String.length sorts words by length and why sorting records later is no harder. The sort is stable: values with equal keys keep the order they were in. Descending order is the same sort with a key that runs the other way, fun s -> -s.Amount, or List.sortByDescending.

List.countBy and List.groupBy take the same kind of key function and answer, respectively, how many values share each key and the values themselves. Both answer a list of pairs in the order each key first appeared, and groupBy is how a report gets its sections: one group per team, item or month.

Sequences, in one paragraph

seq { 1 .. 4 } looks like a list range and is not one: a sequence produces its values as they are asked for. Seq.sum asks for all of them, so the answer matches the list version, but a sequence can describe a range far too large to hold in memory. Lists come with their values already computed, which is the simpler thing to reason about; a sequence is what you reach for when the collection is a stream.

Three ways to one answer, and two ways to sections

let words = ["ada"; "bo"; "cy"; "dee"]

let letters = List.sumBy String.length words
let byLength = List.sortBy String.length words
let counts = List.countBy String.length words

The state can be a different type

The accumulator does not have to look like the elements. Folding a list of ints can produce a string, a tuple, or a record, because the folder is free to build whatever it wants from the state and the next value. List.fold (fun (total, lines) n -> ...) (0, []) carries a running total and the lines printed so far in one pair.

The folder always receives the state first and the element second. That order is why fun (total, lines) n -> reads as "take the state apart, then look at the next value". List.foldBack reverses the direction and the argument order; this course uses the left fold, where the list is consumed from the front.

The starting value is also the answer for an empty list. Zero is the identity for addition, one for multiplication, and the empty string for joining. A maximum has no safe numeric identity, because zero would win an all-negative list, so start from the first element.

Keys are queries in miniature

sortBy, countBy and groupBy all take one function that turns an element into the thing you care about. The key has to be comparable, and a tuple key compares left part first, then right, which is enough to sort by team and then by amount.

Both counting helpers answer pairs in first-appearance order; sorting them afterwards gives a report a stable section order.

Try these next

• Fold a list of words into one sentence, starting from the empty string.
• Count the lengths with List.countBy, then sort the pairs shortest first.
• Sum a list with List.fold, then with List.sumBy, and say which you would keep.