Instances and Dictionaries

An Idealized Operational View of Type Class Dictionary Passing

When you make a class

class Foo a where
    quux :: a -> Int
    muux :: a -> Bool

and then an instance.

data Bar = Bar 

instance Foo Bar where
    quux = \Bar -> 1
    muux = \Bar -> True

There is a desugaring processes that occurs, removing type classes.

For each class there is an associated record,

data FooD a = FooD          -- class Foo a where
    { quuxD :: a -> Int     --    quux :: a -> Int
    , muuxD :: a -> Bool    --    muux :: a -> Bool
    }

and for each instance there is associated value of that record.

barFooInstanceDictionary :: FooD Bar  
barFooInstanceDictionary = FooD      -- instance Foo Bar where
    { quuxD = \Bar -> 1              --     quux = \Bar -> 1
    , muuxD = \Bar -> True           --     muux = \Bar -> True
    }

Functions that before had class contexts

goo :: Foo a => a -> Int
goo a = quux a

are converted to functions that take an additional parameter.

This parameter is called method 'dictionary'.

gooD :: FooD a -> a -> Int -- Foo became FooD and '=>' became '->'
gooD fooDictionary a = quuxD fooDictionary a -- the context is now a parameter!

The instance method quux has become a function quuxD, a record selector for FooD.

FooD is a record of method implemenations for the Foo type class.

So if we write

test :: Int
test = quux Bar

This will get desugared

test :: Int
test = quuxD ? Bar

Somehow we need barFooInstanceDictionary to appear where the ? is.

We rely on type inference to determine that quuxD must have the type

quuxD :: FooD Bar -> Bar -> Int

and rely on the instance selection to persuade the compiler to pass barFooInstanceDictionary to quuxD:

test :: Int
test = quuxD barFooInstanceDictionary Bar

This leads to an operational view of type classes:

Type classes are a way to pass instance dictionaries implicitly.

A Simplification

In the typical case, the dictionaries are records of functions.

If we reduce slightly we get

test :: Int
test = (\Bar -> 1) Bar

So in the end, our type class desugaring moved our method implementation in front of the argument so it could be applied.

Which is where the statement

came from.