On this page

OCaml Higher-Order Functions: map, filter, fold_left/fold_right

Published on July 21, 2026

Enrico Hochkoeppler Profile

By Enrico Hochkoeppler

Web Developer & TutoriaLibre Founder

A higher-order function is one that takes another function as an argument, returns a function as its result, or both. map, filter, and the two directions of fold are the three most important higher-order functions in everyday OCaml, because between them they cover almost every way a list ever needs to be processed: transforming every element, keeping only some of them, or combining them all into a single result.

Why Higher-Order Functions Exist: Factoring Out Repetition​

Consider two functions that, on the surface, look unrelated:


let rec double_all = function

  | [] -> []

  | h :: t -> (h * 2) :: double_all t



let rec is_even_all = function

  | [] -> []

  | h :: t -> (h mod 2 = 0) :: is_even_all t

Both functions have identical structure: handle the empty list, and otherwise apply some operation to the head and recurse on the tail. The only real difference is which operation gets applied to each head — multiplying by two in one case, checking evenness in the other. Recognizing and factoring out that shared structure, rather than writing it over and over with a different operation plugged in each time, is exactly what a higher-order function does:


let rec map f = function

  | [] -> []

  | h :: t -> f h :: map f t



let double_all = map (fun x -> x * 2)

let is_even_all = map (fun x -> x mod 2 = 0)

map takes the varying part — the function to apply — as a parameter, so the shared recursive structure only ever needs to be written once. This is the general idea behind higher-order functions: instead of writing many nearly-identical functions, write one function parameterized by whatever varies between them.

map: Transforming Every Element​

map f lst applies f to every element of lst, producing a new list of the results, in the same order and with the same length as the original:


# List.map (fun x -> x * x) [1; 2; 3; 4];;

- : int list = [1; 4; 9; 16]

Its type, ('a -> 'b) -> 'a list -> 'b list, is worth reading carefully: the input list's element type 'a and the output list's element type 'b don't have to match, since f is free to transform an element into a completely different type — turning a list of numbers into a list of strings, for instance.

filter: Keeping Only Some Elements​

filter p lst keeps exactly the elements of lst for which the predicate p returns true, discarding the rest, without changing the type of the elements or their relative order:


# List.filter (fun x -> x mod 2 = 0) [1; 2; 3; 4; 5; 6];;

- : int list = [2; 4; 6]

Its type, ('a -> bool) -> 'a list -> 'a list, reflects this directly: since filter only ever removes elements, it can never need to produce a different element type than it started with.

Building Toward fold: A Combining Function​

map and filter both look at one element at a time, in isolation. Combining every element of a list into a single result — summing a list of numbers, or concatenating a list of strings — needs something slightly different:


let rec sum = function

  | [] -> 0

  | h :: t -> h + sum t



let rec concat = function

  | [] -> ""

  | h :: t -> h ^ concat t

Once again, the shared structure between these two functions is unmistakable: an empty-list case returning some starting value (0 versus ""), and a non-empty case combining the head with the recursive result on the tail, using some operator (+ versus ^). Factoring out both the starting value and the combining operator produces exactly the shape of fold_right:


let rec fold_right f lst init =

  match lst with

  | [] -> init

  | h :: t -> f h (fold_right f t init)

fold_right ( + ) [1; 2; 3] 0 computes 1 + (2 + (3 + 0)); fold_right ( ^ ) ["a"; "b"; "c"] "" computes "a" ^ ("b" ^ ("c" ^ "")). A useful way to picture what fold_right f lst init does in general: take the list, replace every :: with f, and replace the final [] with init.

fold_left: The Tail-Recursive Alternative​

fold_right has a real cost: it isn't tail-recursive, since combining the head with the recursive result has to wait until that recursive call returns. fold_left restructures the same idea to avoid this, by folding the head into the accumulator immediately, before recursing, rather than after:


let rec fold_left f acc lst =

  match lst with

  | [] -> acc

  | h :: t -> fold_left f (f acc h) t

fold_left ( + ) 0 [1; 2; 3] computes ((0 + 1) + 2) + 3 — building up its result from the left, rather than the right. Because there's no work left to do after the recursive call returns, fold_left runs in constant stack space, making it the usual first choice for processing very long lists.

Why fold_left and fold_right Can Disagree​

For an operator like + that's both associative and commutative, it genuinely doesn't matter which direction a fold processes a list in — the answer comes out the same either way. That stops being true the moment the combining operator isn't associative, and subtraction makes the difference vivid:


# List.fold_right (-) [3; 2; 1] 0;;

- : int = 2   (* 3 - (2 - (1 - 0)) *)

# List.fold_left (-) 0 [3; 2; 1];;

- : int = -6  (* ((0 - 3) - 2) - 1 *)

Both calls process the exact same list with the exact same operator, and get genuinely different, both entirely correct, answers — because they're computing different expressions. fold_right associates from the rightmost element outward; fold_left associates from the leftmost element outward, with the initial accumulator sitting on the opposite side in each case. This is a detail worth internalizing early: reaching for whichever fold happens to be more convenient, without checking whether the combining operation actually commutes and associates freely, is a subtle and easy way to introduce a real bug.

Building Other Functions on Top of Fold​

Both map and filter can themselves be expressed directly in terms of fold, which is a good way to see just how expressive the fold pattern really is:


let map f lst = List.fold_right (fun x acc -> f x :: acc) lst []

let filter p lst = List.fold_right (fun x acc -> if p x then x :: acc else acc) lst []

let length lst = List.fold_left (fun acc _ -> acc + 1) 0 lst

Whether writing a new list function this way, versus writing it directly as a plain recursive function over [] and h :: t, is the better choice is a genuine judgment call. A direct recursive definition is often easier to read at a glance; a fold-based definition guarantees the underlying recursive traversal itself can't be written incorrectly, since that part is handled once, inside fold_left or fold_right itself, rather than being re-derived by hand every time.

Key Takeaways​

Found this helpful? Share the knowledge...

... or support this project to keep it alive!

Buy Me a Coffee

Previous

Parametric Polymorphism

Next

Function Composition & Pipe Operator