The untold art of Composite-friendly interfaces

The Composite pattern is a very powerful design pattern that you use regularly to manipulate a group of things through the very same interface than a single thing. By doing so you don’t have to discriminate between the singular and plural cases, which often simplifies your design.

Yet there are cases where you are tempted to use the Composite pattern but the interface of your objects does not fit quite well. Fear not, some simple refactorings on the methods signatures can make your interfaces Composite-friendly, because it’s worth it.

Always start with examples

Imagine an interface for a financial instrument with a getter on its currency:

public interface Instrument {
  Currency getCurrency();
}

This interface is alright for a single instrument, however it does not scale for a group of instruments (Composite pattern), because the corresponding getter in the composite class would look like (notice that return type is now a collection):

public class CompositeInstrument {
  // list of instruments...

  public Set getCurrencies() {...}
}

We must admit that each instrument in a composite instrument may have a different currency, hence the composite may be multi-currency, hence the collection return type. This breaks the goal of the Composite pattern which is to unify the interfaces for single and multiple elements. If we stop there, we now have to discriminate between a single Instrument and a CompositeInstrument, and we have to discriminate that on every call site. I’m not happy with that.

The composite pattern applied to a lamp: same plug for one or several lamps

The brutal approach

The brutal approach is to generalize the initial interface so that it works for the composite case:

public interface Instrument {
  Set getCurrencies() ;
}

This interface now works for both the single case and the composite case, but at the cost of always having to deal with a collection as return value. In fact I’m not that sure that we’ve simplified our design with this approach: if the composite case is not used that often, we even have complicated the design for little benefit, because the returned collection type always goes on our way, requiring a loop every time it is called.

The trick to improve that is just to investigate what our interface is really used for. The getter on the initial interface only reveals that we did not think about the actual use before, in other words it shows a design decision “by default”, or lack of.

Turn it into a boolean method

Very often this kind of getter is mostly used to test whether the instrument (single or composite) has something to do with a given currency, for example to check if an instrument is acceptable for a screen in USD or tradable by a trader who is only granted the right to trade in EUR.

In this case, you can revamp the method into another intention-revealing method that accepts a parameter and returns a boolean:

public interface Instrument {
  boolean isInCurrency(Currency currency);
}

This interface remains simple, is closer to our needs, and in addition it now scales for use with a Composite, because the result for a Composite instrument can be derived from each result on each single instrument and the AND operator:

public class CompositeInstrument {
  // list of instruments...

  public boolean isInCurrency(Currency currency) {
     boolean result;
     // for each instrument, result &= isInCurrency(currency);
     return result;
  }
}

Something to do with Fold

As shown above the problem is all about the return value. Generalizing on boolean and their boolean logic from the previous example (‘&=’), the overall trick for a Composite-friendly interface is to define methods that return a type that is easy to fold over successive executions. For example the trick is to merge (“fold”) the boolean result of several calls into one single boolean result. You typically do that with AND or OR on boolean types.

If the return type is a collection, then you could perhaps merge the results using addAll(…) if it makes sense for the operation.

Technically, this is easily done when the return type is closed under an operation (magma), i.e. when the result of some operation is of the same type than the operand, just like ‘boolean1 AND boolean2‘ is also a boolean.

This is obviously the case for boolean and their boolean logic, but also for numbers and their arithmetic, collections and their sets operations, strings and their concatenation, and many other types including your own classes, as Eric Evans suggests you favour “Closure of Operations” in his book Domain-Driven Design.

Fire hydrants: from one pipe to multiple pipes (composite)

Turn it into a void method

Though not possible in our previous example, void methods work very well with the Composite pattern: with nothing to return, there is no need to unify or fold anything:

public class CompositeFunction {
  List functions = ...;

  public void apply(...) {
     // for each function, function.apply(...);
  }
}

Continuation-passing style

The last trick to help with the Composite pattern is to adopt the continuation passing style by passing a continuation object as a parameter to the method. The method then sets its result into it instead of using its return value.

As an example, to perform search on every node of a tree, you may use a continuation like this:

