Higher-Order Functions

Functions as values

Every function in OCaml has a type. The type of a function that takes an int and returns an int is int -> int. A function that takes such a function and applies it is a higher-order function, with type (int -> int) -> int -> int.

This is not a special mechanism. It follows directly from functions being values. You can store a function in a variable, pass it as an argument, and return it just like any other value.

The function apply takes any function f and a value x, and returns f x. Its type is ('a -> 'b) -> 'a -> 'b. The type variables 'a and 'b mean it works for any types, so the same apply works whether f is a string function or an integer function.

apply.ml

let apply f x = f x
(* val apply : ('a -> 'b) -> 'a -> 'b *)

let square x = x * x

apply square 5              (* 25 *)
apply (fun x -> x * 3) 5   (* 15 *)
apply String.length "hello" (* 5 *)

map: transforming every element

List.map takes a function and a list, and returns a new list where every element has been transformed by that function. The input list and output list always have the same length. The original list is not modified.

The type is ('a -> 'b) -> 'a list -> 'b list. The function can change the type of each element, for example turning a list of integers into a list of strings.

map.ml

let nums = [1; 2; 3; 4; 5]

List.map (fun x -> x * 2) nums
(* [2; 4; 6; 8; 10] *)

List.map (fun x -> x * x) nums
(* [1; 4; 9; 16; 25] *)

List.map string_of_int nums
(* ["1"; "2"; "3"; "4"; "5"] *)

filter: selecting elements

List.filter takes a predicate function and a list, and returns a new list containing only the elements for which the predicate returns true. The output list can be shorter than the input, but each element in the output appears in the same order as in the input.

filter.ml

let nums = [1; 2; 3; 4; 5; 6]

List.filter (fun x -> x mod 2 = 0) nums
(* [2; 4; 6] *)

List.filter (fun x -> x > 3) nums
(* [4; 5; 6] *)

(* Partial application makes filters reusable *)
let positives = List.filter (fun x -> x > 0)
positives [-1; 2; -3; 4]  (* [2; 4] *)

fold_left: reducing a list to a value

List.fold_left walks a list from left to right, carrying an accumulator through each step. You provide the starting value for the accumulator and the function to combine the accumulator with each element. At the end, you get the final accumulated result.

The type is ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a. The accumulator starts as 'a, each element is 'b, and the combination function produces the next 'a. Summing a list of integers is the simplest example, but fold can compute anything that can be expressed as a running accumulation.

Both map and filter can be expressed in terms of fold_left. Fold is the most fundamental of the three. Map and filter are specialized folds that happen to be common enough to deserve their own names.

Key insight

When you find yourself writing a recursive function that carries an accumulator and walks a list, it is almost certainly a fold in disguise.

fold.ml

let nums = [1; 2; 3; 4; 5]

(* Sum *)
List.fold_left (+) 0 nums  (* 15 *)

(* Product *)
List.fold_left ( *) 1 nums  (* 120 *)

(* Maximum *)
List.fold_left max Int.min_int nums  (* 5 *)

(* Build a new list, equivalent to map *)
List.fold_left
  (fun acc x -> acc @ [x * 2]) [] nums
(* [2; 4; 6; 8; 10] *)

Chaining with the pipe operator

The |> operator passes a value from left to right through a sequence of functions. It reads naturally as a pipeline: start with data, then transform it step by step. Each step is often a partially applied higher-order function.

pipe.ml

(* Without pipe, read inside-out *)
List.fold_left (+) 0
  (List.map (fun x -> x * x)
    (List.filter (fun x -> x mod 2 = 0) [1;2;3;4;5]))

(* With pipe, read top to bottom *)
[1; 2; 3; 4; 5]
|> List.filter (fun x -> x mod 2 = 0)  (* [2; 4] *)
|> List.map    (fun x -> x * x)          (* [4; 16] *)
|> List.fold_left (+) 0                  (* 20 *)

The dependency injection parallel

In object-oriented programming, dependency injection is the practice of passing a dependency (an object, a service, a strategy) into a class rather than hardcoding it. The class does not decide what behavior to use. It receives that behavior from outside, which makes it testable and composable.

Higher-order functions are the same idea applied to functions. Instead of hardcoding a behavior inside a function, you accept that behavior as an argument. The caller decides what to do; the function decides how to iterate, fold, or transform. The principle is identical. Only the medium is different: objects in OOP, functions in OCaml.

di_parallel.ml

(* The behavior is injected as a function argument *)
let transform_all f items =
  List.map f items

(* The caller decides what transformation to apply *)
transform_all (fun x -> x * 2) [1; 2; 3]
transform_all String.uppercase_ascii ["a"; "b"]

(* transform_all does not care what f does.
   It only knows how to apply f to each element.
   The behavior (what to do) comes from outside. *)