# Value restriction and mutually recursive functions

**URL:** https://discuss.ocaml.org/t/value-restriction-and-mutually-recursive-functions/2432
**Category:** Learning
**Created:** [August 10, 2018, 3:52pm UTC](https://discuss.ocaml.org/t/value-restriction-and-mutually-recursive-functions/2432 "2018-08-10T15:52:26Z")
**Posts on this page:** 1
**Showing post:** 2

<div class="post-metadata">

### Author: ![yallop](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/yallop/32/517_2.png) [@yallop](https://discuss.ocaml.org/u/yallop)
#### Post date: [August 10, 2018, 9:20pm UTC](https://discuss.ocaml.org/t/value-restriction-and-mutually-recursive-functions/2432/2 "2018-08-10T21:20:45Z")

</div>

The short answer is that OCaml has the restriction that a recursive function `let rec f = e₁ in e₂` cannot be _polymorphically-recursive_: that is, it can only be used with a single type within its own definition (`e₁`) . Mutually-recursive functions `let f₁ = e₁ and f₂ = e₂ ...` have a corresponding restriction: every function `fᵢ` in the group can only be used with a single type in the definitions `eᵢ`. The reason for the restriction is that type inference for polymorphic recursion is undecidable in the general case.

However, although type _inference_ for polymorphic recursion is undecidable, type _checking_ (i.e. when the types are already known) is fine, so the second program will pass type checking if `aux` is annotated with a suitable polymorphic type. The following is accepted:

```ocaml
let rec aux : 'a. 'a -> int = fun x -> 100
and main () = (aux 1) + (aux true)

```

Fritz Henglein’s 1993 paper [Type inference with polymorphic recursion](https://suif.stanford.edu/~brm/reading/p253-henglein.pdf) is the place to look for the details about undecidability. Most references on ML type inference, from Milner’s 1978 [paper](https://www.sciencedirect.com/science/article/pii/0022000078900144) to Pierce’s [book](https://www.cis.upenn.edu/~bcpierce/tapl/) (end of chapter 22) are likely to touch on the restriction briefly.

---

_[View the full topic](https://discuss.ocaml.org/t/value-restriction-and-mutually-recursive-functions/2432)._