10-22-04 Using Function Objects as Strategies

In the previous article, I showed how the inconsistent interface of the Number class stymied attempts to create generic methods that worked across the various types of Number. However, in the comments someone posted an approach that in effect treats the solution as a Strategy pattern, which produced more elegant code because it completely isolated "the thing that changes" in a function object.

In deference to my friend Chuck Allison, who studied math, I will call these function objects rather than functors, as the term functor has a specific and different meaning in math. However, they are commonly called functors as well.

As I've found with a number of design patterns, the lines get kind of blurry here: we are creating function objects which perform adaptation and they are being passed into methods to be used as strategies.

Taking this approach, I rewrote the example and added the various kinds of generic methods that I had originally set out to create, and more. Here is the result:

import java.math.*;
import java.util.*;
import java.util.concurrent.atomic.*;

// Different types of function objects:
interface Combiner<T> { T combine(T x, T y); }
interface UnaryFunction<R,T> { R function(T x); }
interface Collector<T> extends UnaryFunction<T,T> {
  T result(); // Extract result of collecting parameter
}
interface UnaryPredicate<T> { boolean test(T x); }

public class Functional {
  // Calls the Combiner object on each element to combine
  // it with a running result, which is finally returned:
  public static <T> T
  reduce(Iterable<T> seq, Combiner<T> combiner) {
    Iterator<T> it = seq.iterator();
    if(it.hasNext()) {
      T result = it.next();
      while(it.hasNext())
        result = combiner.combine(result, it.next());
      return result;
    }
    // If seq is the empty list:
    return null; // Or throw exception
  }
  // Take a function object and call it on each object in
  // the list, ignoring the return value. The function
  // object may act as a collecting parameter, so it is
  // returned at the end.
  public static <T> Collector<T>
  forEach(Iterable<T> seq, Collector<T> func) {
    for(T t : seq)
      func.function(t);
    return func;
  }
  // Creates a list of results by calling a function object
  // for each object in the list:
  public static <R,T> List<R>
  transform(Iterable<T> seq, UnaryFunction<R,T> func) {
    List<R> result = new ArrayList<R>();
    for(T t : seq)
      result.add(func.function(t));
    return result;
  }
  // Applies a unary predicate to each item in a sequence,
  // and returns a list of items that produced "true":
  public static <T> List<T>
  filter(Iterable<T> seq, UnaryPredicate<T> pred) {
    List<T> result = new ArrayList<T>();
    for(T t : seq)
      if(pred.test(t))
        result.add(t);
    return result;
  }
  // To use the above generic methods, we need to create
  // function objects to adapt to our particular needs:
  static class IntegerAdder implements Combiner<Integer> {
    public Integer combine(Integer x, Integer y) {
      return x + y;
    }
  }
  static class
  IntegerSubtracter implements Combiner<Integer> {
    public Integer combine(Integer x, Integer y) {
      return x - y;
    }
  }
  static class
  BigDecimalAdder implements Combiner<BigDecimal> {
    public BigDecimal combine(BigDecimal x, BigDecimal y) {
      return x.add(y);
    }
  }
  static class
  BigIntegerAdder implements Combiner<BigInteger> {
    public BigInteger combine(BigInteger x, BigInteger y) {
      return x.add(y);
    }
  }
  static class
  AtomicLongAdder implements Combiner<AtomicLong> {
    public AtomicLong combine(AtomicLong x, AtomicLong y) {
      // Not clear whether this is meaningful:
      return new AtomicLong(x.addAndGet(y.get()));
    }
  }
  // Whatever an ulp is, make a UnaryFunction with it.
  static class BigDecimalUlp
  implements UnaryFunction<BigDecimal,BigDecimal> {
    public BigDecimal function(BigDecimal x) {
      return x.ulp();
    }
  }
  static class GreaterThan<T extends Comparable<T>>
  implements UnaryPredicate<T> {
    private T bound;
    public GreaterThan(T bound) { this.bound = bound; }
    public boolean test(T x) {
      return x.compareTo(bound) > 0;
    }
  }
  static class MultiplyingIntegerCollector
  implements Collector<Integer> {
    private Integer val = 1;
    public Integer function(Integer x) {
      val *= x;
      return val;
    }
    public Integer result() { return val; }
  }
  public static void main(String[] args) {
    // A very cool effect of generics, varargs & boxing:
    List<Integer> li = Arrays.asList(1, 2, 3, 4, 5, 6, 7);
    Integer result = reduce(li, new IntegerAdder());
    System.out.println(result);

    result = reduce(li, new IntegerSubtracter());
    System.out.println(result);

    System.out.println(
      filter(li, new GreaterThan<Integer>(4)));

    System.out.println(forEach(li,
      new MultiplyingIntegerCollector()).result());

    System.out.println(
      forEach(filter(li, new GreaterThan<Integer>(4)),
        new MultiplyingIntegerCollector()).result());

    MathContext mc = new MathContext(7);
    List<BigDecimal> lbd = Arrays.asList(
      new BigDecimal(1.1, mc), new BigDecimal(2.2, mc),
      new BigDecimal(3.3, mc), new BigDecimal(4.4, mc));
    BigDecimal rbd = reduce(lbd, new BigDecimalAdder());
    System.out.println(rbd);

    System.out.println(filter(lbd,
      new GreaterThan<BigDecimal>(new BigDecimal(3))));

    // Use the prime-generation facility of BigInteger:
    List<BigInteger> lbi = new ArrayList<BigInteger>();
    BigInteger bi = BigInteger.valueOf(11);
    for(int i = 0; i < 11; i++) {
      lbi.add(bi);
      bi = bi.nextProbablePrime();
    }
    System.out.println(lbi);

    BigInteger rbi = reduce(lbi, new BigIntegerAdder());
    System.out.println(rbi);
    // The sum of this list of primes is also prime:
    System.out.println(rbi.isProbablePrime(5));

    List<AtomicLong> lal = Arrays.asList(
      new AtomicLong(11), new AtomicLong(47),
      new AtomicLong(74), new AtomicLong(133));
    AtomicLong ral = reduce(lal, new AtomicLongAdder());
    System.out.println(ral);

    System.out.println(transform(lbd,new BigDecimalUlp()));
  }
}
/*Output:
28
-26
[5, 6, 7]
5040
210
11.000000
[3.300000, 4.400000]
[11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
311
true
265
[0.000001, 0.000001, 0.000001, 0.000001]
*/

