Abstract

Type classes are Haskell’s acclaimed solution to ad-hoc overloading. This talk gives an introductory overview of type classes and their runtime witnesses, dictionaries. It asks the questions whether dictionaries should abide by Haskell’s default lazy evaluation strategy.

Conceptually, a type class is a type-level predicate: a type is an instance of a type class iff it type provides an implementation for overloaded functions. For instance, `Eq a’ declares that type `a’ implements a function `(==) :: a → a → Bool’ for checking equality.

Type classes are used as constraints on type variables, in so-called constrained polymorphic functions. E.g. `sort :: Ord a => [a] → [a]’ sorts a list with any type of elements `a’ that are an instance of the Ord type class, i.e. provide implementations for comparison.

Witnesses for type class constraints are necessary to select the appropriate implementation for the overloaded functions at runtime. For instance, if `sort’ is called with Int elements, the Int comparison must be used, versus say Float comparison for Float elements.

Two forms of witnesses have been considered in the literature, runtime type representations and so-called dictionaries, of which the latter are the most most commonly implementation, e.g. in GHC . Haskell implementations treat dictionaries just like all other data, as lazy values that may potentially consists of non-terminating computations. This way part of the type checker’s work, who has made sure that the dictionaries do exist, is simply forgotten. Is this really necessary? Can performance be gained by exploiting the strict nature of dictionaries?