51
votes

Asking this question to clarify my understanding of type classes and higher kinded types, I'm not looking for workarounds in Java.


In Haskell, I could write something like

class Negatable t where
    negate :: t -> t

normalize :: (Negatable t) => t -> t
normalize x = negate (negate x)

Then assuming Bool has an instance of Negatable,

v :: Bool
v = normalize True

And everything works fine.


In Java, it does not seem possible to declare a proper Negatable interface. We could write:

interface Negatable {
    Negatable negate();
}

Negatable normalize(Negatable a) {
    a.negate().negate();
}

But then, unlike in Haskell, the following would not compile without a cast (assume MyBoolean implements Negatable):

MyBoolean val = normalize(new MyBoolean()); // does not compile; val is a Negatable, not a MyBoolean

Is there a way to refer to the implementing type in a Java interface, or is this a fundamental limitation of the Java type system? If it is a limitation, is it related to higher-kinded type support? I think not: it looks like this is another sort of limitation. If so, does it have a name?

Thanks, and please let me know if the question is unclear!

4

4 Answers

62
votes

Actually, yes. Not directly, but you can do it. Simply include a generic parameter and then derive from the generic type.

public interface Negatable<T> {
    T negate();
}

public static <T extends Negatable<T>> T normalize(T a) {
    return a.negate().negate();
}

You would implement this interface like so

public static class MyBoolean implements Negatable<MyBoolean> {
    public boolean a;

    public MyBoolean(boolean a) {
        this.a = a;
    }

    @Override
    public MyBoolean negate() {
        return new MyBoolean(!this.a);
    }

}

In fact, the Java standard library uses this exact trick to implement Comparable.

public interface Comparable<T> {
    int compareTo(T o);
}
12
votes

In general, no.

You can use tricks (as suggested in the other answers) that will make this work, but they do not provide all of the same guarantees that the Haskell typeclass does. Specifically, in Haskell, I could define a function like this:

doublyNegate :: Negatable t => t -> t
doublyNegate v = negate (negate v)

It is now known that the argument and return value of doublyNegate are both t. But the Java equivalent:

public <T extends Negatable<T>> T doublyNegate (Negatable<T> v)
{
    return v.negate().negate();
}

doesn't, because Negatable<T> could be implemented by another type:

public class X implements Negatable<SomeNegatableClass> {
    public SomeNegatableClass negate () { return new SomeNegatableClass(); }
    public static void main (String[] args) { 
       new X().negate().negate();   // results in a SomeNegatableClass, not an X
}

This isn't particularly serious for this application, but does cause trouble for other Haskell typeclasses, e.g. Equatable. There is no way of implementing a Java Equatable typeclass without using an additional object and sending an instance of that object around wherever we send values that need comparing, (e.g:

public interface Equatable<T> {
    boolean equal (T a, T b);
}
public class MyClass
{
    String str;

    public static class MyClassEquatable implements Equatable<MyClass> 
    { 
         public boolean equal (MyClass a, MyClass b) { 
             return a.str.equals(b.str);
         } 
    }
}
...
public <T> methodThatNeedsToEquateThings (T a, T b, Equatable<T> eq)
{
    if (eq.equal (a, b)) { System.out.println ("they're equal!"); }
}  

(In fact, this is exactly how Haskell implements type classes, but it hides the parameter passing from you so you don't need to figure out which implementation to send where)

Trying to do this with just plain Java interfaces leads to some counterintuitive results:

public interface Equatable<T extends Equatable<T>>
{
    boolean equalTo (T other);
}
public MyClass implements Equatable<MyClass>
{
    String str;
    public boolean equalTo (MyClass other) 
    {
        return str.equals(other.str);
    }
}
public Another implements Equatable<MyClass>
{
    public boolean equalTo (MyClass other)
    {
        return true;
    }
}

....
MyClass a = ....;
Another b = ....;

if (b.equalTo(a))
    assertTrue (a.equalTo(b));
....

You'd expect, due to the fact that equalTo really ought to be defined symmetrically, that if the if statement there compiles, the assertion would also compile, but it doesn't, because MyClass isn't equatable with Another even though the other way around is true. But with a Haskell Equatable type class, we know that if areEqual a b works, then areEqual b a is also valid. [1]

Another limitation of interfaces versus type classes is that a type class can provide a means of creating a value which implements the type class without having an existing value (e.g. the return operator for Monad), whereas for an interface you must already have an object of the type in order to be able to invoke its methods.

You ask whether there is a name for this limitation, but I'm not aware of one. It's simply because type classes are actually different to object-oriented interfaces, despite their similarities, because they are implemented in this fundamentally different way: an object is a subtype of its interface, thus carries around a copy of the interface's methods directly without modifying their definition, while a type class is a separate list of functions each of which is customised by substituting type variables. There is no subtype relationship between a type and a type class that has an instance for the type (a Haskell Integer isn't a subtype of Comparable, for example: there simply exists a Comparable instance that can be passed around whenever a function needs to be able to compare its parameters and those parameters happen to be Integers).

[1]: The Haskell == operator is actually implemented using a type class, Eq ... I haven't used this because operator overloading in Haskell can be confusing to people not familiar with reading Haskell code.

7
votes

You're looking for generics, plus self typing. Self typing is the notion of generic placeholder that equates to the class of the instance.

However, self typing doesn't exist in java.

This can be solved with generics though.

public interface Negatable<T> {
    public T negate();
}

Then

public class MyBoolean implements Negatable<MyBoolean>{

    @Override
    public MyBoolean negate() {
        //your impl
    }

}

Some implications for implementers:

  • They must specify themselves when they implement the interface, e.g. MyBoolean implements Negatable<MyBoolean>
  • Extending MyBoolean would require one to override the negate method again.
7
votes

I interpret the question as

How can we implement ad-hoc polymorphism using typeclasses in Java?

You can do something very similar in Java, but without the type safety guarantees of Haskell - the solution presented below can throw errors at runtime.

Here is how you can do it:

  1. Define interface that represents the typeclass

    interface Negatable<T> {
      T negate(T t);
    }
    
  2. Implement some mechanism that allows you to register instances of the typeclass for various types. Here, a static HashMap will do:

    static HashMap<Class<?>, Negatable<?>> instances = new HashMap<>();
    static <T> void registerInstance(Class<T> clazz, Negatable<T> inst) {
      instances.put(clazz, inst);
    }
    @SuppressWarnings("unchecked")
    static <T> Negatable<T> getInstance(Class<?> clazz) {
      return (Negatable<T>)instances.get(clazz);
    }
    
  3. Define the normalize method that uses the above mechanism to get the appropriate instance based on the runtime class of the passed object:

      public static <T> T normalize(T t) {
        Negatable<T> inst = Negatable.<T>getInstance(t.getClass());
        return inst.negate(inst.negate(t));
      }
    
  4. Register actual instances for various classes:

    Negatable.registerInstance(Boolean.class, new Negatable<Boolean>() {
      public Boolean negate(Boolean b) {
        return !b;
      }
    });
    
    Negatable.registerInstance(Integer.class, new Negatable<Integer>() {
      public Integer negate(Integer i) {
        return -i;
      }
    });
    
  5. Use it!

    System.out.println(normalize(false)); // Boolean `false`
    System.out.println(normalize(42));    // Integer `42`
    

The main drawback is that, as already mentioned, the typeclass instance lookup can fail at runtime, not at compile-time (as in Haskell). Using a static hash map is suboptimal too, because it brings all the problems of a shared global variable, this could be mitigated with more sophisticated dependency injection mechanisms. Automatically generating typeclass instances from other typeclass instances, would require even more infrastructure (could be done in a library). But in principle, it implements ad-hoc polymorphism using typeclasses in Java.

Full code:

import java.util.HashMap;

class TypeclassInJava {
  
  static interface Negatable<T> {
    T negate(T t);

    static HashMap<Class<?>, Negatable<?>> instances = new HashMap<>();
    static <T> void registerInstance(Class<T> clazz, Negatable<T> inst) {
      instances.put(clazz, inst);
    }
    @SuppressWarnings("unchecked")
    static <T> Negatable<T> getInstance(Class<?> clazz) {
      return (Negatable<T>)instances.get(clazz);
    }
  }

  public static <T> T normalize(T t) {
    Negatable<T> inst = Negatable.<T>getInstance(t.getClass());
    return inst.negate(inst.negate(t));
  }

  static {
    Negatable.registerInstance(Boolean.class, new Negatable<Boolean>() {
      public Boolean negate(Boolean b) {
        return !b;
      }
    });
  
    Negatable.registerInstance(Integer.class, new Negatable<Integer>() {
      public Integer negate(Integer i) {
        return -i;
      }
    });
  }

  public static void main(String[] args) {
    System.out.println(normalize(false));
    System.out.println(normalize(42));
  }
}