Skip to content

Instantly share code, notes, and snippets.

@nlinker
Created October 12, 2012 07:03
Show Gist options
  • Save nlinker/3877715 to your computer and use it in GitHub Desktop.
Save nlinker/3877715 to your computer and use it in GitHub Desktop.
Scala vs Java Y combinator
//////////////////////////////////////////////////////////////
// Java version
// this is an interface with just one method, apply() from
// https://code.google.com/p/guava-libraries/
import com.google.common.base.Function;
import junit.framework.TestCase;
public class YCFun extends TestCase {
public static interface BranchType<F, T> extends
Function<BranchType<F, T>, Function<F, T>> {
}
public static <F, T> Function<Function<Function<F, T>,
Function<F, T>>, Function<F, T>> y() {
return new Function<Function<Function<F, T>, Function<F, T>>,
Function<F, T>>() {
public Function<F, T> apply(
final Function<Function<F, T>, Function<F, T>> f) {
return new BranchType<F, T>() {
public Function<F, T> apply(final BranchType<F, T> x) {
return f.apply(new Function<F, T>() {
public T apply(F y) {
return x.apply(x).apply(y);
}
});
}
}.apply(new BranchType<F, T>() {
public Function<F, T> apply(final BranchType<F, T> x) {
return f.apply(new Function<F, T>() {
public T apply(F y) {
return x.apply(x).apply(y);
}
});
}
});
}
};
}
// To get proper type inference
public static <F, T> Function<F, T> yapply(
final Function<Function<F, T>, Function<F, T>> f) {
return YCFun.<F, T> y().apply(f);
}
public void testFactorial() {
Function<Integer, Integer> factorial =
yapply(new Function<Function<Integer, Integer>,
Function<Integer, Integer>>() {
public Function<Integer, Integer> apply(
final Function<Integer, Integer> f) {
return new Function<Integer, Integer>() {
public Integer apply(Integer i) {
if (i <= 0) {
return 1;
} else {
return f.apply(i - 1) * i;
}
}
};
}
});
assertEquals(720, factorial.apply(6).intValue());
}
}
//////////////////////////////////////////////////////////////
// Scala version
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
//////////////////////////////////////////////////////////////
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment