Generic Y Combinator in Java 8 using lambdas

YFact.java

//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> {
    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.
  // Formulation : λr.(λf.(f f)) λf.(r λx.((f f) x))
  public static <T> Func<T> Y(final Func<Func<T>> r) {
    return ((FuncToTFunc<T>) 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<Func<Integer>>() {
              public Func<Integer> apply(final Func<Integer> f) {
                return n -> n == 0 ? 1 : n * f.apply(n - 1);
              }
            }

        ).apply(
            // Argument
            Integer.parseInt(args[0])));
  }
}

You can simplify the Y() call as:

System.out.println(
    // Y combinator
    Y((Func<Integer> 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.

If you don't like the type in there, you can switch to if/then. The :? operator has issues with type inference.

         Y((Func<Integer> f) -> n -> { if (n == 0) return 1; else return n * f.apply(n - 1); }).apply(

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<Integer> 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> {
    T apply(SelfApplicable<T> a);
  }

  interface Func<X, Y> {
    Y apply(X x);
  }

  public static void main(String[] args) {
    // The Y combinator

    SelfApplicable<Func<Func<Func<Integer, Integer>, Func<Integer, Integer>>, Func<Integer, Integer>>> Y =
        y -> f -> x -> f.apply(y.apply(y).apply(f)).apply(x);

    // The fixed point generator
    Func<Func<Func<Integer, Integer>, Func<Integer, Integer>>, Func<Integer, Integer>> Fix = Y.apply(Y);

    // The higher order function describing factorial
    Func<Func<Integer, Integer>, Func<Integer, Integer>> F = fac -> x -> x == 0 ? 1 : x * fac.apply(x - 1);

    // The factorial function itself
    Func<Integer, Integer> factorial = Fix.apply(F);

    for (int i = 0; i < 12; i++) {
      System.out.println(factorial.apply(i));
    }
  }
}

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<T,R> {
        Function<T,R> hop(Function<T,R> inFunc);
    }
    interface Fixer<T,R> {
        Function<T,R> fix(Hopper<T,R> toFix);
    }
    interface SelfApply<X> {
        X self(SelfApply<X> me);
    }
    static <T,R> SelfApply<Fixer<T,R>> combinator() {
        return me -> hopper -> input -> hopper.hop(me.self(me).fix(hopper)).apply(input);
    }
    static <T,R> Fixer<T,R> fixer() {
        final SelfApply<Fixer<T,R>> y = combinator();
        return y.self(y);
    }
    public static void main(String[] args) {
        final Hopper<Integer,Integer> factorialDefinition = deeper ->
                n -> (n > 0 ? n * deeper.apply(n - 1) : 1);
        final Fixer<Integer, Integer> fixer = fixer();
        final Function<Integer,Integer> factorial = fixer.fix(factorialDefinition);

        for (int i = 0; i < 12; i++) {
            System.out.printf("%3d => %d\n", i, factorial.apply(i));
        }
    }
}