title: Abusing generics to implement a curried composition function in Java
body: <p>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) <code>(b -&gt; c) -&gt; (a -&gt; b) -&gt; (a -&gt; c)</code>. 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.</p>
  
  <p>Here is the implementation I've created so far: </p>
  
  <pre><code>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&lt;Integer, Integer&gt; plus2 = add().ap(2);
      // next, the times 3 function
      Fn&lt;Integer, Integer&gt; times3 = mult().ap(3);
      // now we compose them into a multiply by 2 and add 3 function
      Fn&lt;Integer, Integer&gt; 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 &lt;A,B,C&gt; 
                  Fn&lt;Fn&lt;B,C&gt;, // (b -&gt; c) -&gt; -- f
                  Fn&lt;Fn&lt;A,B&gt;, // (a -&gt; b) -&gt; -- g
                  Fn&lt;A,C&gt;&gt;&gt;   // (a -&gt; c)
                  compose(){
      return new  Fn&lt;Fn&lt;B,C&gt;, 
                  Fn&lt;Fn&lt;A,B&gt;, 
                  Fn&lt;A,C&gt;&gt;&gt; () {
        public Fn&lt;Fn&lt;A,B&gt;, 
               Fn&lt;A,C&gt;&gt; ap(final Fn&lt;B,C&gt; f){
          return new Fn&lt;Fn&lt;A,B&gt;, 
                     Fn&lt;A,C&gt;&gt;() {
            public Fn&lt;A,C&gt; ap(final Fn&lt;A,B&gt; g){
              return new Fn&lt;A,C&gt;(){
                public C ap(final A a){
                  return f.ap(g.ap(a));
                }
              };
            }
          };
        }
      };
    }
  
    // curried addition
    public static Fn&lt;Integer, Fn&lt;Integer, Integer&gt;&gt; add(){
      return new Fn&lt;Integer, Fn&lt;Integer, Integer&gt;&gt;(){
        public Fn&lt;Integer,Integer&gt; ap(final Integer a) {
          return new Fn&lt;Integer, Integer&gt;() {
            public Integer ap(final Integer b){
              return a + b;
            }
          };
        }
      };
    }
  
    // curried multiplication
    public static Fn&lt;Integer, Fn&lt;Integer, Integer&gt;&gt; mult(){
      return new Fn&lt;Integer, Fn&lt;Integer, Integer&gt;&gt;(){
        public Fn&lt;Integer,Integer&gt; ap(final Integer a) {
          return new Fn&lt;Integer, Integer&gt;() {
            public Integer ap(final Integer b){
              return a * b;
            }
          };
        }
      };
    }
  }
  
  interface Fn&lt;A, B&gt; {
    public B ap(final A a);
  }
  </code></pre>
  
  <p>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):</p>
  
  <pre><code>Currying.java:12: ap(Fn&lt;java.lang.Object,java.lang.Object&gt;) in 
  Fn&lt;Fn&lt;java.lang.Object,java.lang.Object&gt;,Fn&lt;Fn&lt;java.lang.Object,java.lang.Object&gt;,Fn&lt;java.lang.Object,java.lang.Object&gt;&gt;&gt;
  cannot be applied to (Fn&lt;java.lang.Integer,java.lang.Integer&gt;)
      Fn&lt;Integer,Integer&gt; times3plus2 = compose().ap(plus2).ap(times3);
  </code></pre>
  
  <p>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.</p>
  
  <p>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 <em>even more</em> of an incomprehensible wall of text.</p>