Functors in Java

Java is not a functional language. Java does not support functions as values which can be passed around as parameters to other functions. Although, a similar sort of functionality can be implemented using Function Objects. Many people confuse function objects and Functors which are actually quite different things. In this article we focus on Functors but to be able to demonstrate we need to first be able to define function objects which can be passed around as values.

Java 8 adds support for lambda expressions which are a nothing but some sugar for Anonymous classes from earlier versions Java and functions returned from lambda expression are objects which implement a usual interface with only one method. Here we will be using these lambda expressions but similar functionality can be obtained by using Anonymous class syntax by providing inline implementation of these interfaces. Java 8 also introduce default methods for interface which again we will be using in this article, but similar functionality can be obtained by using Abstract class instead, in earlier versions of Java.

As a first step lets define some simple interfaces for function objects, we will be adding more features to these interfaces as we go along.

/**
 * Function Object interface for defining a function
 * which takes a input parameter of type A
 * and returns a value of type B
 */
public interface Function1<A,B> {
   B apply(A a);
}

/**
 * Function object interface for defining a function
 * which takes input parameters of type A and B
 * return s value of type B
 */
public interface Function2<A,B,C> {
   C apply(A a,B b);
}

Function1 and Function2 are interfaces for functions with 1 and 2 input parameters respectively. Similarly, We could also define a Function0,Function3, Function4 etc. interfaces for functions which do not take any input parameter and take 3 and 4 or more parameters. Now lets create some functions and invoke them.

public class TestMain {
   public static void main(String args[]){
       /**
        * square function returns an Integer
        * and return square of it
        */
       Function1<Integer,Integer> square = (Integer a)->{ return a*a; };
       Integer squareValue = square.apply(3);
       System.out.println(squareValue);  // prints 9

       /*
        * Defines a function which takes two integers
        * a and b and returns product of both
        */
       Function2<Integer,Integer,Integer> mult = (Integer a,Integer b)-> { return a*b; };
       Integer productValue = mult.apply(3,4);
       System.out.println(productValue); // prints 12
   }
}

We defined some simple functions which take Integers as input and return Integer as output. Since, in our interfaces we define separate type parameters for each parameter and return type we can function which take and return different types. Let's write a function which takes Age as Integer in years and Height as Double in cm, and returns String with Age and Height separated by "-"

   Function2<Integer,Double,String> ageHeight = (Integer age,Double height)->{ return age+"-"+height; };
   // Now we can print age height
   System.out.println(ageHeight.apply(19,168.2)); // prints 19-168.2

Many functional languages also provide ability to apply a function partially, that is, provide only first few parameters instead of all parameters. When this is done function returns another function which takes remaining parameters, this is called currying and is a very useful feature. Again, it is simple to add this currying to our Function Objects. Lets add this capability to our Function interfaces.

/**
 * Function Object interface for defining a function
 * which takes a input parameter of type A
 * and returns a value of type B
 */
public interface Function1<A,B> {
   B apply(A a);
   default Function1<A,B> apply(){
       return (A a)->{ return apply(a); };
   }
}

/**
 * Function object interface for defining a function
 * which takes input parameters of type A and B
 * return s value of type B
 */
public interface Function2<A,B,C> {
   C apply(A a,B b);
   default Function1<B,C> apply(A a){
       return (B b)->{ return apply(a,b); };
   } 
   default Function2<A,B,C> apply(){
     return (A a,B b)->{return apply(a,b);};
   }
}

Lets see currying in action

  // mult.apply(3) returns a function which when invoked with 
  // a parameter x returns x multiplied by three 
  Function1<Integer,Integer> mult3 = mult.apply(3);
  // A function to calculate a^n
  Function2<Integer,Integer,Integer> pow = (Integer n, Integer a)-> { return (int) Math.pow(a,n); };
  // now we can define other functions like square, cube like so
  Function1<Integer,Integer> square1 = pow.apply(2);
  Function1<Integer,Integer> cube = pow.apply(3);

Functor

Now lets say we have a List of Integers and we want to calculate square of all the Integers in the List. One obvious way is to iterate over each element of the list and pass the value of each item to our square function. And lets say we also want to have all the resulting integers also as a List, so we need to create a new List of Integers and resulting integers to this new list. This is a very common pattern that appears again and again in functional programming. That is, we have a function from input type A to return type B, and a List of type A and we want List of type B created by application of function on each element. This is applicable to all container types like Sets, Lists, Tree,Vector etc, in fact, it applies to types other than container types, only requirement is that Type in question must have at least one type variable, we will see example of a type other than container type later in this blog. For example, List<T> is a List with type variable T. Formally, a Functor is any type, F, with at least one type parameter, A, and which implements a function fmap which accepts function (A to B) and instance of Type F[A] and returns another instance of type F[B]. This is also called lifting of function (A to B) to (F[A] to F[B]) , that is , it operates on higher type now. Lets see how we can implement Functor in Java. In order to demonstrate this we will first create an Interface called Functor and then create a new List by extending java.util.ArrayList and we will also implement Functor interface by defining required fmap method.

