Instantly share code, notes, and snippets.

# aruld/YFact.java

forked from jonbodner/YFact.java
Created Oct 27, 2012
Generic Y Combinator in Java 8 using lambdas
 //based on code from http://www.arcfn.com/2009/03/y-combinator-in-arc-and-java.html and the generic version https://gist.github.com/2571928 class YFact { // T function returning a T // T -> T public static interface Func { T apply(T n); } // Higher-order function returning a T function // F: F -> (T -> T) private static interface FuncToTFunc { Func apply(FuncToTFunc 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. // Formulation : λr.(λf.(f f)) λf.(r λx.((f f) x)) public static Func Y(final Func> r) { return ((FuncToTFunc) f -> f.apply(f)) .apply( f -> r.apply( x -> f.apply(f).apply(x))); } public static void main(String args[]) { System.out.println( // Y combinator Y( // Recursive function generator new Func>() { public Func apply(final Func f) { return n -> n == 0 ? 1 : n * f.apply(n - 1); } } ).apply( // Argument Integer.parseInt(args[0]))); } }

### spullara commented Oct 27, 2012

 You can simplify the Y() call as: ``````System.out.println( // Y combinator Y((Func f) -> (Integer n) -> n == 0 ? 1 : n * f.apply(n - 1)).apply( // Argument Integer.parseInt(args[0]))); `````` I'm not sure about the conversion to method references but I don't see an easy way to do it.

### spullara commented Oct 27, 2012

 If you don't like the type in there, you can switch to if/then. The :? operator has issues with type inference. `````` Y((Func f) -> n -> { if (n == 0) return 1; else return n * f.apply(n - 1); }).apply( ``````
Owner Author

### aruld commented Nov 21, 2012

 Nice Sam! Yea, I run into type error with the latter approach. But, it can be fixed by providing a type hint like before. `((final Func f) -> (Integer n) -> { if (n == 0) return 1; else return n * f.apply(n - 1); })` Btw, I like Brian's version which looks much better. ```class Y { interface SelfApplicable { T apply(SelfApplicable a); } interface Func { Y apply(X x); } public static void main(String[] args) { // The Y combinator SelfApplicable, Func>, Func>> Y = y -> f -> x -> f.apply(y.apply(y).apply(f)).apply(x); // The fixed point generator Func, Func>, Func> Fix = Y.apply(Y); // The higher order function describing factorial Func, Func> F = fac -> x -> x == 0 ? 1 : x * fac.apply(x - 1); // The factorial function itself Func factorial = Fix.apply(F); for (int i = 0; i < 12; i++) { System.out.println(factorial.apply(i)); } } }```

### benhardy commented Dec 13, 2016

 I found this easier to understand by naming the function interfaces uniquely as the order got higher. ```import java.util.function.Function; public class YCombinator { interface Hopper { Function hop(Function inFunc); } interface Fixer { Function fix(Hopper toFix); } interface SelfApply { X self(SelfApply me); } static SelfApply> combinator() { return me -> hopper -> input -> hopper.hop(me.self(me).fix(hopper)).apply(input); } static Fixer fixer() { final SelfApply> y = combinator(); return y.self(y); } public static void main(String[] args) { final Hopper factorialDefinition = deeper -> n -> (n > 0 ? n * deeper.apply(n - 1) : 1); final Fixer fixer = fixer(); final Function factorial = fixer.fix(factorialDefinition); for (int i = 0; i < 12; i++) { System.out.printf("%3d => %d\n", i, factorial.apply(i)); } } }```