What I Like About Type Classes

I’ve been hacking on Steve’s¹ Accrue static analysis framework, which is implemented in Java. Unfortunately, I have a lot of trouble solving problems with object oriented languages. I usually program in either Haskell or Racket, so my intuitions for program structure are admittedly unusual to the Java crowd.

My primary conceptual challenge was how to mitigate the lack of Haskell’s type classes. I use type classes for two distinct purposes:

• assigning behavior to foreign types, i.e. those whose definition I do not control, and

• as a type-directed meta-programming facility

Assigning Behavior to Foreign Types

Sometimes, I manipulate a type whose definition I do not control. In such cases, I often want to associate additional behavior with that type. I recently ran into such an issue in Java. I wanted to define my class to work generically with any class that has a join semi-lattice on its objects.

interface Joinable<T> {
  T join(T t);
}

// the mutable version:

interface Joinable<T> {
  void join(T t);
}

I defined a class parametric on classes implementing Joinable<T> and things seemed quite swell.

class MyClass<T extends Joinable<T>> {
  // ...
    t1.join(t2);
  // ...
}

Quite swell, until, of course, I wanted to instantiate MyClass with some Set<U>. In Ruby parlance, I wanted to monkey patch the Set<U> interface to also implement a join semi-lattice. This clashed with my Haskell experience, where the implementation is straightforward:

instance Setlike a t => SemiLattice t {
  join = union
  lte  = subset
}

Type-Directed Meta-Programming

In addition to monkey patching existing types, type classes provide a hook to automatically generate “obvious” implementations of some functions. For example, there are often obvious ways to lift a function from one type to another type. The first example that comes to my mind is a product lattice. Suppose you have two semi-lattices:

(L,  ⊑ _L), (R,  ⊑ _R)

There is a natural² way to produce a product semi-lattice:

(L × R,  ⊑ _L × R)

wherein we define

(l₁, r₁) ⊑ _L × R(l₂, r₂) ≡ l₁ ⊑ _Ll₂ ∧ r₁ ⊑ _Lr₂

In Haskell, we can express this construction using type classes as follows:

instance SemiLattice a => SemiLattice b => SemiLattice (a, b) where
  lte (x,y) (x',y') = (lte x x') && (lte y y')