public class SearchResults {
   public void addResult(Node node){ // append to list of results...}
   public List getResults() { // return list of results...}
}

public class Node {
  List children = ...;

  public void search(SarchResults sr) {
     //...
     if (found){
         sr.addResult(this);
     }
     // for each child, child.search(sr);
  }
}

By passing a continuation as argument to the method, the continuation takes care of the multiplicity, and the method is now well suited for the Composite pattern. You may consider that the continuation indeed encapsulates into one object the process of folding the result of each call, and of course the continuation is mutable.

This style does complicates the interface of the method a little, but also offers the advantage of a single allocation of one instance of the continuation across every call.

That's continuation passing style (CC Some rights reserved by 2011 BUICK REGAL)

One word on exceptions

Methods that can throw exceptions (even unchecked exceptions) can complicate the use in a composite. To deal with exceptions within the loop that calls each child, you can just throw the first exception encountered, at the expense of giving up the loop. An alternative is to collect every caught exception into a Collection, then throw a composite exception around the Collection when you’re done with the loop. On some other cases the composite loop may also be a convenient place to do the actual exception handling, such as full logging, in one central place.

In closing

We’ve seen some tricks to adjust the signature of your methods so that they work well with the Composite pattern, typically by folding the return type in some way. In return, you don’t have to discriminate manually between the single and the multiple, and one single interface can be used much more often; this is with these kinds of details that you can keep your design simple and ready for any new challenge.

Follow me on Twitter! Credits: Pictures from myself, except the assembly line by BUICK REGAL (Flickr)

Read More

Thinking functional programming with Map and Fold in your everyday Java

In functional programming, Map and Fold are two extremely useful operators, and they belong to every functional language. If the Map and Fold operators are so powerful and essential, how do you explain that we can do our job using Java even though the Java programming language is lacking these two operators? The truth is that you already do Map and Fold when you code in Java, except that you do them by hand each time, using loops.

Disclaimer: I’m not a reference in functional programming and this article is nothing but a gentle introduction; FP aficionados may not appreciate it much.

You’re already familiar with it

Imagine a List<Double> of VAT-excluded amounts. We want to convert this list into another corresponding list of VAT-included amounts. First we define a method to add the VAT to one single amount:

public double addVAT(double amount, double rate) {return amount * (1 + rate);}

Now let’s apply this method to each amount in the list:

public List<Double> addVAT(List<Double> amounts, double rate){
  final List<Double> amountsWithVAT = new ArrayList<Double>();
  for(double amount : amounts){
     amountsWithVAT.add(addVAT(amount, rate));
  }
  return amountsWithVAT;
}

Here we create another output list, and for each element of the input list, we apply the method addVAT() to it and then store the result into the output list, which has the exact same size. Congratulations, as we have just done, by hand, a Map on the input list of the method addVAT(). Let’s do it a second time.

Now we want to convert each amount into another currency using the currency rate, so we need a new method for that:

public double convertCurrency(double amount, double currencyRate){return amount / currencyRate;}

Now we can apply this method to each element in the list:

public List<Double> convertCurrency(List<Double> amounts, double currencyRate){
   final List<Double> amountsInCurrency = new ArrayList<Double>();
   for(double amount : amounts){
      amountsInCurrency.add(convertCurrency(amount, currencyRate));
   }
   return amountsInCurrency;
}

Notice how the two methods that accept a list are similar, except the method being called at step 2:

  1. create an output list,
  2. call the given method for each element from the input list and store the result into the output list
  3. return the output list.

You do that often in Java, and that’s exactly what the Map operator is: apply a given method someMethod(T):T to each element of a list<T>, which gives you another list<T> of the same size.

Functional languages recognize that this particular need (apply a method on each element of a collection) is very common so they encapsulate it directly into the built-in Map operator. This way, given the addVAT(double, double) method, we could directly write something like this using the Map operator:

List amountsWithVAT = map (addVAT, amounts, rate)

Yes the first parameter is a function, as functions are first-class citizens in functional languages so they can be passed as parameter. Using the Map operator is more concise and less error-prone than the for-loop, and the intent is also much more explicit, but we don’t have it in Java…

So the point of these examples is that you are already familiar, without even knowing, with a key concept of functional programming: the Map operator.

And now for the Fold operator

Coming back to the list of amounts, now we need to compute the total amount as the sum of each amount. Super-easy, let’s do that with a loop:

public double totalAmount(List<Double> amounts){
   double sum = 0;
   for(double amount : amounts){
      sum += amount;
   }
   return sum;
}

Basically we’ve just done a Fold over the list, using the function ‘+=’ to fold each element into one element, here a number, incrementally, one at a time. This is similar to the Map operator, except that the result is not a list but a single element, a scalar.

This is again the kind of code you commonly write in Java, and now you have a name for it in functional languages: “Fold” or “Reduce”. The Fold operator is usually recursive in functional languages, and we won’t describe it here. However we can achieve the same intent in an iterative form, using some mutable state to accumulate the result between iterations. In this approach, the Fold takes a method with internal mutable state that expects one element, e.g. someMethod(T), and applies it repeatedly to each element from the input list<T>, until we end up with one single element T, the result of the fold operation.

Typical functions used with Fold are summation, logical AND and OR, List.add() or List.addAll(), StringBuilder.append(), max or min etc.. The mindset with Fold is similar to aggregate functions in SQL.

Thinking in shapes

Thinking visually (with sloppy pictures), Map takes a list of size n and returns another list of the same size:

On the other hand, Fold takes a list of size n and returns a single element (scalar):

You may remember my previous articles on predicates, which are often used to filter collections into collections with less elements. In fact this filter operator is the third standard operator that complements Map and Fold in most functional languages.

Eclipse template

Since Map and Fold are quite common it makes sense to create Eclipse templates for them, e.g. for Map:

Getting closer to map and fold in Java

Map and Fold are constructs that expect a function as a parameter, and in Java the only way to pass a method is to wrap it into a interface.

In Apache Commons Collections, two interfaces are particularly interesting for our needs: Transformer, with one method transform(T):T, and Closure, with one single method execute(T):void. The class CollectionUtils offers the method collect(Iterator, Transformer) which is basically a poor-man Map operator for Java collections, and the method forAllDo() that can emulate the Fold operator using closures.

With Google Guava the class Iterables offers the static method transform(Iterable, Function) which is basically the Map operator.

List<Double> exVat = Arrays.asList(new Double[] { 99., 127., 35. });
 Iterable<Double> incVat = Iterables.transform(exVat, new Function<Double, Double>() {
   public Double apply(Double exVat) {
     return exVat * (1.196);
   }
 });
 System.out.println(incVat); //print [118.404, 151.892, 41.86]

A similar transform() method is also available on the classes Lists for Lists and Maps for Maps.

To emulate the Fold operator in Java, you can use a Closure interface, e.g. the Closure interface in Apache Commons Collection, with one single method with only one parameter, so you must keep the current -mutable- state internally, just like ‘+=’ does.

Unfortunately there is no Fold in Guava, though it is regularly asked for, and there even no closure-like function, but it is not hard to create your own,  for example, you can implement the grand total above with something like this:

// the closure interface with same input/output type
public interface Closure<T> {
 T execute(T value);
}

// an example of a concrete closure
public class SummingClosure implements Closure<Double> {
 private double sum = 0;

 public Double execute(Double amount) {
   sum += amount; // apply '+=' operator
   return sum; // return current accumulated value
 }
}

// the poor man Fold operator
public final static <T> T foreach(Iterable<T> list, Closure<T> closure) {
 T result = null;
 for (T t : list) {
   result = closure.execute(t);
 }
 return result;
}

@Test // example of use
public void testFold() throws Exception {
 SummingClosure closure = new SummingClosure();

 List<Double> exVat = Arrays.asList(new Double[] { 99., 127., 35. });
 Double result = foreach(exVat, closure);
 System.out.println(result); // print 261.0
}

Not only for collections: Fold over trees and other structures

The power of Map and Fold is not limited to simple collections, but can scale to any navigable structure, in particular trees and graphs.

Imagine a tree using a class Node with its children. It may be a good idea to code once the Depth-First and the Breadth-First searches (DFS & BFS) into two generic methods that accept a Closure as single parameter:

public class Node ...{
   ...
   public void dfs(Closure closure){...}
   public void bfs(Closure closure){...}
}

I have regularly used this technique in the past, and I can tell it can cut the size of your classes big time, with only one generic method instead of many similar-looking methods that would each redo their own tree traversal. More importantly, the traversal can be unit-tested on its own using a mock closure. Each closure can also be unit-tested independently, and all that just makes your life so much simpler.

A very similar idea can be realized with the Visitor pattern, and you are probably already familiar with it. I have seen many times in my code and in the code of several other teams that Visitors are well-suited to accumulate state during the traversal of the data structure. In this case the Visitor is just a special case of closure to be passed for use in the folding.

One word on Map-Reduce

You probably heard of the pattern Map-Reduce, and yes the words “Map” and “Reduce” in it refer to the same functional operators Map and Fold (aka Reduce) we’ve just seen. Even though the practical application is more sophisticated, it is easy to notice that Map is embarrassingly parallel, which helps a lot for parallel computations.

Read More