Skip to content

Instantly share code, notes, and snippets.

@liango2
Forked from folone/SCombinator.scala
Created January 13, 2016 19:19
Show Gist options
  • Save liango2/f169668a2547988e388d to your computer and use it in GitHub Desktop.
Save liango2/f169668a2547988e388d to your computer and use it in GitHub Desktop.
Y-Combinator in 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))
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment