Interface derivation in Java

Question

I am working with Java of late, and was wondering whether there was any kind of interface implementation derivation in Java. My preferred programming language is Haskell, which is in many ways antithetical to Java, but one feature that I was wondering whether Java had anything like is the ability to derive interface implementations of compound types from the interface implementations of their parameters. For example, in Haskell:

data Pair k v = Pair k v

instance (Ord k) => Ord (Pair k v) where
    compare (Pair x _) (Pair x' _) = compare x x'

This allows you to order a Pair if its first parameter can be ordered, without explicitly requiring that to be the case. However, the closest I can come to this in Java is through explicit requirement:

class Pair<K extends Comparable<K>, V> extends Comparable<Pair<K,V>> {
    K k;
    V v;
    public int compareTo(Pair<K,V> p) {
        return k.compareTo(p.k);
    }
}

Without a way of leaving the comparability to be inferred, it is impossible for me to implement a BST of pairs without ensuring that all pairs have a comparable first element, so I cannot implement any kind of Map where the first element is not explicitly required to be Comparable. Is there any way around this, other than creating a method of my BST class that attempts to compare the generic type by casting it first as comparable, and then as a Pair with a comparable key, comparing whenever comparability is possible?

Answer 1

It is not possible. Java lacks a type class mechanism; Java's interfaces merely vaguely resemble type classes, but lack any means to auto-implement an interface (amongst other, more fundamental differences from type classes). A type either implements or does not implement an interface — there's no way to make a type magically inherit at compile time something it already doesn't, nor make a type stop inheriting something it already doesn't.

It's also not possible to move the constraint down to compareTo, as that would have to happen at the definition of compareTo within Comparable.

I'd be happy for someone to prove me wrong on this.

The closest you get to Haskell style type classes on the JVM are Scala and Frege — Scala's implicit resolution mechanism is in some ways even more powerful/expressive than Haskell but also more verbose and has some fundamental limitations WRT the use of existentials and type class constraints together; Frege is just a clone of Haskell to the JVM.

---

Workaround:

Aside from a Java-specific/problem-specific, possibly pattern-based and partial, workaround, the closest one I'm aware of is explicit re-implementation of type classes (which is just a Haskell specific term/implementation of ad-hoc polymorphism).

The question linked to by bayou.io will get you started (although it's quite straightforward anyway): Constrained interface implementation. Type class instance derivation will need to happen explicitly as well — you won't get any of the type level, compile time auto-computation magic you get in Haskell or Scala or similar, but you still get the flexibility and (most?) static checking.

P.S. some Haskellers reckon that's how it should be done even in Haskell, so this might give you an idea or three: http://www.haskellforall.com/2012/05/scrap-your-type-classes.html.

Answer 2

In Java, it is often better to have a kind of "companion" interface or class for this kind of problem. In a sense, these companions are much closer to Haskell type classes than something constructed with inheritance. For comparision, this "companion" is Comparator. One advantage is that you can sort one class (say Person) with different comparators (say one for name, one for age...). In your case, the "companion" approach also solves the "generics must be more specific for this to work" problem:

public class Pair<K, V> {
    final public K k;
    final public V v;

    public Pair(K k, V v) {
        this.k = k;
        this.v = v;
    }
}

public class PairComparator<K extends Comparable<? super K>, V>
    implements Comparator<Pair<K,V>> {

    @Override
    public int compare(Pair<K, V> o1, Pair<K, V> o2) {
        return o1.k.compareTo(o2.k);
    }
}

//works for any Pairs with comparable keys:
PairComparator<String, Integer> comp = 
    new PairComparator<String, Integer>();
Pair<String, Integer> p1 = new Pair<>("z",1);
Pair<String, Integer> p2 = new Pair<>("a",3);
System.out.println(comp.compare(p1,p2));