# Joachim Breitner's Homepage

## Making dictionary passing explicit in Haskell

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.

## Comments

If the function is an IO computation, reading from and writing to disk, such a thing could actually make sense :-)

Citation needed.

Have something to say? You can post a comment by sending an e-Mail to me at <mail@joachim-breitner.de>, and I will include it here.

The problem with carrying around a dictionary in data is as you mention "mappend has the choice between three dictionaries This is not a good sign, but let’s hope that they are all the same."

With some oleggery you can, however, define a typeclass as in

http://hackage.haskell.org/packages/archive/reflection/0.3.0/doc/html/Data-Reflection.html

which provides:

data Tagged s a = Tagged a

class Reifies s a | s -> a where

reflect :: Tagged s a

reify :: a -> (forall s. Reifies s a => Tagged s w) -> w

With that you can build a monoid out of arbitrary functions, and still make sure due to the phantom type parameter that they all agree on the dictionary.

Using an old version of that library I posted:

http://www.mail-archive.com/haskell-cafe@haskell.org/msg57747.html

It is an interesting exercise to update that example to use the current safer reflection API.