Map, filter and fold

List.fold_left ( - ) 10 [1; 2; 3] gives 4, and List.fold_right ( - ) [1; 2; 3] 10 gives -8: the same list, the same function, the same start value, two answers. Most loops over a list are a map, a filter or a fold, and knowing which fold you hold decides both the answer and whether a list of a million elements fits on the stack.

You will replace hand-written recursion with the List module’s higher-order functions, explain how the two folds differ, write map and filter as folds and merge two passes into one, and build pipelines over lists with |>.

Map, filter and their relatives replace the usual recursions

Most recursive functions over a list do one of a few jobs: change every element, keep some of them, or both. The List module has a higher-order functionhigher-order function: A function that takes another function as an argument or returns one, such as List.map, which applies the function it is given to every element of a list. for each, a function that takes another function, the step, as its argument and does the walking itself. The session runs each one on four students’ marks:

from session import toplevel

# Higher-order functions of the List module replace the usual recursions: map transforms every element, filter keeps
# some, filter_map does both with a function that may fail, partition splits a list in two and concat_map joins the
# lists a function returns.
toplevel("""
let marks = [("asha", 72); ("ravi", 35); ("meera", 91); ("kiran", 58)];;
List.map snd marks;;
List.filter (fun (_, m) -> m >= 40) marks;;
List.partition (fun (_, m) -> m >= 60) marks;;
let raw = ["72"; "absent"; "91"; ""; "58"];;
List.filter_map int_of_string_opt raw;;
List.map int_of_string_opt raw;;
List.concat_map (fun (name, m) -> if m >= 90 then [name; "distinction"] else [name]) marks;;
""")

$ ocaml
OCaml version 5.5.1
Enter #help;; for help.

# let marks = [("asha", 72); ("ravi", 35); ("meera", 91); ("kiran", 58)];;
val marks : (string * int) list =
  [("asha", 72); ("ravi", 35); ("meera", 91); ("kiran", 58)]
# List.map snd marks;;
- : int list = [72; 35; 91; 58]
# List.filter (fun (_, m) -> m >= 40) marks;;
- : (string * int) list = [("asha", 72); ("meera", 91); ("kiran", 58)]
# List.partition (fun (_, m) -> m >= 60) marks;;
- : (string * int) list * (string * int) list =
([("asha", 72); ("meera", 91)], [("ravi", 35); ("kiran", 58)])
# let raw = ["72"; "absent"; "91"; ""; "58"];;
val raw : string list = ["72"; "absent"; "91"; ""; "58"]
# List.filter_map int_of_string_opt raw;;
- : int list = [72; 91; 58]
# List.map int_of_string_opt raw;;
- : int option list = [Some 72; None; Some 91; None; Some 58]
# List.concat_map (fun (name, m) -> if m >= 90 then [name; "distinction"] else [name]) marks;;
- : string list = ["asha"; "ravi"; "meera"; "distinction"; "kiran"]

What each function did with the session’s marks:

List.filter_map int_of_string_opt read the marks typed as text and skipped "absent" and the empty string in one pass; a plain List.map gave [Some 72; None; Some 91; None; Some 58], which still needs a filter and an unwrap. Each of these functions keeps the order of the elements, and none of them changes the list it is given.

The two folds combine from opposite ends

A foldfold: Combining all the elements of a list into one value with a function and a start value; List.fold_left starts from the first element and List.fold_right from the last. combines all the elements of a list into one value, with a function that takes the result so far and one element. The manual defines List.fold_left f init [b1; …; bn] as f (… (f (f init b1) b2) …) bn, which starts from the first element, and List.fold_right f [a1; …; an] init as f a1 (f a2 (… (f an init) …)), which starts from the last. Step through both on [1; 2; 3] with subtraction:

from session import toplevel

