Higher-Order Programming in OCaml

Meaning of "Higher-Order"

Higher-order functions either take other functions as input or return other functions as output (or both). Higher-order functions are also known as functionals, and programming with them could therefore be called functional programming.

map

map applies the function to each element.

Side Effects

1
2
3

let p x = print_int x; print_newline(); x + 1

let lst = map p [1; 2]

For example for this code snippet, the exact output is 2 1. This is because p 1 is not evaluated before map p 2 :: [], thus 2 is printed before 1.

To enforce strict evaluation, we can use let in notation:

let rec map f = function
  | [] -> []
  | h :: t -> let h' = f h in h' :: map f t

let lst2 = map p [1; 2]

And which is how List.map works.

filter
fold
- fold right. List.fold_right updates the accumulator from the rightmost endpoint of the list and treats the accumulator as the second argument. The evaluation is similar to an -> acc, an-1 -> acc, …, a1 -> acc.
- fold left. List.fold_left updates the accumulator from the leftmost endpoint, and treats the accumulator as the first argument. acc <- a1, acc <- a2, …, acc <- an.
Pipelining.