Iteration
OCaml has no built-in loop construct. Instead, repetition is modeled with two recursive patterns: one for when you know how many steps to take, and one for when you need to keep going until a condition is met.
Two kinds of repetition
In languages with loops, you typically choose between for (known count) and while (condition-based). In OCaml, the same distinction exists but is expressed through two higher-order functions: iter for a fixed number of applications, and first for searching until a predicate holds.
Both are tail recursive, so neither will overflow the stack. The key difference is that iter always terminates, because the count decrements to zero, while first may diverge if the predicate never becomes true.
Definite iteration: iter
iter f n start applies f exactly n times to start, chaining the output of each call as the input to the next. When n reaches zero, the accumulated value is returned. The number of steps is decided before the computation begins.
Because each call passes the result of f start forward, iter is tail recursive. The stack frame is reused on every step, so it can safely run for any number of iterations.
Partial application makes iter very flexible. You can fix f in advance to create a specialized repeater, leaving n and start open for the caller to supply.
let rec iter (f : int -> int) (n : int) (start : int) = if n < 1 then start else iter f (n - 1) (f start) (* iter (fun a -> a * 2) 3 1 step 1: 1 -> 2 step 2: 2 -> 4 step 3: 4 -> 8 result: 8 *) (* Raise x to the power n *) let power x n = iter (fun a -> a * x) n 1 power 2 10 (* 1024 *)
Indefinite iteration: first
first pred start increments start by one on each step until pred start returns true, then returns that value. The number of steps is not known in advance; it depends entirely on when the predicate first holds.
Like iter, first is tail recursive. But unlike iter, it can diverge: if pred is never true, the function runs forever. This is the OCaml equivalent of a while loop that never exits.
Always verify that the predicate will eventually be satisfied for any valid input. A predicate that can never become true turns first into an infinite loop.
let rec first (pred : int -> bool) (start : int) = if pred start then start else first pred (start + 1) (* first (fun k -> k * k > 15) 1 k=1: 1 > 15? no k=2: 4 > 15? no k=3: 9 > 15? no k=4: 16 > 15? yes -> return 4 *) (* Natural square root: first k where k^2 exceeds n, then step back by one *) let sqrt x = (first (fun k -> k * k > x) 1) - 1 sqrt 8 (* 2, since floor(sqrt(8)) = 2 *) sqrt 25 (* 5 *)
Building from iter and first
Because both functions take a step function or predicate as an argument, they combine well with partial application. You can define domain-specific iteration patterns by fixing the function argument and leaving the count or starting point open.
(* Double a number n times *) let double_n_times = iter (fun x -> x * 2) double_n_times 4 1 (* 16 *) (* Increment by a fixed step n times *) let count_by step = iter (fun x -> x + step) let count_by_3 = count_by 3 count_by_3 5 0 (* 15 *) (* Find the first multiple of n at or above start *) let first_multiple_of n = first (fun x -> x mod n = 0) first_multiple_of 7 50 (* 56 *)
iter and first are not built into OCaml. They are ordinary functions you define. The same is true of the looping patterns in the standard library. Once you understand how to build them, you can design your own iteration abstractions for any domain.