Created
May 1, 2012 22:20
-
-
Save jonbodner/2571928 to your computer and use it in GitHub Desktop.
Generic Y Combinator in Java
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//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