# fold_left combines from the first element, fold_right from the last. With an operator that is not associative, such
# as subtraction, the two give different results; with :: one reverses the list and the other copies it.
toplevel("""
List.fold_left ( - ) 10 [1; 2; 3];;
List.fold_right ( - ) [1; 2; 3] 10;;
List.fold_left ( + ) 0 [1; 2; 3];;
List.fold_left (fun acc x -> x :: acc) [] [1; 2; 3];;
List.fold_right (fun x acc -> x :: acc) [1; 2; 3] [];;
(List.fold_left ( ^ ) "" ["a"; "b"; "c"], List.fold_right ( ^ ) ["a"; "b"; "c"] "");;
List.fold_left (fun (lo, hi) x -> (min lo x, max hi x)) (max_int, min_int) [72; 35; 91; 58];;
""")

$ ocaml
OCaml version 5.5.1
Enter #help;; for help.

# List.fold_left ( - ) 10 [1; 2; 3];;
- : int = 4
# List.fold_right ( - ) [1; 2; 3] 10;;
- : int = -8
# List.fold_left ( + ) 0 [1; 2; 3];;
- : int = 6
# List.fold_left (fun acc x -> x :: acc) [] [1; 2; 3];;
- : int list = [3; 2; 1]
# List.fold_right (fun x acc -> x :: acc) [1; 2; 3] [];;
- : int list = [1; 2; 3]
# (List.fold_left ( ^ ) "" ["a"; "b"; "c"], List.fold_right ( ^ ) ["a"; "b"; "c"] "");;
- : string * string = ("abc", "abc")
# List.fold_left (fun (lo, hi) x -> (min lo x, max hi x)) (max_int, min_int) [72; 35; 91; 58];;
- : int * int = (35, 91)

With ( - ) the answers were 4 and -8, because subtraction depends on the order. With ( + ) the order cannot matter, and with ( ^ ) both folds gave "abc", because joining strings is associative. Folding :: shows the directions most plainly: fold_left built [3; 2; 1], a reversed list, while fold_right rebuilt [1; 2; 3]. The last line carried a pair, the lowest and highest mark so far, and gave (35, 91) in one pass.

The two also differ in stack use. fold_left hands its result forward in a tail call, so it runs in one frame; fold_right cannot combine anything until it has reached the end, and keeps a frame waiting for every element. The manual says so in the documentation of fold_right: “Not tail-recursive”. The program below folds a million numbers both ways under a stack limited to 100,000 words:

from session import run, write

# fold_right must reach the end of the list before it can combine anything, so it keeps one frame per element;
# fold_left combines as it goes, in constant stack. Under a small stack limit only fold_right overflows.
write("folds.ml", """let () =
  let l = List.init 1_000_000 (fun i -> i mod 10) in
  let total =
    match Sys.argv.(1) with
    | "left" -> List.fold_left ( + ) 0 l
    | _ -> List.fold_right ( + ) l 0
  in
  Printf.printf "fold_%s over %d elements: %d\\n" Sys.argv.(1) (List.length l) total
""")
run("""
ocamlopt folds.ml -o folds
export OCAMLRUNPARAM=l=100000
./folds left
!./folds right
""")

$ ocamlopt folds.ml -o folds
$ export OCAMLRUNPARAM=l=100000
$ ./folds left
fold_left over 1000000 elements: 4500000
$ ./folds right
Fatal error: exception Stack_overflow
[exit status 2]

fold_left printed 4500000, and fold_right stopped with “Fatal error: exception Stack_overflow” and exit status 2.

Map and filter are folds, and two laws merge passes

A fold can rebuild a list, so map and filter are folds whose step adds an element in front of the result so far. fold_right is the natural choice, because it meets the elements from the last one and so builds the new list in the right order. The session writes both in one line each, then checks two laws on the list [3; 8; 1; 6; 4]:

from session import run, toplevel, write