interface Functor<L extends Functor<?,?>,A> {
  <B>  L fmap(Function1<A,B> f);
}
static class FList<A> extends ArrayList<A> implements Functor<FList<?>,A> {
  public <R> FList<R> fmap(Function1<A,R> f){
       FList<R> list = new FList<R>();
       for(A a:this){
           list.add(f.apply(a));
       }
       return list;
  }
}


public class TestMain {
   public static void main(String args[]){
       /**
        * square function returns an Integer
        * and return square of it
        */
       Function1<Integer,Integer> square = (Integer a)->{ return a*a; };
       Integer squareValue = square.apply(3);
       System.out.println(suqareValue);  // prints 9

       /*
        * Defines a function which takes two integers
        * a and b and returns product of both
        */
       Function2<Integer,Integer,Integer> mult = (Integer a,Integer b)-> { return a*b; };
       Integer productValue = mult.apply(3,4);
       System.out.println(productValue); // println 12
       FList<Integer> nums = new FList<Integer>();
       nums.add(1);nums.add(2);nums.add(3);nums.add(4);nums.add(5);
       System.out.println(nums); // prints [1,2,3,4,5];
       System.out.println(nums.fmap(square)); //prints [1,4,9,16,100];
       System.out.println(nums.fmap(square).fmap(mult.apply(4))); // println [4,16,36,64,100]
   }
}

Here we first calculated square of all numbers in the list of integers. We also chained fmap to first multiply all numbers by square and the fmap resulting list with partially applied mult function with only first parameter specified as 4, this further multiplies numbers in list by 4. This chaining of functions, that is, of applying one function after another is common. And there exist another more elegant way of doing this, which is called function composition. In function composition instead of applying one function first and then applying second function on the result, we create a new function by composing these two functions. This new function when applied to list has the same effect.
We can achieve function composition if we also make our Function Object Functors too, that is, have Function Object also implement fmap method. This is an example where our type is not a container type but still can be Functor. As explained previously that only requirement of a potential Functor type is that it must have at least one type parameter.

// new Function1 defintion with fmap implementation
interface Function1<A,B> extends Functor<Function1<?,?>,B> {
   B apply(A input);
  default <C> Function1<A,C> fmap(Function1<B,C> f){
       return  (A a) -> { return f.apply(apply(a)); };
  }
  default Function1<A,B> apply(){
    return (A a)->{return apply(a);};
  }
}
public class TestMain {
   public static void main(String args[]){
       /**
        * square function returns an Integer
        * and return square of it
        */
       Function1<Integer,Integer> square = (Integer a)->{ return a*a; };
       /*
        * Defines a function which takes two integers
        * a and b and returns product of both
        */
       Function2<Integer,Integer,Integer> mult = (Integer a,Integer b)-> { return a*b; };

       FList<Integer> nums = new FList<Integer>();
       nums.add(1);nums.add(2);nums.add(3);nums.add(4);nums.add(5);
       System.out.println(nums); // prints [1,2,3,4,5];
       
      Function1<Integer,Integer> square_and_mult4 = square.fmap(mult.apply(4));
      System.out.println(nums.fmap(square_and_mult4)); //prints [4,16,36,64,100];
   }
}

This makes our Function Objects Functors too. fmap on Function Object is same as function composition and using that we created a new function square_and_mult4, this function when mapped of elements of list produces same result as applying square and mult individually.
Although, we could implement such a functionality as available in more functional languages such as Haskell but there are some weaknesses in type system of java. For example, when implementing Functor interface we had to again specify implementing type (FList), also there is no way to enforce constraint in the interface that only types which have at least one type parameter should be able to implement this interface. Also, we could declare functions using lambda system but we still had to provide all the types in the LHS, whereas, languages like Haskell can auto deduce this type information. These are some areas where languages like Haskell, scala have real advantage over java.

LESS is More

