Python – Difference between Python classes and Haskell typeclasses

Since both are in OCaml, We can explore the difference between generative and applicative functors easily:

module type S = sig type t end
module M = struct type t = int end

(* An Applicative functor. *)
module F (M : S) = struct
  type t = Foo of M.t list
end

module F1 = F(M)
module F2 = F(M)

(* M1 = M2 => F(M1).t ≡ F(M2).t
   This works.
*)
let x : F1.t = F2.Foo [3]


(* A Generative functor. Note the () argument *)
module F (M : S) () = struct
  type t = Foo of M.t list
end

module F1 = F(M)()
module F2 = F(M)()

(* This doesn't work anymore ! F1.t ≠ F2.t *)
let x : F1.t = F2.Foo [3]

Applicative functors are the default in OCaml, they are more appropriate when a functor application is pure (which is, arguably, the most common case). Generative functors are available since 4.02.

Generative functors are the default in SML, they are more appropriate when a functor is impure (or when doing type shenanigans). AFAIK, applicative functors are not available in any SML dialects.

In practice in OCaml, generative functors are used in general in combination with first class modules to have functions that generates a fresh type at each application. This has various use cases (heterogeneous maps, emulating singletons types, ...). In particular, this sentence from the manual is of importance: "As a side-effect of this generativity, one is allowed to unpack first-class modules in the body of generative functors."

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.