Functions, and functions that call themselves

A function is a value

let double x = x + x defines a function: the name, then the parameters, then the expression that answers. Applying it is juxtaposition — no brackets and no commas — so double 21 is the call and add 40 2 passes two arguments. A function that takes a function is no harder to write than one that takes a number.

Because functions are ordinary values, one can be handed to another: apply_twice f x runs f twice on x, and it does not care what f is as long as it accepts and answers the same type. That is the idea behind the list functions a few chapters from here. The compiler works out that f and x must share a type, and says so in the inferred signature.

Recursion needs rec, and a stopping case

A function that calls itself must be introduced with let rec, because the name does not exist until its own definition is finished. Without the keyword the compiler answers that the value is unbound, which is a clearer complaint than a wrong answer would be.

Recursion always has the same two parts: a case that answers without calling itself, and a step that calls itself on something smaller. factorial stops at 1 and multiplies its way down; the stopping case is the part the compiler cannot check for you, so it is the part worth writing first.

Currying: arguments arrive one at a time

Every function in OCaml takes one argument. let add a b = a + b is a function that takes a and answers a function that takes b; the call add 40 2 is two applications in a row. That is called currying, and it is why a partial application is useful: let add_ten = add 10 is a real function waiting for the second number.

The type tells the same story: add : int -> int -> int has two arrows because there are two arguments. When the compiler reports a mismatch, read the arrows from left to right — the types before the last arrow are what the function expects, and the last is what it answers.

Recursion is checked like any other call. The recursive name is only in scope inside the body when the definition says rec, and the compiler does not prove that the argument gets smaller. The base case and the step are a contract you write; the type checker only guarantees that every call has the right shape.

What the compiler knows about a function

When you define let double x = x + x, the compiler gives it the type int -> int without being told. It knows + works on two ints here, so x must be an int and the answer is an int. Change the body to x +. x and the same definition becomes float -> float; nothing else in the file needs to change.

That is why an annotation is rarely needed on a small function, and why the inferred type is worth reading when a definition is refused. The type is the compiler’s summary of what the body does with its arguments — a compact answer to the question "what did I actually write?".

What goes wrong

The missing rec is the first: the compiler says Unbound value factorial at the recursive call, even though the name is right there on the line above. The definition is not in scope inside itself until rec says it is.

The second is a base case that is never reached. if n = 0 then 0 else n + sum_to (n + 1) compiles, has the right type, and runs until the stack gives out. The checker cannot see the direction of the step; trace the argument by hand for two calls and check that it moves toward the case that stops.

Try these next

• Write square and pass it to apply_twice; predict the answer before running.
• Turn add into add_ten by applying one argument, then call it on three different numbers.
• Write sum_to n with an accumulator and compare it with a version that adds on the way back up.

A recursive function

let rec power base exponent =
  if exponent = 0 then 1
  else base * power base (exponent - 1)

let () = print_endline (string_of_int (power 2 10))