Lists and the helpers that walk them

One type, any number of values

[3; 12; 5] is a list of three ints. The separator is a semicolon, not a comma: a comma makes a tuple, which is one value with parts, while a list is any number of values that all have the same type. [1 .. 5] builds a range, [1 .. 10] does the same over ten, and [] is the empty list.

A list is a linked list, which is why taking the front is cheap and reaching the tenth element is not: List.item 9 walks ten cells. At the sizes in this course that never matters, and it is worth knowing anyway, because it explains why F# code is written as one pass over a list rather than as an index loop.

Change every value, or keep some

List.map applies a function to every value and keeps the length. List.filter keeps the values whose test answers true, so the answer is the same length or shorter. Neither changes the list it was given: each answers a new list and the old one is still there.

The test is a function returning bool. When it is short enough not to deserve a name, it is written inline as a lambda: fun n -> n < 10. Read that aloud as "a function of n that is true when n is less than ten".

The = inside is comparison, not assignment — the same sign as in the second chapter, told apart by where it sits. n % 2 = 0 is true for an even number, and that is the whole of the test for one.

Two helpers and three lists

let nums = [3; 12; 5; 20; 1]

let doubled = List.map (fun n -> n * 2) nums
let small = List.filter (fun n -> n < 10) nums
let evens = List.filter (fun n -> n % 2 = 0) [1 .. 10]

A list is built from the front

The bracket syntax hides a simpler shape. [1; 2; 3] is shorthand for 1 :: 2 :: 3 :: [], where :: puts one value on the front of an existing list and [] is the empty list. That is the whole data structure: a value and the rest, or nothing at all.

Because that is the shape, a function over a list can be written as two cases. [] is the stopping point, and head :: tail names the first value and the remainder. A recursive function handles the head, calls itself on the tail, and the list gets shorter until it is empty. This is also why List.head is cheap and List.item 9 is not: the tenth value is nine links away.

Lists are immutable, so neither helper changes the list you passed in. They build a new spine and share the values, so an old binding still prints what it did before.

Map, ranges and the cost of a shape

List.map takes a function from one type to another, so a list of ints can become a list of strings, tuples or records. List.filter cannot: its function must answer bool, and the result keeps the same element type, only fewer of them. Keeping those two signatures apart explains most of the type errors you will meet here.

Both preserve order and walk the list once. List.choose combines the two jobs when the function returns an option, which is the subject of a later chapter.

A range is shorthand for a list you could have written out: [1 .. 5] is five values, and [1 .. 2 .. 9] uses the middle value as a step, answering the odd numbers. Appending with @ walks the whole left list to find its end, while :: allocates one cell at the front. That is why F# code often builds a list backwards and reverses it once.

Try these next

• Write 1 :: [2; 3] and [1] @ [2; 3], and compare the results.
• Map a list of names to their lengths, then sum the lengths.
• Write a recursive total with [] and head :: tail, and check it against List.sum.