I begin by defining interfaces for different types of function objects. These were created on demand, as I developed the different methods and discover the need for each. The Combiner is the class suggested by the anonymous poster. Note that this abstracts away the detail that I was trying to add two objects, and just says that they are being combined somehow. As a result, you can see that IntegerAdder and IntegerSubtracter can be types of Combiner.

A UnaryFunction takes a single argument and produces a result; the argument and result need not be of the same type. A Collector may be used as a "Collecting Parameter" and you can extract the result when you're finished. A UnaryPredicate produces a boolean result. There are other types of function objects that can be defined but these are enough to make the point.

The Functional class contains a number of generic methods that apply function objects to sequences. reduce() applies the function in a Combiner to each element of a sequence in order to produce a single result.

forEach() takes a Collector and applies its function to each element, ignoring the result of each function call. This could be called just for the side effect (which wouldn't be a "functional" style of programming but can still be useful) or the Collector could maintain internal state to become a collecting parameter, as will be the case in this example.

transform() produces a list by calling a UnaryFunction on each object in the sequence and capturing the result.

Finally, filter() applies a UnaryPredicate to each object in a sequence and keeps the ones that produce true in a list, which it returns.

There are more generic functions like this that you can define. The C++ STL, for example, has lots of them.

In C++, latent typing takes care of matching up operations when you call functions, but in Java we need to write the function objects to adapt the generic methods to our particular needs. So the next part of the class shows various different implementations of the function objects. Note, for example, that IntegerAdder and BigDecimalAdder solve the same problem – adding two objects – by calling the appropriate operations for their particular type. So that's the adaptation and strategy in one.

In main(), you can see the various different generic method calls. Note the very first line: a very succinct side effect of generics, varargs and boxing generates the List<Integer>.

You can see that in each method call, a sequence is passed along with the appropriate function object. Also, a number of the expressions can get fairly complex, such as:

forEach(filter(li, new GreaterThan(4)),
        new MultiplyingIntegerCollector()).result()

This produces a list by selecting all elements in li that are greater than 4, and then applies the MultiplyingIntegerCollector() to the resulting list and extracts the result(). I won't explain the details of the rest of the code other than to say that you can probably figure it out by walking through it.

Feedback Wiki Page