Understanding typeclass polymorphism

Overview

Understanding type class polymorphism by translation into higher-order functions (dictionary passing).

References

1. “How to make ad-hoc polymorphism less ad-hoc” Philip Wadler and Stephen Blott, 1989 PS
2. Implementing, and Understanding Type Classes, Caml mailing list, Oleg Kiseylov, 2007 web

Code examples: https://github.com/pbv/tapf-classes

A simple class

class Show a where
   show :: a -> String

instance Show Bool where
  show b = if b then "True" else "False"

instance Show Int where
  show = showInt  -- showInt :: Int -> String

print :: Show a => a -> IO () 
print x = putStrLn (show x)

How can this be implemented?

Dictionary passing

• Each class declaration corresponds to a data type declaration for the record of operations (the dictionary)
• Each instance declaration corresponds to a value of the corresponding dictionary type
• Overloaded functions take dictionaries as extra parameters

Implementing our example

data ShowD a = ShowD { -- dictionary for Show
    show :: a -> String
    }

showDBool :: ShowD Bool  -- instance for Bool
showDBool = ShowD {
    show = \b -> if b then "True" else "False"
    }

showDInt :: ShowD Int    -- instance for Int
showDInt = ShowD { show = showInt }

print :: ShowD a -> a -> IO ()
print showD x = putStrLn (show showD x)

Numbers

-- simplified Num class
class Num a where
  fromInt :: Int -> a
  (+) :: a -> a -> a

Dictionary translation

data NumD a = NumD { fromInt :: Int -> a
                   , add :: a -> a -> a
                   }

Summing a list

sum :: Num a => [a] -> a
sum []     = 0
sum (x:xs) = x + sum xs

Translation

sum :: NumD a -> [a] -> a
sum numD []     = fromInt numD 0
sum numD (x:xs) = add numD x (sum numD xs)

Overloading with two classes

printIncr :: (Show a, Num a) => a -> IO ()
printIncr x = putStrLn (show (x+1))

Translation

printIncr :: (ShowD a, NumD a) -> a -> IO ()
printIncr (showD, numD) x
  = putStrLn (show showD (add numD x
                             (fromInt numD 1)))

Instances with constraints

instance (Eq a, Eq b) => Eq (a,b) where
  ...
instance Eq a => Eq [a] where
  ...

Instances with typeclass constraints translate as functions that construct new dictionaries from existing ones.

Example

instance Eq a where
  eq :: a -> a -> Bool

instance (Eq a, Eq b) => Eq (a,b) where
  eq (x,y) (x',y') = eq x x' && eq y y'

Translation

data EqD a = EqD { eq :: a -> a -> Bool }

eqDPair :: (EqD a, EqD b) -> EqD (a,b)
eqDPair (EqD eqA, EqD eqB)
  = EqD (\(x,y) (x',y') ->
                   eqA x x' && eqB y y')

Recursive example: equality over lists

instance Eq a => Eq [a] where
  eq [] []         = True
  eq (x:xs) (y:ys) = eq x y && eq xs ys
       -- `eq` used above at different types
  eq _      _      = False

Translation

eqDList :: EqD a -> EqD [a]
eqDList (EqD eqA) = EqD eqL
  where
    eqL [] []         = True
    eqL (x:xs) (y:ys) = eqA x y && eqL xs ys
    eqL _      _      = False

Observations

Dictionaries behave similiarly to the method suite in an OO-language:

• allow multiple dictionaries passed to a function
• allow separate compilation (modules)

Unlike OO-methods, dictionaries are passed separately from data:

• the compiler ensures that values and dictionaries “meet up” at the right place
• allows dispatching on the result type (e.g. fromInt)
• allows type safety for binary methods (e.g. ==)
• allows multi-parameter classes

Observations (cont.)

• Dictionary-passing is not only implementation technique (see first paper for references)
• GHC will use dictionary-passing in the general case but will optimize it away if it can