Object orientation for functional programmers

Dear fellow functional programmers, it seems object orientation is determined on staying, so it may be time to learn something about it. In this post, we move this functional program into an object-oriented language, preserving immutability, pattern matching, composability, and type safety. The examples are in OCaml and Java, but should translate seamlessly to any functional and object-oriented languages.

type 'a list =
  | Nil
  | Cons of 'a * 'a list
(* fold_right : ('a -> 'b -> 'b) -> 'b -> 'a list -> 'b *)
let rec fold_right step base xs =
  match xs with
    | Nil -> base
    | Cons (x, xs') -> step x (fold_right step base xs')
(* map : ('a -> 'b) -> 'a list -> 'b list *)
let map f xs = 
  fold_right (fun x xs' -> Cons (f x, xs')) Nil xs

Since we are building a “List library,” we’ll put everything in one Java class.

public class List { }

I also keep the OCaml naming style for clarity, even though it looks horrendous in Java. Let’s take each part in turn.

Immutable data type

The first thing we need to move are the constructors Nil and Cons. We can make these using classes with a common interface. In this case, we choose not to expose them by making them static inner classes, but that is unimportant.

The OCaml type is polymorphic, so our Java interface (and classes) needs to be generic. Nil has no arguments, so the Java class has no fields, Cons has two, so the Java class has two fields.

Finally, because data types are immutable in OCaml, we also need to carry this property over. In Java we can make fields immutable by merely using the final keyword.

We end up with:

public class List {
  private interface list<A> { }
  private static class Nil<A> implements list<A> { }
  private static class Cons<A> implements list<A> {
    public final A element;
    public final list<A> rest;
    public Cons(A element, list<A> rest) {
      this.element = element;
      this.rest = rest;
    }
  }
}

Pattern matching

Time to handle the complicated fold_right function and, therefore, pattern matching. Object-oriented languages have a sophisticated workaround to compensate for the language’s lack of pattern matching in the form of a design pattern; Specifically, the Visitor pattern. We implement this with another interface, and add a visit method to the constructors.

public class List {
  private interface listVisitor<A, B> {
    B visit(Nil<A> xs);
    B visit(Cons<A> xs);
  }
  private interface list<A> {
    <B> B visit(listVisitor<A, B> visitor);
  }
  private static class Nil<A> implements list<A> {
    public <B> B visit(listVisitor<A, B> visitor) {
      return visitor.visit(this);
    }
  }
  private static class Cons<A> implements list<A> {
    // ...
    public <B> B visit(listVisitor<A, B> visitor) {
      return visitor.visit(this);
    }
  }
}

Ignoring the higher-order function step until the next section, with the Visitor pattern, it is straight forward to implement the fold_right method. It is a little more tedious than OCaml, but it is not difficult to see the same structure:

<A, B> B fold_right(??? step, B base, list<A> xs) {
  return xs.visit(new listVisitor<A, B>() {
    public B visit(Nil<A> xs) {
      return base;
    }
    public B visit(Cons<A> xs) {
      return step.apply(xs.element, xs.rest.visit(this));
    }
  });
}

Higher-order function

The final part of the puzzle is the higher-order functions. It needs to be something we can take as arguments, and we only really have one thing that fits that criteria: objects. So for each function signature, we simply make a class for it. This one fits the purpose of fold_right:

private interface FoldFunc<A, B> {
  B apply(A elem, B rest);
}

Which means we can also implement the map method:

private interface MapFunc<A, B> {
  B apply(A elem);
}
<A, B> list<B> map(MapFunc<A, B> f, list<A> xs) {
  return fold_right(new FoldFunc<A, list<B>>() {
    public list<B> apply(A elem, list<B> rest) {
      return new Cons<B>(f.apply(elem), rest);
    }
  }, new Nil<B>(), xs);
}

Conclusion

Even though it is a little clunky and verbose in Java, it is possible to do functional programming. Using lambdas and diamond operators does make it a little prettier, but they do not add any expressiveness.

In my book, I discuss how to move from already object-oriented code towards many of the same benefits gained from functional programming through refactoring: