1. Currying with Java Generics

    In functional languages like ML and Haskell (and even non-functional ones like Python, C#, and Ruby) we have first class functions. Functions can be passed to other functions and can be returned from functions as a result. There are a couple of aspects of this that make them useful in these languages. First, these first-class function “close over” their scope. Meaning if I write code like this in Python:

    def function_factory():
        a = 3
        return lambda b: a + b
    

    The function that function_factory returns has the value of a baked into it. This isn’t super surprising or anything, but the thing to notice is that a wasn’t defined inside of the returned function. We say it was “closed over”.

    The second thing these languages with first class functions provide us with is a way to make an anonymous function. This is just a function without a name, and it’s part of the first class nature of functions. You have to be able to create a function literal, the same way you can make a “String” or a 3. Python provides the lambda keyword, which is a bit cumbersome, but functional languages like Haskell provide even more succinct syntax. The above lambda can be created in Haskell with:

    \b -> a + b

    If you’re looking for one killer application of first class functions, the easy example for an imperative language is callback functions. Want some library to do something when an event happens? Just pass them the function you want closed over any variables you need it to have. Everything wrapped up all nice and tidy.

    "But wait", you say, "that sounds an awful lot like an object!". And you’d be right. State and functionality wrapped up into one nice little package sounds a lot like an object. And in a way, that’s certainly how you could implement first class functions in a language without them. Create an object that stores the state it needs and has some method that uses that state and then performs the wanted functionality. But in these modern times, where are you going to get a language with objects that doesn’t also have first class functions? Why, even JavaScript has closures and anonymous functions…

    Oh that’s right: Java.

    But it won’t do to just show how we can write callbacks in Java using emulated first class functions. After all, that’s something Java already does just fine, there’s no need to come up with a wacky way of doing it. No, I think today we’ll focus on forcing Java to use our emulated first class functions to do some functional programming. But first, we’ll have to take a slight detour and explain currying.

    I’ll refer the historical lesson on currying to Wikipedia and focus on the essentials. Currying is a way to allow multiple arguments in a language that only allows one argument per function. The catch is that the language has to support anonymous functions. Luckily, all the languages that only support one argument per function also support anonymous functions for just this reason. Sounds weird? Don’t worry about it, all that matters is how it works in practice.

    I’ll write a classy curried version of addition to demonstrate. First in Python:

    def add(a):
        return lambda b: a + b
    

    then in Haskell to show the contrast:

    add = \a -> \b -> a + b

    So what can we do with these seemingly overcomplicated versions of two-argument functions? Well, for one, we can partially apply them. That means if we only give add one argument, instead of an error, we get back a function that just waits around and returns the overall answer when we get around to giving it the second argument. That’s actually pretty cool. Here’s partial application at work in Python:

    plus2 = add(2)
    

    and in Haskell:

    plus2 = add 2
    

    plus2 is a function that takes a number as an argument and adds 2 to whatever that argument is. That’s it. If you want to skip partial application, and just give both arguments at once, you can. Adding 3 and 4 with our curried function looks like this:

    add(3)(4) # returns 7!

    and in Haskell

    add 3 4 -- result is still 7!

    You’ll notice Python is a bit more verbose than Haskell here, with the parenthesis and all, but as we’ll see, it doesn’t hold a candle to Java in complexity. And to be fair, Haskell is a functional language designed to support these kinds of things, Python is multi-paradigm language that has a functional aspect. (And actually, Haskell has syntactic support for currying as well that makes it even more succinct, but that’s for another day).

    Anywho, after currying, the one other concept we’d like to force our poor Java compiler to deal with is higher-order functions(HOFs). HOFs are functions that take functions as arguments or return them as results. Above, we saw that currying entails returning functions as results, but we didn’t take any functions as arguments. Let’s change that now with this Python example:

    def compose(f):
        def compose_inner(g):
            return lambda a: f(g(a))
        return compose_inner

    And here is how we can do it in Haskell (Note: this is not how a Haskell programmer would actually do it!):

    compose = \f -> \g -> \a -> f (g a)

    So if we have a function f that takes a single argument, and another function g that takes a single argument and outputs some value that f is allowed to take as input, then we can plug the output of g to the input of f and get a whole new function as a result. Here’s an example in Python of using this:

    def add2(a):
        return a + 2
    
    def mult3(b):
        return b * 3
    
    mult3_then_add2 = compose(add2)(mult3)
    mult3_then_add2(4) # returns 14

    and Haskell:

    add2 = \a -> a + 2
    
    mult3 = \b -> b * 3
    
    mult3_then_add2 = compose add2 mult3
    mult3_then_add2 4 -- result is still 14!

    Alright, well this is neat and all, but I promised you some functional goodness in Java. The only problem is, Java doesn’t support anonymous functions (sometimes called lambdas), which is pretty central to our currying scheme!

    Well, no, Java doesn’t have lambdas. But, what it does have is anonymous classes, which is just enough to shoehorn in some functional concepts, like currying! Warning: Never write Java code like this. You could never look your mother in the eye again. The central idea is that we can use anonymous local classes to implement an interface that is somewhat like an object whose only purpose is to hold a function. For good measure, we make this whole endeavor type-safe by making extensive use of Java Generics. We’re going to force the Java compiler to bend in ways it was never intended to bend!

    interface Fn<A, B> {
      public B ap(final A a);
    }
    
    public class Currying {
    
      // This is our compose function
      public static <A,B,C>
        Fn<Fn<B,C>, // (b -> c) -> 
        Fn<Fn<A,B>, // (a -> b) -> 
        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));
                  }
                };
              }
            };
          }
        };
      }
    
      // This is our add function
      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;
              }
            };
          }
        };
      }
    
      // This is our multiply function
      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;
              }
            };
          }
        };
      }
      
      // This is the lessthan function
      public static Fn<Integer, Fn<Integer, Boolean>> lessthan(){
        return new Fn<Integer, Fn<Integer, Boolean>>(){
          public Fn<Integer, Boolean> ap(final Integer a){
            return new Fn<Integer, Boolean>(){
              public Boolean ap(final Integer b){
                return a < b;
              }
            };
          }
        };
      }
    
      // This is the string length function
      public static Fn<String, Integer> length(){
        return new Fn<String, Integer>(){
          public Integer ap(final String str){
            return str.length();
          }
        };
      }
      
      // This is a tricky one! It takes a curried function of two arguments as its
      // first argument (we'll call this function f), then it returns a new curried
      // function that takes the two arguments in reversed order! We use this in the
      // main function to flip the order of the lessthan function's arguments so we
      // can have the function that answers the question "is it less than two?",
      // rather than "is two less than it?"
      public static <A,B,C> 
        Fn<Fn<A,Fn<B,C>>, // (a -> b -> c) ->
        Fn<B,Fn<A,C>>>  // (b -> a -> c)
        flip(){
        return new Fn<Fn<A,Fn<B,C>>, Fn<B,Fn<A,C>>>(){
          public Fn<B, Fn<A,C>> ap(final Fn<A,Fn<B,C>> f){
            return new Fn<B, Fn<A,C>>(){
              public Fn<A,C> ap(final B b){
                return new Fn<A,C>(){
                  public C ap(final A a){
                    return f.ap(a).ap(b);
                  }
                };
              }
            };
          }
        };
      }
    
      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 = Currying.<Integer,Integer,Integer>
          compose().ap(plus2).ap(times3);
        // without compose
        System.out.println(plus2.ap(times3.ap(4)));
        // with compose
        System.out.println(times3plus2.ap(4));
    
        //Let's do something with different data types!
    
        // First lets create the "is this less than 7?" function. We have to use
        // flip to flip the order of arguments to lessthan so we get the right
        // meaning 
        Fn<Integer, Boolean> lessthan7 = Currying.<Integer,Integer,Boolean>
          flip().ap(lessthan()).ap(7);
        // Next, let's compose lessthan7 and length
        Fn<String,Boolean> lengthlessthan7 = Currying.<String,Integer,Boolean>
          compose().ap(lessthan7).ap(length());
    
        // Now let's use our cool function in a loop
        String[] strings = {"Hi","there","majestic","person"};
        for (String str : strings){
          System.out.println(lengthlessthan7.ap(str));
        }
      } 
    }
      

    I feel like I might go to jail for committing atrocities like this! (Special thanks to Russell Zahniser for his help with some sticky generics points on StackOverflow)