Writing the Z combinator in Ocaml

Question

I'm new to lambda calculus, and I find the grammar sometimes ambiguous to me. Specifically, I'd like to know how to understand the Z combinator:

Z = λ f. (λ x. f (λ v. xxv)) (λ x. f (λ v. xxv))

How to write it in OCaml? Updated: I get error when writing like this:

 fun f-> let g = fun x -> f(fun v-> x x v)in g g;;

Error: This expression has type 'a -> 'b -> 'c but an expression was expected of type 'a The type variable 'a occurs inside 'a -> 'b -> 'c

Answer 1

Typing the Z-combinator requires either to allow recursive types (with the -rectypes option) or to box the type recursion inside a type constructor:

type 'a fix = Fix of ('a fix -> 'a)
let z f = 
  (fun (Fix x as fx) -> f (fun v -> x fx v)) 
  (Fix (fun (Fix x as fx) -> f (fun v -> x fx v)))

Essentially, we are replacing

x x v

which requires x to accept itself as an argument which leads to the recursive type 'a -> 'b -> 'c as 'a by

x fx v

which boxes the recursive type as ('a -> 'b) fix -> 'a -> 'b