# map and filter are folds that rebuild a list. Two laws hold for any pure functions: two maps equal one map of the
# composed function, and two filters equal one filter of both tests. The fused form builds one list instead of two.
toplevel("""
let map f l = List.fold_right (fun x acc -> f x :: acc) l [];;
let filter p l = List.fold_right (fun x acc -> if p x then x :: acc else acc) l [];;
let l = [3; 8; 1; 6; 4];;
(map (fun x -> x * 2) l, filter (fun x -> x > 3) l);;
(map (fun x -> x * 2) l = List.map (fun x -> x * 2) l, filter (fun x -> x > 3) l = List.filter (fun x -> x > 3) l);;
let f x = x + 1 and g x = x * 10;;
List.map f (List.map g l) = List.map (fun x -> f (g x)) l;;
let p x = x mod 2 = 0 and q x = x > 3;;
List.filter p (List.filter q l) = List.filter (fun x -> q x && p x) l;;
List.filter (fun y -> y > 20) (List.map g l) = List.filter_map (fun x -> let y = g x in if y > 20 then Some y else None) l;;
""")
write("fused.ml", """let words f =
  let before = Gc.minor_words () in
  let r = f () in
  (r, Gc.minor_words () -. before)

let () =
  let l = List.init 1000 Fun.id in
  let f x = x + 1 and g x = x * 10 in
  let a, w2 = words (fun () -> List.map f (List.map g l)) in
  let b, w1 = words (fun () -> List.map (fun x -> f (g x)) l) in
  Printf.printf "same result: %b\\n" (a = b);
  Printf.printf "two maps: %.0f words, one fused map: %.0f words\\n" w2 w1
""")
run("""
ocamlopt fused.ml -o fused
./fused
""")

$ ocaml
OCaml version 5.5.1
Enter #help;; for help.

