Lists, and the functions that walk them

One type, one shape

A list holds values that all have the same type: [3; 1; 4] is a list of three ints and [] is the empty one. The colon-colon operator puts a single item on the front, so 1 :: [2; 3] is the same list as [1; 2; 3]. Adding to the front is cheap; reaching the last item means walking the whole chain.

Lists are immutable, so nothing is added to a list you already have: a function that seems to add an item answers a new list that shares the tail. That sharing is why the front is the natural place to work, and why printing a list usually means joining it into one string first.

Four functions instead of a loop

List.map changes every item and keeps the shape, List.filter keeps the items that pass a test, List.fold_left carries an accumulator from a seed through the list, and List.sort puts the items in order. Each takes a function as an argument, which is why the function is often written inline as fun x -> ....

A list is printed by turning it into text: String.concat ", " joins a list of strings, so mapping string_of_int over a list of numbers first gives one line you can print. List.iter is the fifth function worth knowing: it runs a function on every item for its effect, which is how a list is printed one item per line. The functions compose, and that is the point — a filter, a sort and a map describe an answer rather than the steps to it. Seen together, map, filter and fold are one idea: each takes a list and a function and decides what to do with the answers — change every item, keep the ones that pass, or carry a running value from one item to the next.

Two constructors, and a walk that follows them

Every list is either [] or an item consed onto another list with ::. [1; 2; 3] is shorthand for 1 :: 2 :: 3 :: [], and that is why the same two patterns can take any list apart: [] for the empty case and x :: rest for one item and the remainder.

A recursive list function follows the shape of the data. The empty case answers a base value, and the cons case does something with x and calls itself on rest. List.map, List.filter and List.fold_left are exactly this walk with the interesting part supplied as a function, which is why you rarely need to write the recursion yourself.

fold_left and fold_right differ in the direction the accumulator travels and in how much room they need. fold_left starts from the seed and walks toward the end, carrying the answer in an argument; that is the one to reach for when the result is a sum, a count or a string being built. List.rev is a fold in disguise, and @ copies its left argument, so appending repeatedly is the expensive way to build a list.

What goes wrong

The first mistake is reaching for List.hd on a list that may be empty. It raises Failure "hd" at run time, and the type system cannot tell a list with items from one without. Match on [] and x :: rest, or use List.nth_opt, and the empty case becomes a branch you had to write.

The second is a fold whose accumulator type drifts. List.fold_left (fun acc x -> acc + x) 0 is fine; put a string_of_int inside and the accumulator becomes a string, so the seed has to change too. When a fold is refused, write the accumulator type in a comment above the call and check that every branch answers that same type.

Try these next

• Map String.length over a list of words and print the lengths as one line.
• Filter a list of numbers to the even ones, then sum them with a fold.
• Write count item xs by hand with [] and ::, then compare it with a filter and a length.

Map, sort and fold on words

let words = ["pear"; "fig"; "apple"]

let () =
  print_endline (String.concat ", " (List.sort compare words));
  print_endline
    (string_of_int (List.fold_left (fun n w -> n + String.length w) 0 words))