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) == 720Note 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?
8 comments:
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);
}
David: Nice! I've updated the code with your shorter solution. Thanks!
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 ?
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.
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...
Matt, its most definitely cheating :)
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. :)
Post a Comment