# let map f l = List.fold_right (fun x acc -> f x :: acc) l [];;
val map : ('a -> 'b) -> 'a list -> 'b list = <fun>
# let filter p l = List.fold_right (fun x acc -> if p x then x :: acc else acc) l [];;
val filter : ('a -> bool) -> 'a list -> 'a list = <fun>
# let l = [3; 8; 1; 6; 4];;
val l : int list = [3; 8; 1; 6; 4]
# (map (fun x -> x * 2) l, filter (fun x -> x > 3) l);;
- : int list * int list = ([6; 16; 2; 12; 8], [8; 6; 4])
# (map (fun x -> x * 2) l = List.map (fun x -> x * 2) l, filter (fun x -> x > 3) l = List.filter (fun x -> x > 3) l);;
- : bool * bool = (true, true)
# let f x = x + 1 and g x = x * 10;;
val f : int -> int = <fun>
val g : int -> int = <fun>
# List.map f (List.map g l) = List.map (fun x -> f (g x)) l;;
- : bool = true
# let p x = x mod 2 = 0 and q x = x > 3;;
val p : int -> bool = <fun>
val q : int -> bool = <fun>
# List.filter p (List.filter q l) = List.filter (fun x -> q x && p x) l;;
- : bool = true
# List.filter (fun y -> y > 20) (List.map g l) = List.filter_map (fun x -> let y = g x in if y > 20 then Some y else None) l;;
- : bool = true
$ ocamlopt fused.ml -o fused
$ ./fused
same result: true
two maps: 6000 words, one fused map: 3000 words

The home-made map and filter gave [6; 16; 2; 12; 8] and [8; 6; 4], the same lists as List.map and List.filter. The first law, map fusion, says that mapping g and then f equals one map of the function that applies both: List.map f (List.map g l) = List.map (fun x -> f (g x)) l printed true. The second law joins two filters into one test, List.filter p (List.filter q l) = List.filter (fun x -> q x && p x) l, also true, and the last line turned a map followed by a filter into one List.filter_map, true again.

Laws like these let you rewrite a pipeline without changing its answer, as long as f, g, p and q are pure: no printing, no refs, no exceptions. The compiled program measured what fusion saves on 1,000 elements: two maps allocated 6,000 words, since the list in the middle is built and thrown away, and the fused map 3,000.

The three rewrites the session checked, side by side:

A pipeline lists the steps in the order the data takes them

x |> f is f x, so a chain of |> reads like a list of instructions: start from this data, keep these elements, take this part, combine. The session totals the passing marks both ways, as a pipeline and as nested calls. Step through the pipeline stage by stage:

from session import toplevel

# x |> f is f x, so a chain of |> lists the steps in the order the data goes through them. The nested form gives the
# same result written inside out.
toplevel("""
let marks = [("asha", 72); ("ravi", 35); ("meera", 91); ("kiran", 58)];;
marks |> List.filter (fun (_, m) -> m >= 40) |> List.map snd |> List.fold_left ( + ) 0;;
List.fold_left ( + ) 0 (List.map snd (List.filter (fun (_, m) -> m >= 40) marks));;
let passed = List.filter (fun (_, m) -> m >= 40) marks;;
List.fold_left ( + ) 0 (List.map snd passed) / List.length passed;;
marks |> List.sort (fun (_, a) (_, b) -> compare b a) |> List.map fst |> List.take 2;;
""")

$ ocaml
OCaml version 5.5.1
Enter #help;; for help.

# let marks = [("asha", 72); ("ravi", 35); ("meera", 91); ("kiran", 58)];;
val marks : (string * int) list =
  [("asha", 72); ("ravi", 35); ("meera", 91); ("kiran", 58)]
# marks |> List.filter (fun (_, m) -> m >= 40) |> List.map snd |> List.fold_left ( + ) 0;;
- : int = 221
# List.fold_left ( + ) 0 (List.map snd (List.filter (fun (_, m) -> m >= 40) marks));;
- : int = 221
# let passed = List.filter (fun (_, m) -> m >= 40) marks;;
val passed : (string * int) list =
  [("asha", 72); ("meera", 91); ("kiran", 58)]
# List.fold_left ( + ) 0 (List.map snd passed) / List.length passed;;
- : int = 73
# marks |> List.sort (fun (_, a) (_, b) -> compare b a) |> List.map fst |> List.take 2;;
- : string list = ["meera"; "asha"]

Both forms gave 221, but the nested call reads from the innermost function outwards, the opposite of the order in which the steps run. The average of the three passing marks was 73, because / on int drops the fraction of 221 / 3. Sorting by mark from the highest, keeping the names and taking two with List.take, new in OCaml 5.3, gave ["meera"; "asha"]: three stages after the data, each on its own line in a real program, each easy to test on its own.

Practise: map, filter, fold and pipelines

The questions use the session’s marks, folds and laws with new lists. Work out each result, or decide whether two forms are equal, before you check:

Interview questions

Warm-up (fresher to 2–5 years): how do fold_left and fold_right differ in OCaml?

Both combine the elements of a list into one value with a function and a start value. fold_left starts from the first element, f (f (f init a) b) c, and passes its result forward in a tail call, so it runs in constant stack space. fold_right starts from the last element, f a (f b (f c init)), and needs one stack frame per element, which the standard library documents as not tail-recursive. With an operator that depends on order the results differ: subtraction from 10 over [1; 2; 3] gives 4 from the left and -8 from the right. Folding :: from the left reverses a list, and from the right rebuilds it in order.

Two harder questions follow, about a total that overflows on a large import and about a parsing pipeline that keeps options around too long. For each, name the pass or the fold you would change first, then open its first step:

Key takeaways

• List.map, filter, partition, filter_map and concat_map replace the usual recursions over a list, keep the order of the elements and never change the list they are given.
• fold_left combines from the first element in constant stack, while fold_right combines from the last and needs a frame per element, so the two give different answers for subtraction and different stack use for long lists.
• map and filter are folds that rebuild a list, and for pure functions two maps or two filters can be fused into one pass that builds no list in the middle.
• A |> pipeline of map, filter and fold lists the steps in the order they run, and gives the same result as the nested calls.