Type Classes: a Primer

Coined by Stra­chey1967, ad-hoc poly­mor­phism occurs when a “func­tion is defined over sev­eral dif­fer­ent types, act­ing in a dif­fer­ent way for each type.” While design­ing the Haskell type sys­tem, Wadler and Blott1989 intro­duced the mech­a­nism of type classes to extend Hind­ley-Mil­ner typ­ing and unify para­met­ric and ad-hoc poly­mor­phism.
Mod­ern pro­gram­ming lan­guages have adopted type classes to again unify ad-hoc and para­met­ric poly­mor­phism. Lan­guages such as Coq, Scala, Rust, Swift, Lean, and Pure­Script have fol­lowed suit with vary­ing imple­men­ta­tions of type classes—even if branded under a dif­fer­ent name. The remain­der of this sec­tion will intro­duce some ter­mi­nol­ogy and ordi­nary use cases for type classes. For the remain­der of the the­sis, core exam­ples are given using Rust traits. In this con­text “trait” and “type class” are syn­ony­mous. This intro­duc­tion will put Rust and Haskell side-by-side for read­ers famil­iar with Haskell.

A Class to Stringify

The sim­plest of our exam­ples defines a class to turn val­ues into a string—a com­mon oper­a­tion. To start we need to define a trait with an appro­pri­ate name and trait meth­ods.

trait ToString {
    fn to_string(&self) -> String;
}
class ToString a where
  toString :: a -> String

Shown in is a trait def­i­n­i­tion, ToString. All future trait imple­men­tors, or class instances, will pro­vide an imple­me­na­tion for each trait mem­ber—in this case, fn to_string(&self) -> String.

A trait is hardly use­full with­out imple­men­tors. imple­ments ToString for the types char and i32 (a Rust inte­ger).

impl ToString for char {
    fn to_string(&self) -> String {
        String::from(*self)
    }
}

impl ToString for i32 {
    fn to_string(&self) -> String {
        format!("{}", self)
    }
}
instance ToString Char where
  toString a = [a]

instance ToString Int where
  toString a = show a

Both of these imple­men­ta­tions are facts, that is, they declare that each respec­tive type is an imple­men­tor of the ToString trait. (Note that the Haskell imple­men­ta­tion toString a = [a] takes advan­tage of the fact that in Haskell type String = [Char].)The imple­men­ta­tion for inte­gers, impl ToString for i32, uses built-in for­mat­ting func­tions to stringify the pro­vided inte­ger. To min­i­mize code, assume that the show func­tion is “built-in,” and not a class mem­ber.

With some basic imple­men­tors we can already start to use the trait. Let’s write a sim­ple func­tion, print_ln, that will print a value to the con­sole.

fn print_ln<T>(v: T)
  where T: ToString {
    println!("{}", v.to_string());
}
printLn :: ToString t => t -> IO ()
printLn = putStrLn . toString

The print_ln func­tion is para­me­ter­ized over a type T, and uses the trait method v.to_string() to stringify v then print it to std­out. How­ever, it does so in the con­text T: ToString. A con­text defines a set of pred­i­cates that must hold in order to invoke a func­tion. For this func­tion, that pred­i­cate is that the type T: ToString (read as “tee imple­ments to string”). By pro­vid­ing this trait bound in the where con­text, Rust knows that there exists a method to_string on v.

Traits abstract over shared behav­ior. The ToString trait declares the behav­ior of types that can be con­verted into a string, trait imple­men­tors pro­vide this behav­ior by imple­ment­ing con­crete mem­ber func­tion instances. Defin­ing every type an imple­men­tor would be a tedious process and so far we haven’t seen wherein the power of traits lies. To demon­strate this, let’s con­sider how we might use our cur­rent ToString imple­men­tors to stringify a vec­tor. A naïve devel­oper might want to pro­vide the sep­a­rate imple­men­ta­tions shown in .

impl ToString for Vec<char> {
  fn to_string(&self) -> String {
    format!("[{}]",
      self.iter()
          .map(ToString::to_string)
          .collect::<Vec<_>>()
          .join(", ")
    )
  }
}
impl ToString for Vec<i32> {
  fn to_string(&self) -> String {
    format!("[{}]",
      self.iter()
          .map(ToString::to_string)
          .collect::<Vec<_>>()
          .join(", ")
    )
  }
}

Of course this is redun­dant, the imple­men­ta­tions are equiv­a­lent. Any vec­tor whose ele­ments imple­ment ToString can share the same imple­men­ta­tion. Traits of course allow for this abstrac­tion, imple­men­ta­tions can be para­met­ric, thus chain­ing imple­men­ta­tion blocks together. The pre­vi­ous two dec­la­ra­tions would canon­i­cally be imple­mented as in .

impl<T> ToString for Vec<T>
  where T: ToString, {
  fn to_string(&self) -> String {
    format!("[{}]",
      self.iter()
          .map(ToString::to_string)
          .collect::<Vec<_>>()
          .join(", ")
    )
  }
}
instance ToString a => ToString [a] where
  toString a = "[" ++ listWSep ++ "]"
    where
      listOfStrs = map toString a
      listWSep = intercalate ", " listOfStrs

Sim­i­lar to the def­i­n­i­tion of print_ln ear­lier, the imple­men­ta­tions in are para­met­ric over T and rely on a con­text. Writ­ing this dec­la­ra­tion in Eng­lish we might say “a vec­tor imple­ments ToString if its ele­ments imple­ment ToString.”

The trait machin­ery of Rust will “fig­ure out” which imple­men­ta­tions to call when print_ln is invoked with vec­tors of char­ac­ters or inte­gers. The fig­ur­ing out process in Rust is called trait res­o­lu­tion. A com­plex process and the topic of this work.

print_ln(vec!['a', 'b', 'c']) // "[a, b, c]"

print_ln(vec![1, 2, 3]) // "[1, 2, 3]"