Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

I don't think I understand type classes. I'd read somewhere that thinking of them 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.

share|improve this question

3 Answers 3

up vote 36 down vote accepted

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.

share|improve this answer
    
Ah, that makes a lot of sense. The type vs value-based dispatch is probably the big thing I wasn't thinking about properly. The issue of parametric polymorphism and more specific typing makes sense. I had just pulled that and subtyping-based interfaces together in my mind (apparently I think in Java :-/ ). –  oconnor0 Jan 15 '12 at 3:57
    
Are existential types something akin to creating subtypes of C without the presence of downcasts? –  oconnor0 Jan 15 '12 at 4:03
    
Kind of. They are a means for making a type abstract, i.e. hiding its representation. In Haskell, if you also attach class constraints to it, you can still use methods of those classes on it, but nothing else. -- Downcasts are actually a feature that is separate from both subtyping and existential quantification, and could, in principle, be added in the presence of the latter, too. Just as there are OO languages who don't provide it. –  Andreas Rossberg Jan 15 '12 at 8:02
    
PS: FWIW, wildcard types in Java are existential types, though rather limited and ad-hoc (which may be part of the reason why they are somewhat confusing). –  Andreas Rossberg Jan 15 '12 at 8:48
1  
@didierc, that would be restricted to cases that can be fully resolved statically. Moreover, to match type classes it would require a form of overloading resolution that is able to distinguish based on the return type alone (see item 1). –  Andreas Rossberg Feb 11 '13 at 14:25

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.

share|improve this answer
    
and yet there seems to be a close relationship between ML modules and Haskell type classes. cse.unsw.edu.au/~chak/papers/DHC07.html –  Steven Shaw Apr 5 at 10:33

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.