Skip to content

Instantly share code, notes, and snippets.

@folone
Created June 30, 2011 07:19
  • Star 6 You must be signed in to star a gist
  • Fork 8 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save folone/1055790 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))
}
@nmarcin92
Copy link

:(

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment