Typing the Y combinator in Scala.

Y.scala

// Typing the Y combinator in Scala 2.
// $ scalac Y.scala
// $ scala Y
// 720
// Succ(Succ(Succ(Succ(Succ(Succ(Zero))))))

object Y {

  case class Fix[A,B](f : Fix[A,B] => A => B) {
    def apply(x : Fix[A,B]) = f(x)
  }

  def y[A,B](f : (A => B) => A => B) : A => B = {
    val g : Fix[A,B] => A => B = x => a => f(x(x))(a)
    g(Fix(g))
  }

  // The factorial function.
  def fact(self : Int => Int)(n : Int) : Int = {
    if (n == 0) 1
    else n * self(n - 1)
  }

  // A representation of natural numbers.
  abstract class Nat
  case class Zero() extends Nat {
    override def toString() : String = "Zero"
  }
  case class Succ(n : Nat) extends Nat {
    override def toString() : String = "Succ(" + n.toString() + ")"
  }

  def int2nat(self : Int => Nat)(n : Int) : Nat = {
    if (n == 0) Zero()
    else Succ(self(n-1))
  }

  def main(args: Array[String]): Unit = {
    val result0 = y(fact)(6)
    println(result0)
    val result1 = y(int2nat)(6)
    println(result1)
  }
}