Friday, February 25, 2011

Parameterized Types

I recently had a major epiphany. I always thought Java Generics was about type safety until I realized that they are an implementation of the more general term "parameterized types" and thus are about reuse. Basically, in object oriented programming there are three ways to reuse code: inheritance, composition, and parameterized types. Let's look at how to use parameterized types for reuse.

Let's use the pedantic example of sorting. You've written a new ultra fast O(n) sorting algorithm, and you want to use it to sort all kinds of things, not just integers. In the pre Java 5 world, your sorting class would also implement something like Comparable, so any implementing class would have to override compareTo() for the actual comparison. That's the inheritance way to reuse. But that means your sorting class violate SRP. Now it sorts AND compares. You could have the implementor pass in a Comparator at construction and delegate to it during sorting, that's the composition way to reuse, but you'd rather not have a third object involved for clarity. What you can do is parameterize your sorting algorithm so the type of object that is getting sorted must implement Comparable, and let the sorted object itself decide how to compare itself to other objects of the same type.

public class SuperCoolSorter<T extends Comparable<T>> {

 public T[] sort(T[] collection) {
  for (T t : collection) {
   // secret O(n) sorting
   T other = t;
   t.compareTo(other);
  }
  return collection;
 }
}

So when you want to sort BugBears:
Create a BugBear class that implements Comparable<BugBear>
public class BugBear implements Comparable<BugBear> {
  public int compareTo(BugBear other) {
    // your comparison
  }
}

then new up sorter parameterizing it with BugBears:

SuperCoolSorter<BugBear> bugBearSorter = new SuperCoolSorter<BugBear>>();
bugBearSorter.sort(// bugbear array)

You've now created a sorting class that is independent of how things it sorts get compared, yet is reusable to sort anything that implements Comparable. Of course you could just have sort take in an array of Comparable, but then you'd have to return an array of Comparable then force the client to cast. By using parameterized types, you also control which type gets returned from sort.

Although this is pretty Java Generics specific, it's a usable pattern for any language that implements parameterized types. For example, C++ using templates.

Also, loosely typed languages like Ruby, Groovy, and Smalltalk do not need the extra markup to implement this pattern. Since they are "duck typed" languages, you can just call compareTo() on the passed in objects without the all the extra ceremony.

There you have it. The third type of reuse you may have never known about.