Skip to content
Tutorials Center
My learning

Topics

Lesson 13 of 40 ยท Functions and Recursion

Higher-Order Functions in OCaml

Write and use functions that take or return functions in OCaml: map, filter, function composition, returning functions, callbacks, and building your own higher-order helpers.

A higher-order function is a function that takes another function as an argument, returns a function, or both. In OCaml, functions are first-class values, so this is not an advanced feature but the normal way of writing code. Loops in other languages usually become calls to a higher-order function in OCaml.

Three ways to use functions as data

Take a function List.map f xs
Return a function make_adder 5
Combine functions compose f g

All three appear in everyday OCaml.

1 / 2

Taking a function as an argument

Suppose you want to apply an operation twice. Without higher-order functions you would write a function for each operation. With them, the operation is a parameter:

OCAML
let apply_twice f x = f (f x)

# apply_twice (fun n -> n + 3) 10;;
- : int = 16
# apply_twice String.uppercase_ascii "ab";;
- : string = "AB"
# apply_twice (fun s -> s ^ "!") "hey";;
- : string = "hey!!"

Its type is ('a -> 'a) -> 'a -> 'a: whatever the function, its input and output types must match, since the result is fed back into it.

Writing map and filter yourself

The functions below are the heart of functional programming. Reading how they are built shows what the standard library does:

OCAML
let rec map f = function
  | [] -> []
  | x :: rest -> f x :: map f rest

let rec filter pred = function
  | [] -> []
  | x :: rest ->
      if pred x then x :: filter pred rest else filter pred rest

(rec and the list patterns are explained in Recursion and Lists.) Their types:

OCAML
val map : ('a -> 'b) -> 'a list -> 'b list
val filter : ('a -> bool) -> 'a list -> 'a list

map can change the element type ('a to 'b); filter cannot.

Use them:

OCAML
# map String.length ["one"; "three"; "ox"];;
- : int list = [3; 5; 2]
# filter (fun n -> n > 2) [1; 2; 3; 4];;
- : int list = [3; 4]

Returning functions

A function can build and return another function. Together with closures this gives you configurable behavior:

OCAML
let multiplier k = fun x -> x * k

let triple = multiplier 3
let tenfold = multiplier 10

# triple 7;;
- : int = 21

Here is a slightly richer example: a function that makes a "validator".

OCAML
let in_range lo hi = fun x -> lo <= x && x <= hi

let is_percent = in_range 0 100

# List.filter is_percent [-5; 0; 50; 100; 101];;
- : int list = [0; 50; 100]

Function composition

Composing two functions gives a new function:

OCAML
let compose f g = fun x -> f (g x)

let shout = compose (fun s -> s ^ "!") String.uppercase_ascii

# shout "hello";;
- : string = "HELLO!"

The type is ('b -> 'c) -> ('a -> 'b) -> 'a -> 'c. The standard library has Fun.compose in recent versions (OCaml 5.2) and the idiom you will see everywhere is the pipe |>, which applies data to a chain of functions without defining new ones. Both are two sides of the same idea.

Functions in data structures

Functions can be stored in lists, tuples and records:

OCAML
let operations = [
  ("double", (fun x -> x * 2));
  ("negate", (fun x -> -x));
  ("square", (fun x -> x * x));
]

let () =
  List.iter
    (fun (name, f) -> Printf.printf "%s 7 = %d\n" name (f 7))
    operations

This prints double 7 = 14, negate 7 = -7, square 7 = 49. The tuple pattern in the fun takes each pair apart. Printf.printf is formatted printing; %s takes a string and %d an int.

Callbacks and the "strategy" pattern

Passing a function lets the caller decide behavior. For example, a sort that takes a comparison function:

OCAML
let words = ["pear"; "fig"; "banana"]

let by_length a b = compare (String.length a) (String.length b)
let sorted = List.sort by_length words
(* ["fig"; "pear"; "banana"] *)

No class, no interface: the "strategy" is just a function.

Useful higher-order helpers from the standard library

Function Type (simplified) Use
List.map ('a -> 'b) -> 'a list -> 'b list transform every element
List.filter ('a -> bool) -> 'a list -> 'a list keep elements that satisfy a test
List.iter ('a -> unit) -> 'a list -> unit run an effect for each element
List.fold_left ('acc -> 'a -> 'acc) -> 'acc -> 'a list -> 'acc reduce a list to one value
List.exists ('a -> bool) -> 'a list -> bool does any element pass?
Fun.flip ('a -> 'b -> 'c) -> 'b -> 'a -> 'c swap the first two arguments

You will meet them all in the list module and folds lessons.

A stand-in: map, filter and compose

The stand-in implements the same helpers recursively on JavaScript arrays, so you can check they behave like their OCaml namesakes.

JS Stand-in: write map and filter yourself

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 a higher-order function?

    Higher-order functions treat functions as values: they accept them or produce them.
  2. 2. What is the type of List.map?

    map applies a function that may change the element type.
  3. 3. What does let triple = multiplier 3 create if multiplier k = fun x -> x * k?

    Partial application plus a closure produces a function that remembers k = 3.
  4. 4. Why does apply_twice have the type ('a -> 'a) -> 'a -> 'a?

    f is applied to its own output, which forces its input and output types to be equal.

Summary

  • Higher-order functions take or return functions; OCaml treats functions as ordinary values.
  • map, filter and similar helpers replace many loops.
  • Closures let a returned function remember its configuration.
  • Functions can sit in lists, tuples and records, and be used as callbacks.
  • Composition and the pipe build new behavior from small functions.

Next: Recursion