When a programer looks at a new language which is slightly different than general programming languages, first question that comes to his mind is if the language is turing complete. Similar thing happened to me when I looked at LESS. LESS is a CSS preprocessor and from a cursory look it looks like a macro sort of language which copy pastes definitions from one place to another. Actually, it is little more than that as it also tries to be a CSS like declarative language. That is, instead of defining variable you define properties and order defining those properties does not matter. Nevertheless, I have still not well understood the model of computation followed by this language, but it seems that even implementing a counter in this language is not very straightforward. I do not have anything to say to creators of LESS as it is not intended to be a general purpose language. Language does allow mathematical expression, variable definition, conditions (guards), methods. With these tools at hand I thought it would be easy to implement loops using recursion and calculate factorial and fibonacci sequence. My first attempt at creating a program that will find the factorial of a given number failed as it seems language does not allow updating a variable in a given scope once it is defined. At this point I knew that probably language does not well support writing such routines. I googled a lot to see if someone else has done something like this, but did not find anything. I was now looking for a language feature which could be exploited to carry out calculations and also preserve state. After trying many things I found that if you keep all the state in the form of parameters of a function (mixin), it is possible to get the effect of modifying a variable (state updation).  Below are some programs I wrote for calculating factorial and fibonacci numbers.

  
.fact_impl(@n,@res) when (@n > 1){
   .fact_impl(@n - 1, @res * (@n - 1));
}

.fact_impl(1,@res){
  @fact_res:@res;
}
.fact(@k){
  .fact_impl(@k,@k);
}

.fib_impl(@n,@first,@second) when (@n > 0){
  .fib_impl(@n - 1,@second,@first+@second);
}
.fib_impl(0,@first,@second){
  @fib_res:@first;
}
.fib(@k){
  .fib_impl(@k,0,1);
}

result{
  .fact(6);
  .fib(8);
  factorial_of_6:@fact_res;
  fibonacci_8:@fib_res;
}

LISP in Javascript

The main concept in LISP is that data is program and program is data. A wonderful way in which authors of SICP present the later is by creating data structure just by using functions. Lists in LISP and methods to operate on them can be created using just functions. We can do the same in Javascript as well, i.e. create List data-structure by just using functions and without objects or arrays. In fact we can create any data structure in this way. But an interesting question is where is data stored? (Its not too difficult to answer this question). Following is the JavaScript code which implements basic cons, car and cdr routines in Javascript.

  
function cons(x,y){
    var p=function(n){
        if(n==0)return x;
        if(n==1)return y;
        throw new Error("Index out of bound"+n);
    }
    p.toString=function(){
        return "("+x+","+y+")";
    }
    return p;
}
function car(z){
    return z(0);
}
function cdr(z){
    return z(1);
}

Now let us create some functions based on this list

  
/**
 * Syntactic sugar for constructing a list
 */
function list(){
   var args = [].slice.call(arguments);
   if(args.length == 0)
       return null;
   var first = args.shift();
   return cons(first,list.apply(this,args));
}
/**
 *  calculates length of the list
 */
function len(l){
    if(!l) return 0;
    return 1 + len(cdr(l))
}
/**
 * Calculate the factorials upto n
 * returns a list of factorials upto n
 */ 
function fact1(n,acc,a){
   if(n>1) return cons(acc,fact(n-1,acc*a,a+1));
   return acc;
}
function fact(n){
  return fact1(n,1,1);
}

These lists are created purely out of functions, we did not use any array or object type. This list can be extended to more complex data structures such as tree or graph.
Now let us create a little more complicated data structure, a binary search tree.

/**
 * Method to create a node in tree
 */
function create_node(val,left,right){
  return cons(val,cons(left,right));
}
/**
 * method to get left subtree
 */
function left(tree){
  return car(cdr(tree));
}
/**
 * method to get right subtree
 */
function right(tree){
  return cdr(cdr(tree));
}
/**
 * method to add a new number in binary search tree
 */
function add(num,tree){
    if(!tree){
      return create_node(num,null,null);
    }
    var val=car(tree);
    var l = left(tree);
    var r = right(tree);
    if(num > val) return create_node(val,l,add(num,r));
    if(num < val) return create_node(val,add(num,l),r);
    return tree;
}
/*
 * method to check if a number 
 * exists in the tree
 */
function num_exists(num,tree){
  if(tree){
     var l = left(tree);
     var r = right(tree);
     var val = car(tree);
     if(num == val){
       return true;
     }
     return num_exists(num,l) || num_exists(num,r);
  }
  return false;
}

/**
 * method to do in order traversal of tree
 * and output list of sorted nodes
 * @param tree current node to traverse in the tree
 * @parent list of root val and in order traversed 
 * list of right sibling subtree
 */
function traverse(tree,parent){
  if(!parent){
    parent = null;
  }
  if(tree){
     var l = left(tree);
     var r = right(tree);
     var val = car(tree);
     var traversedRight = traverse(r,parent);
     var trr = cons(val,traversedRight);
     return traverse(l,trr);
  }
  return parent;
}

/* sample run */
var tree = add(3);
tree=add(4,tree);
tree=add(9,tree);
tree=add(5,tree);
tree=add(1,tree);
tree=add(2,tree);
console.log(num_exists(5,tree)); // outputs: true
console.log(""+traverse(tree)); // outputs: (1,(2,(4,(5,(9,null)))))

As we can how complex data structures can be created without using any object or array