SCombinator.scala

/**
 * <b>Fixed Point Combinator is:</b>
 * Y = λf.(λx.f (x x)) (λx.f (x x))
 * 
 * <b>Proof of correctness:</b>
 * Y g  = (λf . (λx . f (x x)) (λx . f (x x))) g    (by definition of Y)
 * = (λx . g (x x)) (λx . g (x x))                  (β-reduction of λf: applied main function to g)
 * = (λy . g (y y)) (λx . g (x x))                  (α-conversion: renamed bound variable)
 * = g ((λx . g (x x)) (λx . g (x x)))              (β-reduction of λy: applied left function to right function)
 * = g (Y g)                                        (by second equality) [1]
 */
object SCombinator extends Application {
    
    def Y[T](func: (T => T) => (T => T)): (T => T) = func(Y(func))(_:T) // By definition
    
    private def fact = Y {
      f: (Int => Int) =>
        n: Int =>
          if(n <= 0) 1
          else n * f(n - 1)
    }
    
    override def main(args: Array[String]) =
        println(fact(5))
}

object WithoutExplicitRecursion {
  def Y[A,B](f: (A=>B)=>(A=>B)) = {
    case class W(wf: W=>A=>B) {
      def apply(w: W) = wf(w)
    }
    val g: W=>A=>B = w => f(w(w))(_)
    g(W(g))
  }
}