11

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?

3 Answers 3

7

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.

2
  • Thanks for [42, "foo"]. It is a vivid example.
    – ceving
    Dec 20, 2016 at 15:17
  • 2
    Though this answer is well written and contains useful information, I think that by focusing on the implementation in the compiled code, it significantly overstates the similarities between interfaces and type classes. With type classes (and the Haskell type system more generally), most of the interesting stuff happens during compilation and isn't reflected in the final machine code.
    – K. A. Buhr
    Dec 31, 2017 at 18:38
8

There are several differences

  1. Haskell typeclasses are nominatively typed -- you have to declare that Maybe is a Monad. Go interfaces are structurally typed: if circle declares area() float64 and so does square then they both are under the interface shape automatically.
  2. Haskell (with GHC extensions) have Multi Parameter Type Classes and (like my Maybe a example) type classes for higher kinded types. Go has no equivalent for these.
  3. In Haskell, type classes are consumed with bound polymorphism which gives you constraints that are inexpressible with Go. For example + :: Num a => a -> a -> a, which ensures that you won't try to add floating point and quaternions, is inexpressible in Go.
6
  • Is 1. really a difference or is it just missing sugar?
    – ceving
    Dec 20, 2016 at 14:41
  • 1
    Go interfaces define a protocol for values, Haskell type classes define a protocol for types, that is also a pretty major difference, I would say. (That's why they are called "type classes", after all. They classify types, unlike OO classes (or Go's interfaces), which classify values.) Dec 20, 2016 at 14:55
  • 1
    @ceving, it's definitely not sugar in the normal sense: if Haskell jumped to something like Scala implicits for type classes it would break a lot of existing code.
    – walpen
    Dec 20, 2016 at 15:07
  • @JörgWMittag I'll agree there and I liked your answer: I was trying to get at more of the difference from the users perspective.
    – walpen
    Dec 20, 2016 at 15:08
  • @walpen Why does this break code? I wonder how such code could exist considering the strictness of Haskell's type system.
    – ceving
    Dec 20, 2016 at 15:36
4

They are completely different. Go interfaces define a protocol for values, Haskell type classes define a protocol for types. (That's why they are called "type classes", after all. They classify types, unlike OO classes (or Go's interfaces), which classify values.)

Go interfaces are just boring old structural typing, nothing more.

4
  • 1
    Can you explain it? Maybe even without condescending tone. What I have read states that type classes are ad-hoc polymorphism comparable to operator overloading, which is the same as interfaces in Go.
    – ceving
    Dec 20, 2016 at 15:08
  • From the Haskell tutorial: "Like an interface declaration, a Haskell class declaration defines a protocol for using an object"
    – ceving
    Dec 20, 2016 at 15:28
  • 2
    From that same tutorial (bold emphasis mine): "Type classes […] allow us to declare which types are instances of which class" The instances of a Go interface are values, the instances of a Haskell type class are types. Values and types live in two completely separate worlds (at least in languages like Haskell and Go, dependently-typed languages like Agda, Guru, Epigram, Idris, Isabelle, Coq, etc. are a different matter). Dec 20, 2016 at 17:16
  • Voting up because the answer is insightful, but I think more detail could help. And what's boring about structural typing?! It's pretty rare, and worth celebrating in my opinion.
    – Max Heiber
    Feb 13, 2020 at 23:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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