Skip to content
Tutorials Center
My learning

Topics

Lesson 19 of 40 ยท Lists, Arrays and Records

Folding Lists: fold_left and fold_right

Understand folds, the universal list reducers in OCaml: fold_left versus fold_right, accumulators, building sum, max, reverse, map and filter, and choosing the right fold.

Many list functions follow one shape: start with an initial value and combine it with each element. Summing, counting, finding the maximum, reversing, even map and filter all fit. That shape is captured by a fold (in some languages called reduce). If you understand fold_left, you can read and write a large part of functional code.

fold_left

OCAML
val List.fold_left : ('acc -> 'a -> 'acc) -> 'acc -> 'a list -> 'acc

It takes a function f, an initial accumulator init and a list. It processes elements from left to right:

TEXT
fold_left f init [a; b; c] = f (f (f init a) b) c

Example: the sum.

OCAML
# List.fold_left (fun acc x -> acc + x) 0 [1; 2; 3; 4];;
- : int = 10
# List.fold_left (+) 0 [1; 2; 3; 4];;
- : int = 10

A step-by-step trace:

step acc x new acc
start 0 0
1 0 1 1
2 1 2 3
3 3 3 6
4 6 4 10

The function receives the accumulator first, then the element. fold_left is tail-recursive, so it works on very long lists.

Many functions are folds

OCAML
let sum = List.fold_left (+) 0
let product = List.fold_left ( * ) 1
let count = List.fold_left (fun n _ -> n + 1) 0
let maximum = function
  | [] -> invalid_arg "maximum"
  | x :: rest -> List.fold_left max x rest

Define them with a final parameter if the compiler complains about weak types (let sum l = List.fold_left (+) 0 l).

OCAML
let rev l = List.fold_left (fun acc x -> x :: acc) [] l
# rev [1; 2; 3];;
- : int list = [3; 2; 1]

rev shows how the accumulator can be a list: each element is consed onto the front, reversing the order.

The accumulator can be anything: a tuple, a record, a map. Compute the sum and count at once:

OCAML
let sum_and_count l =
  List.fold_left (fun (s, c) x -> (s + x, c + 1)) (0, 0) l

# sum_and_count [10; 20; 30];;
- : int * int = (60, 3)

Building a frequency table

OCAML
let count_words words =
  List.fold_left
    (fun acc w ->
      let n = try List.assoc w acc with Not_found -> 0 in
      (w, n + 1) :: List.remove_assoc w acc)
    [] words

For a long list use a Hashtbl or a Map; this version is clear but quadratic.

fold_right

OCAML
val List.fold_right : ('a -> 'acc -> 'acc) -> 'a list -> 'acc -> 'acc

fold_right processes from the right, and the argument order is different: element first, accumulator second, list before the initial value.

TEXT
fold_right f [a; b; c] init = f a (f b (f c init))

It matches the shape of a list exactly: replace each :: with f and [] with init:

OCAML
# List.fold_right (fun x acc -> x :: acc) [1; 2; 3] [];;
- : int list = [1; 2; 3]
# List.fold_right (fun x acc -> x ^ acc) ["a"; "b"; "c"] "";;
- : string = "abc"

This is the right choice for building lists in order, such as map and filter:

OCAML
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 []

Beware: fold_right is not tail-recursive in the classical implementation, so on lists with hundreds of thousands of elements, use fold_left and List.rev, or check your OCaml version's notes.

Does the direction matter?

For associative operations with a neutral start (+, *, max), both give the same answer. For others, the results differ:

OCAML
# List.fold_left (-) 100 [1; 2; 3];;
- : int = 94
# List.fold_right (-) [1; 2; 3] 100;;
- : int = -98

The first computes ((100 - 1) - 2) - 3. The second computes 1 - (2 - (3 - 100)), which is -98.

fold_left vs fold_right at a glance

fold_left fold_right
direction left to right right to left
function arguments acc x x acc
stack constant (tail-recursive) grows with the list
good for counting, sums, reversing rebuilding lists in order

Other folds and relatives

  • List.fold_left2 and List.fold_right2 fold over two lists.
  • List.iter is a fold that returns unit.
  • Array.fold_left, String.fold_left (OCaml 4.13+), Hashtbl.fold, Map.fold follow the same idea.
  • List.fold_left plus Fun.flip swaps argument order when needed.

When not to fold

A fold can express everything, but that is not a reason to use it for everything. If the standard library has List.exists, List.filter or List.map, use it: the name tells the reader what you mean. Use a fold when you need a result no ready-made function gives you.

A stand-in: folds on arrays

JavaScript's reduce is fold_left, and reduceRight is like fold_right with the arguments swapped. Run the stand-in to see the order for subtraction.

JS Stand-in: left and right folds

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is List.fold_left (+) 0 [1; 2; 3]?

    It adds each element to the accumulator starting from 0, giving 6.
  2. 2. What is the order of the function arguments in fold_left's function?

    fold_left calls f acc x; fold_right calls f x acc.
  3. 3. What does List.fold_left (fun acc x -> x :: acc) [] [1; 2; 3] produce?

    Each element is consed onto the accumulator, so the list is reversed.
  4. 4. Why prefer fold_left on very long lists?

    fold_right has to remember pending calls, while fold_left runs like a loop.

Summary

  • A fold reduces a list to one value with an accumulator.
  • fold_left f init l goes left to right and is tail-recursive; f takes acc then element.
  • fold_right f l init goes right to left, mirrors list structure, and takes element then acc.
  • Sum, count, maximum, reverse, even map and filter can be written as folds.
  • Prefer a specific library function when one exists.

Next: Sorting and association lists