32leaves.net

Y combinator in Scala

This is just a quick post to share this thing with the world: the Y-combinator in Scala (yipee, anonymous recursion). Unfortunately this can’t be written purely as Scala does not employ lazy evaluation (like Haskell does).

1
2
3
4
5
6
7
8
9
object YCombinator {

  def Y[A](f: (A => A) => (A => A)): (A => A) = f(Y(f))(_:A)
 
  def main(args: Array[String]) = {
    println(Y( (fact:(Int => Int)) => (x:Int) => if(x == 0) 1 else x * fact(x - 1) )(5))
  }
 
}
Fork me on GitHub