Typing the Y combinator in SML/NJ.

y.sml

(* Typing the Y combinator in SML/NJ.
 * $ sml y.sml
   720
   Succ(Succ(Succ(Succ(Succ(Succ(Zero))))))
*)

datatype 'a fix = Fix of ('a fix -> 'a)

fun fix f = Fix f
fun unfix (Fix f) = f

fun y (f : ('a -> 'b) -> 'a -> 'b) : 'a -> 'b =
    let fun g x a =
            f ((unfix x) x) a
    in
       g (fix g)
    end

(* The factorial function. *)
fun fact _    0 = 1
  | fact self n = n * self (n - 1)

(* A representation of natural numbers. *)
datatype nat = Zero | Succ of nat

fun int2nat self 0 = Zero
  | int2nat self n = Succ (self (n - 1))

fun string_of_nat _     Zero     = "Zero"
  | string_of_nat self (Succ n)  = "Succ(" ^ (self n) ^ ")"

local
    val result = y fact 6
    val result' = y int2nat 6
in
    val () = print ((Int.toString result) ^ "\n")
    val () = print ((y string_of_nat result') ^ "\n")
end