8

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?

5

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.

  • Thanks for [42, "foo"]. It is a vivid example. – ceving Dec 20 '16 at 15:17
  • 1
    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 '17 at 18:38
7

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.
  • Is 1. really a difference or is it just missing sugar? – ceving Dec 20 '16 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.) – Jörg W Mittag Dec 20 '16 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 '16 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 '16 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 '16 at 15:36
3

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.

  • 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 '16 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 '16 at 15:28
  • 1
    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). – Jörg W Mittag Dec 20 '16 at 17:16

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.