Skip to content

Instantly share code, notes, and snippets.

@jonbodner
Created May 1, 2012 22:20
Show Gist options
  • Save jonbodner/2571928 to your computer and use it in GitHub Desktop.
Save jonbodner/2571928 to your computer and use it in GitHub Desktop.
Generic Y Combinator in Java
//based on code from http://www.arcfn.com/2009/03/y-combinator-in-arc-and-java.html
class YFact {
// T function returning a T
// T -> T
public static interface Func<T> {
T apply(T n);
}
// Higher-order function returning a T function
// F: F -> (T -> T)
private static interface FuncToTFunc<T> {
Func<T> apply(FuncToTFunc<T> x);
}
//Next comes the meat. We define the Y combinator, apply it to the factorial input function, and apply the result to the input argument. The result is the factorial.
public static <T> Func<T> Y(final Func<Func<T>> r) {
return (new FuncToTFunc<T>() {
public Func<T> apply(final FuncToTFunc<T> f) {
return f.apply(f);
}
})
.apply(
new FuncToTFunc<T>() {
public Func<T> apply(final FuncToTFunc<T> f) {
return r.apply(
new Func<T>() {
public T apply(T x) {
return f.apply(f).apply(x);
}
});
}
});
}
public static void main(String args[]) {
System.out.println(
// Y combinator
Y(
// Recursive function generator
new Func<Func<Integer>>() {
public Func<Integer> apply(final Func<Integer> f) {
return new Func<Integer>() {
public Integer apply(Integer n) {
if (n == 0) return 1;
else return n * f.apply(n - 1);
}
};
}
}
).apply(
// Argument
Integer.parseInt(args[0])));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment