Y-Combinator in Scala

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))
}

As noted here this is not a Y-combinator, it's a recursion operator (not sure about the term): your Y provides a recursion for a given function. Which is neat and cool, just not Y.

As noted here this is not a Y-combinator, it's a recursion operator (not sure about the term): your Y provides a recursion for a given function. Which is neat and cool, just not Y.

Thanks, will read it.