Y combinator using lambda and method references

[Brian Goetz]

Try this version (again, just because you can, doesn't mean you 
necessarily should.)

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));
      }
   }
}




On 10/27/2012 5:20 PM, Arul Dhesiaseelan wrote:
> I attempted to port this Y combinator [1] using Java 8 lambdas. The closest
> I can make it work is shown here [2].
>
> It looks like intellij code inspection suggests I can still reduce this
> further by using 2 method references and 1 lambda as shown visually here
> [3], but I run into problems with those conversions.
>
> # 1 Applying the first inspection (line # 19) to a method reference fails
> in a compile error:
> error: cannot find symbol variable f
>
> #2 Applying the second inspection (line # 22) to a method reference
> compiles just fine, but runs into a StackOverflowError. May be this is a
> problem with the code itself.
>
> #3 Applying the third inspection (line # 31) to a lambda fails in a compile
> error:
>
> error: method Y in class YFact cannot be applied to given types;
> required: Func<Func<T>>
> found: (final Fun[...] - 1)
> reason: cyclic inference - cannot infer target type for given lambda/method
> reference expression
> where T is a type-variable:
> T extends Object declared in method <T>Y(Func<Func<T>>)
>
> I am not sure if this is a case where the editor is incorrect in detecting
> compilation errors. I believe the editor should reject these if the
> compiler cannot infer the target type.
>
> Please apologize if this does not belong here.
>
> - Arul
>
> [1] http://www.arcfn.com/2009/03/y-combinator-in-arc-and-java.html
> [2] https://gist.github.com/3965968
> [3] https://dl.dropbox.com/u/3274664/java/yfact-idea-inspections.png
>