Swirly Mein Kopf

Friday, April 23. 2010

Making dictionary passing explicit in Haskell

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.

Trackbacks


No Trackbacks

Comments

Display comments as (Linear | Threaded)

*"It is perfectly valid to have functions with signature (Monoid a => Int -> Int)"

Citation needed.
#1 anonymous on 2010-04-23 17:08 (Reply)
*Functions with a signature like (Monoid a => Int -> Int) are not allowed, AFAIK. You'll get an 'ambiguous constraint' error.
#2 Erik on 2010-04-23 17:09 (Reply)
*And even if you could use that type, what could such a function possibly do with it that it couldn't do with Int -> Int?
#2.1 Anonymous on 2010-04-23 17:11 (Reply)
*Assume the class in question were Num and assume ScopedTypeVariables. Then the code could run something like (1 :: a) >= (0 :: a) which depends on the Num and Ord instance in question, without inputing or outputting data.

If the function is an IO computation, reading from and writing to disk, such a thing could actually make sense :-)
#2.1.1 Joachim Breitner (Homepage) on 2010-04-23 18:12 (Reply)
*Ok, I was a bit quick there. I modified the example.
#3 Joachim Breitner (Homepage) on 2010-04-23 17:49 (Reply)
*You can even turn your dictionary back, safely into a type class using reflection.

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.
#4 Edward Kmett (Homepage) on 2010-04-23 18:53 (Reply)
*Thanks, very interesting pointer. Encoding the value of a pointer in a type expression seems to be, well, bold, but it does go quite far.
#4.1 Joachim Breitner (Homepage) on 2010-04-23 20:37 (Reply)

Add Comment



To prevent automated Bots from commentspamming, please enter the string you see in the image below in the appropriate input box. Your comment will only be submitted if the strings match. Please ensure that your browser supports and accepts cookies, or your comment cannot be verified correctly.
CAPTCHA

Gravatar, Favatar, Identica author images supported.
What is the first name of the owner of this blog? / Wie heißt der Betreiber diess Blogs mit Vornamen?
 
 
Nach oben