Anonymous recursive functions in OCaml

Question

How do you make an anonymous recursive function (something simple for example factorial n?) I have heard it is possible but no idea how to make it work in OCaml.

let a =
  fun x -> ....

I just don't know how to keep it going...

Answer 1

There is also an "intuitive" way to accomplish anonymous recursion without resorting to Y combinators.

It makes use of a let binding to store the value of a lambda that accepts itself as an argument, so that it can call itself with itself as the first parameter, like so:

let fact = (let fact0 = (fun self n -> if n < 2 then 1 else n * self self (n - 1)) in (fun n -> fact0 fact0 n));;

It's anonymous only to the extent that it is not defined with let rec.

Answer 2

Let me try to expand a bit on Jeffrey Scofield's answer. A non-anonymous recursive definition of the factorial function could be

let rec fact n =
    if n < 2 then 1 else n * fact (n - 1)

The first problem you encounter when you try to define an anonymous recursive function is how to do the actual recursive call (fact (n - 1) in our case). For a call we need a name and we do not have a name for an anonymous function. The solution is to use a temporary name. With the temporary name f, the definition body is just

fun n -> if n < 2 then 1 else n * f (n - 1)

This term does not have a type, because the "temporary name" f is unbound. But we can turn it into a value that does have a type by bounding f as well. Let us call the result g:

let g = fun f n -> if n < 2 then 1 else n * f (n - 1)

g is not yet anonymous at the moment, but only because I want to refer to it again. Observe that g has type (int -> int) -> (int -> int). What we want (the factorial function) will have type (int -> int). So g takes something of the type we want (a function type in this case) and produces something of the same type. The intuition is that g takes an approximation of the factorial function, namely a function f which works for all n up to some limit N and returns a better approximation, namely a function that works for all n up to N+1.

Finally we need something that turns g into an actual recursive definition. Doing so is a very generic task. Recall that g improves the approximation quality. The final factorial function fact is one which cannot be further improved. So applying g to fact should be the same as just fact. (Actually that is only true from a value point of view. The actual computation inherent in g fact n for some n is different from that of just fact n. But the returned values are the same.) In other words, fact is a fixed point of g. So what we need is something that computes fixed points.

Luckily, there is a single function that does so: The Y combinator. From a value point of view, the Y combinator (let us use y in OCaml, as uppercase is reserved for constructors) is defined by the fact that y g = g (y g) for all g: given some function g, the combinator returns one of its fixed points. Consequently,

y : (`a -> `a) -> `a

In our case the type variable is instantiated by (int -> int). One possible way to define y would be

let y = fun g -> (fun x -> g (x x)) (fun x -> g (x x))

but this works only with lazy evaluation (as, I believe, Haskell has). As OCaml has eager evaluation, it produces a stack overflow when used. The reason is that OCaml tries to turn something like y g 8 into

g (y g) 8
g (g (y g)) 8
g (g (g (y g))) 8
...

without ever getting to call g. The solution is to use deferred computation inside of y:

let y = fun g -> (fun x a -> g (x x) a) (fun x a -> g (x x) a)

One drawback is that y does not work for arbitrary types any more. It only works for function types.

y : ((`b -> `c) -> (`b -> `c)) -> (`b -> `c)

But you asked for recursive definitions of functions anyway, not for recursive definitions of other values. So, our definition of the factorial function is y g with y and g defined as above. Neither y nor g are anonymous yet, but that can be remedied easily:

(fun g -> (fun x a -> g (x x) a) (fun x a -> g (x x) a))
    (fun f n -> if n < 2 then 1 else n * f (n - 1))

UPDATE:

Defining y only works with the -rectypes option. The reason is that we apply x to itself.

Answer 3

Here is a definition of factorial using only anonymous functions:

let fact =
    (fun f -> (fun x a -> f (x x) a) (fun x a -> f (x x) a))
    (fun f n -> if n < 2 then 1 else n * f (n - 1))

It requires the use of the -rectypes flag.

Here's a session showing that it works:

$ rlwrap ocaml -rectypes
        OCaml version 4.03.0

let fact =
    (fun f -> (fun x a -> f (x x) a) (fun x a -> f (x x) a))
    (fun f n -> if n < 2 then 1 else n * f (n - 1));;
val fact : int -> int = <fun>
# fact 8;;
- : int = 40320

I cheated somewhat by looking up the Y Combinator here: Rosetta Code: Y Combinator

Update

Disclaimer: you would do better to read up on lambda calculus, fixed points, and the Y Combinator than to get your info from me. I'm not a theorist, just a humble practitioner.

Following the actual computation is almost impossible (but definitely worth doing I'm sure). But at a high level the ideas are like this.

The first line of the definition is the Y Combinator, which in general calculates the fixed point of a function. It so happens that a recursive function is the fixed point of a function from functions to functions.

So the first goal is to find the function whose fixed point is the factorial function. That's the second line of the definition. If you give it a function of type int -> int, it gives you back another function of type int -> int. And if you give it the factorial function, it gives you back the factorial function. This means that the factorial function is its fixed point.

So then when you apply the Y Combinator to this function, you do indeed get the factorial function.