Joachim Breitner's Homepage

Haskell provides type classes to support polymorphism. A type class defines a few methods, which can then be implemented for a concrete type in the type class instance. This is a powerful system, but it also has it drawbacks. Most notably, each type can have at most one implementation of the type class. But sometimes you need to use a different implementation.

If, for example, you used the Binary class to store data on disk. Now you changed your data type and the binary instance, and you can not read the old data any more. One solution is to re-name your type using “newtype” and implement another type instance for that. Often, this is enough. But still, instances are not first-class-citizens. You can not pass them around or modify them, as you can pass around and modify data and functions.

Under the hood of the compiler, things look different. The ghc puts the methods of the instance in a dictionary and passes that implicitly to any functions having a (Class a) constraint. (Other implementations exist though)  If one could make that behavior explicit, one could easily modify the instance before passing it to the function. But this is unfortunately not possible.

But it is possible to pass an explicit dictionary along the data. I use the Monoid class as an example, and define a representation of the dictionary to-be-passed, as well as the dictionary of the default instance:

data MonoidDict a = MonoidDict
  { ed_mempty :: a
  , ed_mappend :: a -> a -> a
  }

monoidDict :: Monoid a => MonoidDict a
monoidDict = MonoidDict mempty mappend

(For conciseness, I ignore the mconcat method.) My first idea was to pass this instance along with data: (MonoidDict a, a). But this would not work because there are methods, such as mempty, who need the dictionary without getting passed a value to use. Therefore, I need to put the dictionary both in the covariant and the contravariant position:

newtype WithMonoidDict a = WithMonoidDict (MonoidDict a -> (MonoidDict a, a))

We need functions to clamp a dictionary to a value, and to extract it again:

wrapWithCustomMonoidDict :: MonoidDict a -> a -> WithMonoidDict a
wrapWithCustomMonoidDict dict val = WithMonoidDict $ const (dict, val)

extractFromCustomMonoidDict :: MonoidDict a -> WithMonoidDict a -> a
extractFromCustomMonoidDict dict (WithMonoidDict f) = snd (f dict)

Note that both expect the dictionary, so that it can be fed into WithMonoidDict from “both sides”. For convenience, we can define variants that use the standard instance:

wrapWithMonoidDict :: Monoid a => a -> WithMonoidDict a
wrapWithMonoidDict = wrapWithCustomMonoidDict monoidDict

extractFromMonoidDict :: Monoid a => WithMonoidDict a -> a
extractFromMonoidDict = extractFromCustomMonoidDict monoidDict

We want to be able to pass the wrapped values as any other value with a Monoid instance, so we need to declare that:

instance Monoid (WithMonoidDict a) where
    mempty = WithMonoidDict (\d -> (d, ed_mempty d))
    mappend (WithMonoidDict f1) (WithMonoidDict f2) = WithMonoidDict $ \d ->
        let (d1,v1) = f1 d
            (d2,v2) = f2 d
        in  (d1, ed_mappend d1 v1 v2)

Note that mappend has the choice between three dictionaries This is not a good sign, but let’s hope that they are all the same.

Does it work? Let’s see:

listInstance :: MonoidDict [a]
listInstance = monoidDict

reverseInstance :: MonoidDict [a]
reverseInstance = monoidDict { ed_mappend = \l1 l2 -> l2 ++ l1 }

examples = do
    let l1 = [1,2,3]
    let l2 = [4,5,6]
    putStrLn $ "Example lists: " ++ show l1 ++ " " ++ show l2
    putStrLn $ "l1 ++ l2: " ++ show (l1 ++ l2) 
    putStrLn $ "l1 `mappend` l2: " ++ show (l1 `mappend` l2) 
    putStrLn $ "Wrapped with default instance:"
    putStrLn $ "l1 `mappend` l2: " ++ show (
        extractFromMonoidDict $ wrapWithMonoidDict l1 `mappend` wrapWithMonoidDict l2)
    putStrLn $ "Same with reversed monoid instance:"
    putStrLn $ "l1 `mappend` l2: " ++ show (
        extractFromCustomMonoidDict reverseInstance $
            wrapWithCustomMonoidDict reverseInstance l1 `mappend`
            wrapWithCustomMonoidDict reverseInstance l2)

Running examples gives this output:

Example lists: [1,2,3] [4,5,6]
l1 ++ l2: [1,2,3,4,5,6]
l1 `mappend` l2: [1,2,3,4,5,6]
Wrapped with default instance:
l1 `mappend` l2: [1,2,3,4,5,6]
Same with reversed monoid instance:
l1 `mappend` l2: [4,5,6,1,2,3]

Indeed it works.

Unfortunately, this approach is not sufficient for all cases. It is perfectly valid to have a function with signature (Monoid a => Maybe a -> Maybe a), whose behavior depends on the instance of a, even when being passed Nothing and returning Nothing. Such a function would have a problem here, because the dictionary would not be passed to the function.

I wonder if it would be possible to extend the Haskell language somehow to be able to properly pass an alternative dictionary to such functions. But given that not all compilers use dictionary passing, my hopes are low.