The ideas of functional programming (FP) have arrived in most mainstream programming languages, including imperative languages such as Java and C++. However, there is still a significant difference to languages that primarily target FP.

In this post we will employ FP without using any language support for FP. This serves two purposes. On the one hand, it demonstrates that the ideas of FP are so fundamental that they don’t require unusual syntactical constructs to work. On the other hand, it illustrates what advantages FP languages offer for FP. Today’s language of choice is Java.

Functions

As a first step, we define a function type as an abstract class.

abstract class Function<A, B> {
	abstract B eval(A a);
}

Note that Java contains built-in function types since Java 1.8. In this article, however, we will not use them or the syntax Java offers for functional interfaces. Instead, we will work with purely imperative Java code.

We can now construct a function that increments an integer as an anonymous subclass of the Function class.

Function<Integer, Integer> incr = new Function<Integer, Integer>() {
  @Override
  public Integer eval(Integer in) {
    return in + 1;
  }
};

This code snippet shows clearly that using functions in this way is overly verbose in Java. However, it is possible to instantiate a stand-alone function (not instance method) this way.

We can apply the function to an argument and will get the expected result.

incr.eval(4) // yields 5

Currying and partial application

FP works best with currying and partial application. For example, a function that adds two values can be seen as a function that takes one value and returns a function that takes another value and returns a result. Actually, we can straightforwardly translate this to a Java object:

Function<Integer, Function<Integer, Integer>> add = new Function<Integer, Function<Integer, Integer>>() {
  @Override
  Function<Integer, Integer> eval(final Integer a) {
    return new Function<Integer, Integer>() {
      @Override
      Integer eval(final Integer b) {
        return a + b;
      }
    };
  }
};

And now we can partially apply this function by supplying the arguments individually:

Function<Integer, Integer> add3 = add.eval(3);
System.out.println(add3.eval(4));
System.out.println(add3.eval(12));

Higher-order functions

Among the most powerful tools in FP are higher-order functions (HOF), functions that take functions as an input or produce functions as an output. Due to currying, the above function add is a HOF, as it returns a Function<Integer, Integer>. Another typical example for a HOF is function composition:

static <A, B, C> Function<A, C> compose(final Function<A, B> f, final Function<B, C> g) {
  return new Function<A, C>() {
    @Override
    C eval(A a) {
      return g.eval(f.eval(a));
    }
  };
}

Note that compose is defined as a static method that takes two arguments, so not curried. We can, however, also define HOFs as anonymous subclasses of Function. For example, this is how mapping over a list can be implemented in our bizarre FP-Java:

static <A, B> Function<Function<A, B>, Function<List<A>, List<B>>> map() {
  return new Function<Function<A, B>, Function<List<A>, List<B>>>() {
    @Override
    Function<List<A>, List<B>> eval(final Function<A, B> f) {
      return new Function<List<A>, List<B>>() {
        @Override
        List<B> eval(final List<A> as) {
          List<B> result = new LinkedList<B>(); // use LinkedList because we are doing FP
          for (A a : as) {
            result.add(f.eval(a));
          }
          return result;
        }
      };
    }
  };
}

To use map, we have to give the types for A and B explicitly. The following listing uses map to define a function that increments all elements of a list and applies it:

Function<List<Integer>, List<Integer>> listIncr = Lists.<Integer, Integer>map().eval(incr);

List<Integer> is = listIncr.eval(Arrays.asList(1, 2, 3));

Conclusion

I think that nobody would like to program funcionally in Java this way. However, it is technically possible, and does not require overly exotic or creative programming techniques. In fact, the only prerequisite is a custom function type. Everything else can be built on such a function type: Currying, partial application, and higher-order functions are not complicated to implement.

Nevertheless, the code snippets also demonstrate that actual FP languages are much better suited for FP than Java. Among the things that I noticed were:

  • The syntax for defining functions (= anonymous subclasses of the Function class) is very verbose. This is alleviated by the recent extensions in Java, which allow defining lambdas in-place and other shortcuts. Similarly for other imperative programming languages (e.g., C++).
  • Although Java’s type system allows restricting the input and output types of a function, the syntax for defining types is hard to read due to the nested brackets < and >.
  • Java’s type inference mechanisms are not powerful enough. For example, the call to map in the final listing above required manually fixing the type parameters of map. FP languages are typically able to infer such type information.
  • FP benefits from using pure, side effect-free functions. Pure FP languages such as Haskell don’t even allow side effects. Purity and immutability of data makes reasoning over FP programs easier and is often necessary for composing functions in a meaningful way.
  • At some point, a way to define type classes and infer type class instances would be necessary. Scala, for example, introduces implicit parameters and lets the compiler resolve them. This might mean that a direct realization of type classes is not possible in an imperative programming model.

I still think it’s interesting that these FP concepts are so universal that they can directly be implemented even in a language without support for FP.