Abusing generics to implement a curried composition function in Java

Question

So, after playing around with Java generics a bit, to get a deeper understanding of their capabilities, I decided to try to implement the curried version of the composition function, familiar to functional programmers. Compose has the type (in functional languages) (b -> c) -> (a -> b) -> (a -> c). Doing currying arithmetic functions wasn't too hard, since they are just polymorphic, but compose is a higher order function, and its proven taxing to my understanding of generics in Java.

Here is the implementation I've created so far:

public class Currying {

  public static void main(String[] argv){
    // Basic usage of currying
    System.out.println(add().ap(3).ap(4));
    // Next, lets try (3 * 4) + 2
    // First lets create the (+2) function...
    Fn<Integer, Integer> plus2 = add().ap(2);
    // next, the times 3 function
    Fn<Integer, Integer> times3 = mult().ap(3);
    // now we compose them into a multiply by 2 and add 3 function
    Fn<Integer, Integer> times3plus2 = compose().ap(plus2).ap(times3);
    // now we can put in the final argument and print the result
    // without compose:
    System.out.println(plus2.ap(times3.ap(4)));
    // with compose:
    System.out.println(times3plus2.ap(new Integer(4)));
  }

  public static <A,B,C> 
                Fn<Fn<B,C>, // (b -> c) -> -- f
                Fn<Fn<A,B>, // (a -> b) -> -- g
                Fn<A,C>>>   // (a -> c)
                compose(){
    return new  Fn<Fn<B,C>, 
                Fn<Fn<A,B>, 
                Fn<A,C>>> () {
      public Fn<Fn<A,B>, 
             Fn<A,C>> ap(final Fn<B,C> f){
        return new Fn<Fn<A,B>, 
                   Fn<A,C>>() {
          public Fn<A,C> ap(final Fn<A,B> g){
            return new Fn<A,C>(){
              public C ap(final A a){
                return f.ap(g.ap(a));
              }
            };
          }
        };
      }
    };
  }

  // curried addition
  public static Fn<Integer, Fn<Integer, Integer>> add(){
    return new Fn<Integer, Fn<Integer, Integer>>(){
      public Fn<Integer,Integer> ap(final Integer a) {
        return new Fn<Integer, Integer>() {
          public Integer ap(final Integer b){
            return a + b;
          }
        };
      }
    };
  }

  // curried multiplication
  public static Fn<Integer, Fn<Integer, Integer>> mult(){
    return new Fn<Integer, Fn<Integer, Integer>>(){
      public Fn<Integer,Integer> ap(final Integer a) {
        return new Fn<Integer, Integer>() {
          public Integer ap(final Integer b){
            return a * b;
          }
        };
      }
    };
  }
}

interface Fn<A, B> {
  public B ap(final A a);
}

The implementations of add, mult, and compose all compile just fine, but I find myself having a problem when it comes to actually using compose. I get the following error for line 12 (the first usage of compose in main):

Currying.java:12: ap(Fn<java.lang.Object,java.lang.Object>) in 
Fn<Fn<java.lang.Object,java.lang.Object>,Fn<Fn<java.lang.Object,java.lang.Object>,Fn<java.lang.Object,java.lang.Object>>>
cannot be applied to (Fn<java.lang.Integer,java.lang.Integer>)
    Fn<Integer,Integer> times3plus2 = compose().ap(plus2).ap(times3);

I assume this error is because generic types are invariant, but I am not sure how to solve the problem. From what I've read, wildcard type variables can be used to alleviate invariance in some cases, but I'm not sure how to use it here or even whether it will be useful.

Disclaimer: I have no intention of writing code like this in any real project. This is a fun "can it be done" kind of thing. Also, I made the variable names brief in defiance of standard Java practice because otherwise this example becomes an even more of an incomprehensible wall of text.

Answer 1

The basic problem here is that in the original call to compose(), there is no way for the compiler to infer the bindings of A, B, and C, so it assumes them all to be Object. You can fix it by specifying the type bindings explicitly:

Fn<Integer, Integer> times3plus2 = 
    Currying.<Integer, Integer, Integer>compose().ap(plus2).ap(times3);

Of course, then you lose the clarity that comes from type inference. If you need type inference, you could define some intermediate classes to do the inferring:

public static ComposeStart compose() {
    return new ComposeStart();
}

class ComposeStart {
    public <B,C> ComposeContinuation<B,C> ap(Fn<B,C> f) {
        return new ComposeContinuation<B, C>(f);
    }
}

class ComposeContinuation<B, C> {
    private final Fn<B,C> f;

    ComposeContinuation(Fn<B,C> f) {
        this.f = f;
    }

    public <A> Fn<A,C> ap(final Fn<A,B> g) {
        return new Fn<A,C>() {
            public C ap(A a) {
                return f.ap(g.ap(a));
            }
        };
    }
}

However, then the intermediate steps of currying are no longer Fns.