In almost all examples, a y-combinator in ML-type languages is written like this:

let rec y f x = f (y f) x
let factorial = y (fun f -> function 0 -> 1 | n -> n * f(n - 1))

This works as expected, but it feels like cheating to define the y-combinator using let rec ....

I want to define this combinator without using recursion, using the standard definition:

Y = λf·(λx·f (x x)) (λx·f (x x))

A direct translation is as follows:

let y = fun f -> (fun x -> f (x x)) (fun x -> f (x x));;

However, F# complains that it can't figure out the types:

  let y = fun f -> (fun x -> f (x x)) (fun x -> f (x x));;
  --------------------------------^

C:\Users\Juliet\AppData\Local\Temp\stdin(6,33): error FS0001: Type mismatch. Expecting a
    'a    
but given a
    'a -> 'b    
The resulting type would be infinite when unifying ''a' and ''a -> 'b'

How do I write the y-combinator in F# without using let rec ...?

f# y-combinator
Edit
Report