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?


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))(_)

- 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(_))

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

val fact = Y(factComb _)

Alex Edward said...

You have posted a great article, thanks for sharing it, keep posting this kind of informative blog

Lan Linh said...

I found lots of interesting information here.Great work. The post was professionally written and I feel like the author has extensive knowledge in this subject. Nice post.
pacman |happy wheels |my little pony games | unblocked games

Michael Amat said...

I was about to say something on this topic. But now i can see that everything on this topic is very amazing and mind blowing, so i have nothing to say here. I am just going through all the topics and being appreciated. Thanks for sharing.

Greenwood Jonny said...

Excellent blog you have here but I was curious abou t if you knew of any communi ty forums tha t cover the same topics talked about in this article? I’d really like to be a part of online community where I can get advice from other experienced individuaIs that share the same interest. If you have any suggestions, please let me know. Appreciate it!

Dedi Abdullah said...

penyebab kutil di vagina dan cara mengobatinya secara tradisional
Tips untuk menyembuhkan kutil kelamin dgan cara alami
alat kelamin wanita
kutil di alat kelamin ibu hamil
obat bintik bintik di area telur penis
tanda tanda wanita berpenyakit kelamin
apakah obat callusol manjur untuk mengobati kutil kelamin?
obat callusol untuk kutil kelamin
callusol apa bisa untuk kutil kelamin?
obt kutil kelamin wilayah lampung
cara menyembuhkan kutil kelamin di lampung