Difference between OOP interfaces and FP type classes [duplicate]

Possible Duplicate:
Java's Interface and Haskell's type class: differences and similarities?

When I started learning Haskell, I was told that type classes are different and more powerful than interfaces.

One year later, I've used interfaces and type classes extensively and I've yet to see an example or explanation of how they are different. It's either not a revelation that comes naturally, or I've missed something obvious, or there is in actual fact no real difference.

Searching the Internet hasn't turned up anything substantial. So SO, do you have the answer?

Solution 1:

You can look at this from multiple angles. Other people will disagree, but I think OOP interfaces are a good place to start from to understand type classes (certainly compared to starting from nothing at all).

People like to point out that conceptually, type classes classify types, much like sets - "the set of types which support these operations, along with other expectations which can't be encoded in the language itself". It makes sense and is occasionally done to declare a type class with no methods, saying "only make your type an instance of this class if it meets certain requirements". That happens very rarely with OOP interfaces¹.

In terms of concrete differences, there are multiple ways in which type classes are more powerful than OOP interfaces:

• The biggest one is that type classes decouple the declaration that a type implements an interface from the declaration of the type itself. With OOP interfaces, you list the interfaces a type implements when you define it, and there's no way to add more later. With type classes, if you make a new type class which a given type "up the module hierarchy" could implement but doesn't know about, you can write an instance declaration. If you have a type and a type class from separate third parties which don't know about each other, you can write an instance declaration for them. In analogous cases with OOP interfaces, you're mostly just stuck, though OOP languages have evolved "design patterns" (adapter) to work around the limitation.

• The next biggest one (this is subjective, of course) is that while conceptually, OOP interfaces are a bunch of methods which can be invoked on objects implementing the interface, type classes are a bunch of methods which can be used with types which are members of the class. The distinction is important. Because type class methods are defined with reference to the type, rather than the object, there's no obstacle to having methods with multiple objects of the type as parameters (equality and comparison operators), or which return an object of the type as a result (various arithmetic operations), or even constants of the type (minimum and maximum bound). OOP interfaces just can't do this, and OOP languages have evolved design patterns (e.g. virtual clone method) to work around the limitation.

• OOP interfaces can only be defined for types; type classes can also be defined for what are called "type constructors". The various collection types defined using templates and generics in the various C-derived OOP languages are type constructors: List takes a type T as an argument and constructs the type List<T>. Type classes let you declare interfaces for type constructors: say, a mapping operation for collection types which calls a provided function on each element of a collection, and collects the results in a new copy of the collection - potentially with a different element type! Again, you can't do this with OOP interfaces.

• If a given parameter needs to implement multiple interfaces, with type classes it's trivially easy to list which ones it should be a member of; with OOP interfaces, you can only specify a single interface as the type of a given pointer or reference. If you need it to implement more, your only options are unappealing ones like writing one interface in the signature and casting to the others, or adding separate parameters for each interface and requiring that they point to the same object. You can't even resolve it by declaring a new, empty interface which inherits from the ones you need, because a type won't automatically be considered as implementing your new interface just because it implements its ancestors. (If you could declare implementations after the fact, this wouldn't be such a problem, but yeah, you can't do that either.)

• Sort of the reverse case of the one above, you can require that two parameters have types that implement a particular interface and that they be the same type. With OOP interfaces you can only specify the first part.

• Instance declarations for type classes are more flexible. With OOP interfaces, you can only say "I'm declaring a type X, and it implements interface Y", where X and Y are specific. With type classes, you can say "all List types whose element types satisfy these conditions are members of Y". (You can also say "all types which are members of X and Y are also members of Z", although in Haskell this is problematic for a number of reasons.)

• So-called "superclass constraints" are more flexible than mere interface inheritance. With OOP interfaces, you can only say "for a type to implement this interface, it must also implement these other interfaces". That's the most common case with type classes as well, but superclass constraints also let you say things like "SomeTypeConstructor must implement so-and-so interface", or "results of this type function applied to the type must satisfy so-and-so constraint", and so on.

• This is currently a language extension in Haskell (as are type functions), but you can declare type classes involving multiple types. For example, an isomorphism class: the class of pairs of types where you can convert from one to the other and back without losing information. Again, not possible with OOP interfaces.

• I'm sure there's more.

It's worth noting that in OOP languages which add generics, some of these limitations can be erased (fourth, fifth, possibly second points).

On the other side, there are two significant things which OOP interfaces can do and type classes natively don't:

• Runtime dynamic dispatch. In OOP languages, it's trivial to pass around and store pointers to an object implementing an interface, and invoke methods on it at runtime which will be resolved according to the dynamic, runtime type of the object. By contrast, type class constraints are by default all determined at compile time -- and perhaps surprisingly, in the vast majority of cases this is all you need. If you do need dynamic dispatch, you can use what are called existential types (which are currently a language extension in Haskell): a construct where it "forgets" what the type of an object was, and only remembers (at your option) that it obeyed certain type class constraints. From that point, it behaves basically in the exact same way as pointers or references to objects implementing interfaces in OOP languages, and type classes have no deficit in this area. (It should be pointed out that if you have two existentials implementing the same type class, and a type class method which requires two parameters of its type, you can't use the existentials as parameters, because you can't know whether or not the existentials had the same type. But compared to OOP languages, which can't have such methods in the first place, this is no loss.)

• Runtime casting of objects to interfaces. In OOP languages, you can take a pointer or reference at runtime and test whether it implements an interface, and "cast" it to that interface if it does. Type classes don't natively have anything equivalent (which is in some respects an advantage, because it preserves a property called parametricity, but I won't get into that here). Of course, there's nothing stopping you from adding a new type class (or augmenting an existing one) with methods to cast objects of the type to existentials of whichever type classes you want. (You can also implement such a capability more generically as a library, but it's considerably more involved. I plan to finish it and upload it to Hackage someday, I promise!)

I should point out that while you can do these things, many people consider emulating OOP that way bad style and suggest you use more straightforward solutions, such as explicit records of functions instead of type classes. With full first-class functions, that option is no less powerful.

Operationally, OOP interfaces are usually implemented by storing a pointer or pointers in the object itself which point to tables of function pointers for the interfaces the object implements. Type classes are usually implemented (for languages which do polymorphism-by-boxing, like Haskell, rather than polymorphism-by-multiinstantiation, like C++) by "dictionary passing": the compiler implicitly passes the pointer to the table of functions (and constants) as a hidden parameter to each function which uses the type class, and the function gets one copy no matter how many objects are involved (which is why you get to do the things mentioned in the second point above). The implementation of existential types looks a lot like what OOP languages do: a pointer to the type class dictionary is stored along with the object as "evidence" that the "forgotten" type is a member of it.

If you've ever read about the "concepts" proposal for C++ (as it was originally proposed for C++11), it's basically Haskell's type classes reimagined for C++'s templates. I sometimes think it would be nice to have a language which simply takes C++-with-concepts, rips out the object-oriented and virtual functions half of it, cleans up the syntax and other warts, and adds existential types for when you need runtime type-based dynamic dispatch. (Update: Rust is basically this, with many other nice things.)

¹_{Serializable in Java is an interface without methods or fields and thus one of those rare occurrences.}

Solution 2:

I assume you are talking about Haskell type classes. It's not really the difference between interfaces and type classes. As the name states, a type class is just a class of types with a common set of functions (and associated types, if you enable the TypeFamilies extension).

However, Haskell's type system is in itself more powerful than, for example, C#'s type system. That allows you to write type classes in Haskell, which you can't express in C#. Even a type class as simple as Functor cannot be expressed in C#:

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

The problem with C# is that generics can't be generic themselves. In other words, in C# only types of kind * can be polymorphic. Haskell allows polymorphic type constructors, so types of any kind can be polymorphic.

This is the reason why many of the powerful generic functions in Haskell (mapM, liftA2, etc.) can't be expressed in most languages with a less powerful type system.

Solution 3:

The main difference - which makes type-classes much more flexible than interfaces - is that type-classes are independent from its data types and can be added afterwards. Another difference (at least to Java) is that you can provide default implementations. An example:

//Java
public interface HasSize {
   public int size();
   public boolean isEmpty();
}

Having this interface is nice, but there is no way to add it to an existing class without changing it. If you are lucky, the class is non-final (say ArrayList), so you could write a subclass implementing the interface for it. If the class is final (say String) you are out of luck.

Compare this to Haskell. You can write the type-class:

--Haskell
class HasSize a where
  size :: a -> Int
  isEmpty :: a -> Bool
  isEmpty x = size x == 0

And you can add existing data types to the class without touching them:

instance HasSize [a] where
   size = length

Another nice property of type-classes is the implicit invocation. E.g. if you have a Comparator in Java, you need to pass it in as explicit value. In Haskell, the equivalent Ord can be used automatically, as soon as an appropriate instance is in scope.