Type Classes: Not Quite Overloading

Pablo Nogueira

Updated: 26 August 2011

1. In principle, overloading (or ad-hoc polymorphism) is a mechanism for name reuse independently of any semantic relationship among names. In Haskell, overloading is achieved by means of type classes which support a less ad-hoc version of overloading, but not overloading proper, hence the title of the foundational paper by Blott and Wadler which was "How to make ad-hoc polymorphism less ad-hoc".
2. Background: type classes were originally introduced to reconcile overloading with type inference (or type reconstruction) in implicitly-typed languages of the ML family. Hindley-Damas-Milner's type-inference algorithm W can infer the most general type of a function. For example, in the case of the identity function, id x = x, algorithm W infers the parametrically polymorphic type ∀a.a→a. A parametrically polymorphic function captures families of monomorphic functions with uniform behaviour. The uniformity is illustrated by the internal representation of the function where the type of the data on which it acts is a parameter: id a x = x. The application id Int is the identity function on integers (and x must be an integer), id Float the identity function on floats, etc. The body of each monomorphic identity is identical save for the type annotation.

   In contrast, overloaded functions don't have the same behaviour. This makes type inference problematic. A hoary example is arithmetical multiplication. The values and algorithms involved in integer and floating-point multiplication are different. We can't write a single function mult to do the job. We must write different overloaded versions, e.g.:

     mult :: Int → Int → Int
     mult x y = ...  -- integer multiplication
   
     mult :: Float → Float → Float
     mult x y = ...  -- floating-point multiplication
    

   In this setting, overloading is resolved in terms of scope and type signatures of arguments, which means type signatures must be written explicitly. For example, without its type signature it is impossible to tell whether double below is a function on integers or floats:

    double x = mult x x
    

   However, providing type signatures leads to code bloating:

    double :: Int → Int
    double x = mult x x
   
    double :: Float → Float
    double x = mult x x
    

   This is unsatisfactory. Despite the different behaviour, all the versions of mult and double are about the same idea, namely, about "multiplication" and "doubling" of numbers.

3. Type classes: overloaded functions are defined by making the varying types belong to the same type class. A type class defines a collection of types that is constructed in modular fashion. For example, type class Mult is the class of types for which mult has been implemented. The programmer must provide all inhabitants (witnesses) of the class.

    class Mult a where
      mult :: a → a → a
   
    instance Mult Int where
      mult = ...  -- integer multiplication
   
    instance Mult Float where
      mult = ...  -- floating-point multiplication
    

   We can now define double x = mult x x. The type checker infers it has type ∀a. Mult a ⇒ a → a, meaning ∀a∈Mult. a → a. The idea is simple and clever: the overloaded function is now a parameter. Internally, double has type ∀a. MultD a → a → a where MultD is a dictionary type (record) with a mult member funcion. Overloading resolution for applications of double to actual values is based on the types of those values, which determine the particular instance of Mult and, consequently, the particular dictionary value of type MultD to be passed at run time.

4. However, overloading is about reusing names independently of whether a semantic relationship between types can be established by grouping them into the same type class. Even with type classes, we can't invoke overloaded functions within the same scope, e.g.:

      push :: a → Stack a → Stack a
      push :: Door → IO ()
    

   The first function is a well-known function on stacks. The second displays on the screen the pushing of an emergency door in a fire simulation program. Both functions are meant to be used in the simulation. But stacks and doors don't belong in the same class. We must resort to resolving overloading manually in terms of scope, e.g., Stack.push, Door.push. In short, we must give up overloading and its automatic resolution.

   We can't use within the same scope different abstractions sharing operator names. For instance, constructor type classes are employed in the definition of abstract data type interfaces:

    class Queue q where
      empty   :: q a
      isEmpty :: q a → Bool
      enqueue :: a → q a → q a
      head    :: q a → a
      tail    :: q a → q a
   
    length :: Queue q ⇒ q a → Int
    length q
      | isEmpty q = 0
      | otherwise = 1 + length (tail q)
    

   We can't use head, tail, and length operators together with the list counterparts within the same scope unless we qualify their names by class/module. The conflict is between operators in different classes.

   We can't define overloaded functions within the same type class:

     class Vector m where
       ...
       mult :: m a → m a → m a
       mult :: a   → m a → m a
    

   We can't overload (and override) functions in subclasses. This is why multiple subclassing is not a problem, in contrast with classes in object-oriented languages. For example:

    class A a where ..
    class A a ⇒ B a where ..
    class A a ⇒ C a where ..
    class (B a, C a) ⇒ D a where ..
   
         A
        / \
       B   C
        \ /
         D
    

   There's no ‘diamon of death‘ conflict between B's, C's and D's function names cause they are all required to differ.

   Summarising:

   1. Cannot overload names within the same class.
   2. Cannot overload names in different classes used within the same scope. Overloading takes place within the members of a class.
   3. Cannot overload names in subclasses.

5. Related stuff: can't overload value constructors nor record members.

   Value constructors play the role of type tags that help the type checker figure out the type of the value. For example, below is the type of disjoint sums:

    data Sum a b = Inl a | Inr b
    

   We cannot define overloaded value constructors:

     MkSum :: a → Sum a b
     MkSum :: b → Sum a b
    

   What would the type of MkSum 3 be ?

   We may provide type annotations to disambiguate:

     (MkSum 3) :: Sum Int Bool
    

   but this fails when both components have the same type (is 3 an Inl or an Inr?)

    (MkSum 3) :: Sum Int Int
    

   A way to disambiguate is to provide a type-tag proxy:

    data INL = INL
    data INR = INR
   
    MkSum :: INL → a → Sum a b
    MkSum :: INR → b → Sum a b
   
    (MkSum INL 3) :: Sum Int Int
    

   There is no confusion about which value is constructed. But this is resolving overloading manually, as with the original value constructors:

    Inl = MkSum INL
    Inr = MkSum INR
    

   So better to have different value constructor names.