Edit

Recursion

There are three places recursion is commonly used: bindings, types, and modules.

Feature	Recursive	Non-recursive
Bindings	let rec fn = ...	let fn = ...
Types	type t = ...	type nonrec t = ...
Modules	module rec A ...	module A ...

Recursive Bindings

By default the name of a binding is not available for use on the right side of that binding. This applies to all let bindings, including function definitions. This behavior is required for Binding Shadowing to work:

let x = 10;
/* If bindings were recursive by default this would form a cycle and break */
let x = x + 10;

The natural way to write a recursive function will have an error:

let infiniteRecursion = () => {
  /* Error: Unbound value infiniteRecursion */
  infiniteRecursion();
};

Opt-in to a recursive binding using the rec keyword:

let rec infiniteRecursion = () => {
  infiniteRecursion();
};

Mutual Recursion

Mutually recursive functions use the and keyword:

let rec function1 = () => {
  function2();
}
and function2 = () => {
  function3();
}
and function3 = () => {
  function1();
};

• Note: The and keyword is not specific to recursion, it can be used without the rec keyword. Doing so would cause all bindings to be created simultaneously but not visible to each other.

Recursive Types

Types, unlike bindings, are recursive by default. This is because it is common for types to be recursive and uncommon for types to be shadowed. A recursive type could be used to define a binary tree:

type tree =
  | Leaf
  | Node(tree, tree);

Opt-out of recursive types using the nonrec keyword:

type t = string;
type nonrec t = list(t);

/* t is now list(string) */
let x: t = ["hello", "world"];

Mutually Recursive Types

Types can be mutually recursive just like bindings using the and keyword:

type node = {
  value: string,
  edges: list(edge),
}
and edge = {
  weight: int,
  next: node,
};

Mutually Recursive Modules

Sometimes functions will be organized across modules and both modules need functions from each other. Use the module rec and and keywords for this kind of mutual recursion.

Note: Recursive modules require an explicit module type annotation.

module type X = {
  let x: unit => int;
  let y: unit => int;
};

module rec A: X = {
  let x = () => 1;
  let y = () => B.y() + 1;
}
and B: X = {
  let x = () => A.x() + 2;
  let y = () => 2;
};