Type classes vs object interfaces

Question

I don't think I understand type classes. I'd read somewhere that thinking of type classes as "interfaces" (from OO) that a type implements is wrong and misleading. The problem is, I'm having a problem seeing them as something different and how that is wrong.

For example, if I have a type class (in Haskell syntax)

class Functor f where
  fmap :: (a -> b) -> f a -> f b

How is that different than the interface [1] (in Java syntax)

interface Functor<A> {
  <B> Functor<B> fmap(Function<B, A> fn)
}

interface Function<Return, Argument> {
  Return apply(Argument arg);
}

One possible difference I can think of is that the type class implementation used at a certain invocation is not specified but rather determined from the environment -- say, examining available modules for an implementation for this type. That seems to be an implementation artifact that could be addressed in an OO language; like the compiler (or runtime) could scan for a wrapper/extender/monkey-patcher that exposes the necessary interface on the type.

What am I missing?

[1] Note the f a argument has been removed from fmap since given it's an OO language, you'd be calling this method on an object. This interface assumes the f a argument has been fixed.

Answer 1

In their basic form, type classes are somewhat similar to object interfaces. However, in many respects, they are much more general.

1. Dispatch is on types, not values. No value is required to perform it. For example, it is possible to do dispatch on the result type of function, as with Haskell's Read class:

   class Read a where
     readsPrec :: Int -> String -> [(a, String)]
     ...
   

   Such dispatch is clearly impossible in conventional OO.

2. Type classes naturally extend to multiple dispatch, simply by providing multiple parameters:

   class Mul a b c where
     (*) :: a -> b -> c
   
   instance Mul Int Int Int where ...
   instance Mul Int Vec Vec where ...
   instance Mul Vec Vec Int where ...
   

3. Instance definitions are independent from both class and type definitions, which makes them more modular. A type T from module A can be retrofitted to a class C from module M2 without modifying the definition of either, simply by providing an instance in module M3. In OO, this requires more esoteric (and less OO-ish) language features like extension methods.

4. Type classes are based on parametric polymorphism, not subtyping. That enables more accurate typing. Consider e.g.

   pick :: Enum a => a -> a -> a
   pick x y = if fromEnum x == 0 then y else x
   

   vs.

   pick(x : Enum, y : Enum) : Enum = if x.fromEnum() == 0 then y else x
   

   In the former case, applying pick '\0' 'x' has type Char, whereas in the latter case, all you'd know about the result would be that it's an Enum. (This is also the reason why most OO languages these days integrate parametric polymorphism.)

5. Closely related is the issue of binary methods. They are completely natural with type classes:

   class Ord a where
     (<) :: a -> a -> Bool
     ...
   
   min :: Ord a => a -> a -> a
   min x y = if x < y then x else y
   

   With subtyping alone, the Ord interface is impossible to express. You need a more complicated, recursive form or parametric polymorphism called "F-bounded quantification" to do it accurately. Compare Java's Comparable and its use:

   interface Comparable<T> {
     int compareTo(T y);
   };
   
   <T extends Comparable<T>> T min(T x, T y) {
     if (x.compareTo(y) < 0)
       return x;
     else
       return y;
   }
   

On the other hand, subtyping-based interfaces naturally allow the formation of heterogeneous collections, e.g. a list of type List<C> can contain members that have various subtypes of C (although it is not possible to recover their exact type, except by using downcasts). To do the same based on type classes, you need existential types as an additional feature.

Answer 2

In addition to Andreas's excellent answer, please keep in mind that type classes are meant to streamline overloading, which affects the global name space. There is no overloading in Haskell other than what you can obtain via type classes. In contrast, when you use object interfaces, only those functions that are declared to take arguments of that interface will need to worry about the function names in that interface. So, interfaces provide local name spaces.

For example, you had fmap in an object interface called "Functor". It would be perfectly ok to have another fmap in another interface, say "Structor". Each object (or class) can pick and choose which interface it wants to implement. In contrast, in Haskell, you can have only one fmap within a particular context. You cannot import both Functor and Structor type classes into the same context.

Object interfaces are more similar to Standard ML signatures than to type classes.

Answer 3

In your concrete example (with Functor type class), Haskell and Java implementations behave differently. Imagine you have Maybe data type and want it to be Functor (it is really popular data type in Haskell, which you can easily implement in Java as well). In your Java example you will make Maybe class implement your Functor interface. So you can write the following (just pseudo code because I have c# background only) :

Maybe<Int> val = new Maybe<Int>(5);
Functor<Int> res = val.fmap(someFunctionHere);

Notice that the res has type Functor, not Maybe. So this makes Java implementation almost unusable because you lose concrete type information, and need to do casts. (at least I failed to write such an implementation where types were still present). With Haskell type classes you will get Maybe Int as a result.