Haskell vs. Go – Differences Between Haskell’s Type Classes and Go’s Interfaces

gohaskellpolymorphismtype-systems

I am wondering if there is a difference between Haskell's type classes and Go's interfaces. Both define types based on functions, in that way, that a value matches a type, if a function required by the type is defined for the value.

Are there any differences or are this just two names for the same thing?

Best Answer

The two concepts are very very similar. In normal OOP languages, we attach a vtable (or for interfaces: itable) to each object:

| this
v
+---+---+---+
| V | a | b | the object with fields a, b
+---+---+---+
  |
  v
 +---+---+---+
 | o | p | q | the vtable with method slots o(), p(), q()
 +---+---+---+

This allows us to invoke methods similar to this->vtable.p(this).

In Haskell, the method table is more like an implicit hidden argument:

method :: Class a => a -> a -> Int

would look like the C++ function

template<typename A>
int method(Class<A>*, A*, A*)

where Class<A> is an instance of typeclass Class for type A. A method would be invoked like

typeclass_instance->p(value_ptr);

The instance is separate from the values. The values still retain their actual type. While typeclasses allow some polymorphism, this is not subtyping polymorphism. That makes it impossible to make a list of values that satisfy a Class. E.g. assuming we have instance Class Int ... and instance Class String ..., we cannot create a heterogeneous list type like [Class] that has values like [42, "foo"]. (This is possible when you use the “existential types” extension, which effectively switches to the Go approach).

In Go, a value doesn't implement a fixed set of interfaces. Consequently it can't have a vtable pointer. Instead, pointers to interface types are implemented as fat pointers that include one pointer to the data, another pointer to the itable:

    `this` fat pointer
    +---+---+
    |   |   |
    +---+---+
 ____/    \_________
v                   v
+---+---+---+       +---+---+
| o | p | q |       | a | b | the data with
+---+---+---+       +---+---+ fields a, b
itable with method
slots o(), p(), q()

this.itable->p(this.data_ptr)

The itable is combined with the data into a fat pointer when you cast from an ordinary value to an interface type. Once you have an interface type, the actual type of the data has become irrelevant. In fact, you can't access the fields directly without going through methods or downcasting the interface (which may fail).

Go's approach to interface dispatch comes at a cost: each polymorphic pointer is twice as large as a normal pointer. Also, casting from one interface to another involves copying the method pointers to a new vtable. But once we've constructed the itable, this allows us to cheaply dispatch method calls to many interfaces, something which traditional OOP languages suffer with. Here, m is the number of methods in the target interface, and b is the number of base classes:

  • C++ does object slicing or needs to chase virtual inheritance pointers when casting, but then has simple vtable access. O(1) or O(b) cost of upcasting, but O(1) method dispatch.
  • The Java Hotspot VM doesn't have to do anything when upcasting, but upon interface method lookup does a linear search through all itables implemented by that class. O(1) upcasting, but O(b) method dispatch.
  • Python doesn't have to do anything when upcasting, but uses a linear search through a C3-linearized base class list. O(1) upcasting, but O(b²) method dispatch? I'm not sure what the algorithmic complexity of C3 is.
  • The .NET CLR uses an approach similar to Hotspot but adds another level of indirection in an attempt to optimize for memory usage. O(1) upcasting, but O(b) method dispatch.

The typical complexity for method dispatch is much better since method lookup can often be cached, but the worst case complexities are quite horrible.

In comparison, Go has O(1) or O(m) upcasting, and O(1) method dispatch. Haskell has no upcasting (constraining a type with a type class is a compile-time effect), and O(1) method dispatch.

Related Topic