Thursday, September 25, 2008

The Y Combinator in Scala

A while ago I ran across an implementation of the Y combinator in Java. My first thought was, "Woah, this is cool!", followed immediately by "Woah, this is hideous!"

Below is my port of that code to Scala. Hopefully it's just as cool, and just a little less hideous.

case class B[F,T](c: B[F, T] => (F => T)) extends (B[F, T] => (F => T)) {
def apply(b: B[F, T]) = c(b);
}

def Y[F, T] = (f: (F => T) => F => T) =>
B[F, T](x => f(x(x)(_)))(B(x => f(x(x)(_))))

val factorial = Y[Int, Int](f => i => if (i <= 0) 1 else f(i - 1) * i)
factorial(6) == 720

Note that it's a straight port of the Java code, so it doesn't make any use at all of Scala's more powerful type system. (It does, however, make liberal use of type inference and syntactic sugar, especially for Function types.) A question for the type experts: can Scala do better with more advanced types?

10 comments:

David said...

In the interest of continuing to shorten the code, you can replace the first 7 lines with:

case class B[F,T](c: B[F, T] => (F => T)) extends (B[F, T] => (F => T)) {
def apply(b: B[F, T]) = c(b);
}

Jorge Ortiz said...

David: Nice! I've updated the code with your shorter solution. Thanks!

pvncad said...

Is there way to define Y combinator in scala completely anonymous like we can do in dynamically typed languages such lisp ?

I am quite new to scala. Could you elaborate bit on class B in your code ?

Seth Tisue said...
This comment has been removed by the author.
Seth Tisue said...

def Y[A,B](f: (A=>B)=>(A=>B)) = {
case class W(wf: W=>A=>B) {
def apply(w: W) = wf(w) }
val g: W=>A=>B = w => f(w(w))(_)
g(W(g))
}

Notes:
- The case class doesn't need "extends ...".
- Making the case class inner improves encapsulation and avoid excessive type declarations.
- Storing the repeated subexpression in a val makes the code more clearly isomorphic to the well-known Scheme version.

I'm still trying to figure out if you can somehow do without the case class entirely.

Matt Hellige said...

Depending on the point of the exercise, I'd probably just do:

def fix[A,B](f: (A=>B)=>(A=>B)): A=>B = f(fix(f))(_)

You might find the use of recursion cheating, I'm not sure...

Jack Cough said...

Matt, its most definitely cheating :)

Matt Hellige said...

I don't know, it seems like all the solutions use the built-in recursion somewhere... Some use it at the type-level instead of the value-level, but I sort of think that's just sleight-of-hand.

But, after all these years, this stuff still hurts my head. I admit it.

And yes, I concede the point, it's cheating. :)

lmm said...

pvncad: Defining it anonymously works, though seems to requires a little more handholding of the typesystem:

scala> (((f: (Int => Int) => Int => Int) => B[Int,Int](x => f(x(x)(_)))(B(x => f(x(x)(_))))): (((Int => Int) => (Int => Int)) => (Int => Int)))({g: (Int => Int) => ({i : Int => if (i <= 0) 1 else g(i - 1) * i})})(6)
res29: Int = 720

The type B is our way to represent a function of type "B => T => T"; we can't define it as this because scala doesn't let you define types recursively, and we need to give it some type because scala is typed. I feel like it should be possible to do something more clever, but I haven't managed to yet.

Eli Jordan said...

How about this. No recursion :-D

def Y[A, R](f: (A => R) =>
(A => R)):
(A => R) = {
var yf: A => R = null
yf = (f(_))(yf(_))
yf
}

def factComb(f: Int => Int)(n: Int): Int = {
if(n == 0) 1
else n * f(n - 1)
}

val fact = Y(factComb _)