Skip to content

Instantly share code, notes, and snippets.

@nlinker
Forked from folone/SCombinator.scala
Created October 12, 2012 03:44
Show Gist options
  • Save nlinker/3877175 to your computer and use it in GitHub Desktop.
Save nlinker/3877175 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))
}
@nlinker
Copy link
Author

nlinker commented Feb 15, 2023

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.

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