Haskell’s type classes are one of its most powerful and distinctive features. They are also, at times, rather annoying. One of the most annoying facts about Haskell’s type classes is that they are decidedly not first class. GHC 7.4 brings first class constraints to Haskell, but most of the difficulties come from the lack of first class instance. Not having first class instances has a range of negative consequences.
For example, type class instances are automatically carried over module boundaries. If you don’t think this is a problem you have never had to deal with Control.Monad.Either and Control.Monad.Error in the same program.
The ability to have only a single instance for each class associated with a type makes little theoretical sense. Integers form a monoid under addition. Integers also form a monoid under multiplication. In fact, forming a monoid under two different operations is the crux of the definition of a semi-ring. So, why does it make any sense at all that in Haskell there can be at most one definition of “Monoid” for any type?
Scala’s implicit objects do not suffer from these limitations1. Neither do Coq’s type classes2. There have been various proposals for “first class instances”3, but none have made it into Haskell proper.
Or have they? The remainder of this blog post will show how to get first class instance in GHC 7.4.1. To the best of my knowledge this has not been published by anyone else yet (although Edward Kmett's blog has gotten pretty close4).
First of all we are going to need some language extensions, and some imports for later on:
Other than the truly evil Unsafe.Coerce, there is nothing here that threatening. No Undecidable/Incoherent/CommunistInstances. No kind polymorphism, monomorphism enabling, or data type promoting hogwash. We didn’t even import GHC.Prim, which is pretty amazing considering that without it we can’t use the Constraint keyword.
Following Kmett we define a type for explicit dictionaries
Now is the magic part. We define a function that lets us use an explicit dictionary to do implicit things
This function works, but by itself isn’t very useful. So far to produce a dictionary, you have to already have a type class instance in scope. We need a way to keep instances from taking over and flooding across module boundaries. The standard Haskell solution to this is to define a newtype. So, lets define one newtype to rule them all
Okay, this is very good for proxying types of kind *, but we really should also define
What good is this proxy definition? Well, in GHC newtypes disappear completely at runtime. That means (ignoring type families) that the representation of an instance of some class for Proxy Label Type is the same as it is for Type, so we can define a truly mischievous little function
Lets add some stuff to make working with these things friendlier
And that’s it. We have a fully functional first class instances system. Here is how you use it. Lets define a new version of the Show type class
Now, normally there is only one way to Show a thing. But, our Show' wont be so lame
Some stuff to get the instance:
Now we need a function to test. Luckily, we turned on FlexibleContexts at the beginning
In GHCi we can confirm that it works.
*Main> showInt 3
<interactive>:118:1:
No instance for (Show' Int)
arising from a use of `showInt'
Possible fix: add an instance declaration for (Show' Int)
In the expression: showInt 3
In an equation for `it': it = showInt 3
*Main> withDict stupidShowIntDict (showInt 3)
"from StupdiShow"
*Main> withDict normalShowIntDict (showInt 3)
"3"
*Main>
“Big f-ing deal” you say. “That’s what we had newtypes for. This is pretty useless.” Well, I turn to the most popular example of bad legacy design in the Haskell standard library. Monad is not a subtype of Functor, and even worse, many types have nice Monad instances, but no instances of Applicative. We can fix that.
First of all, we need to get to recreate our dictionary making machinery for Proxy1. Disturbingly, the code (up to the numerals) is identical to what we had before
Now we can define some functions to produce Functor and Applicative instances for all monads
So, now when you run into someone who for unknown reasons defined their own list type and only made it a Monad
You don’t need to be stuck. Just define a function so you don’t need to stick type signatures all over the place
And you got your Functor!
*Main> fmap (+1) $ Cons 1 Nil
<interactive>:121:1:
No instance for (Functor List)
arising from a use of `fmap'
Possible fix: add an instance declaration for (Functor List)
In the expression: fmap (+ 1)
In the expression: fmap (+ 1) $ Cons 1 Nil
In an equation for `it': it = fmap (+ 1) $ Cons 1 Nil
*Main> withDict listFunctor $ fmap (+1) $ Cons 1 Nil
Cons 2 Nil
I’m not quite ready to make this my first package on Hackage. The API still needs some kinks worked out. And, I need to do a lot more testing to see if this creates any opportunities for segmentation faults. Still, it is nice to know that passable instances are at least possible in Haskell.
1. Oliveira and Ordesky http://ropas.snu.ac.kr/~bruno/papers/TypeClasses.pdf ↩2. Sozeau and Oury http://mattam.org/research/publications/First-Class_Type_Classes.pdf ↩
3. Oliveira and Sulzmann http://www.cs.mu.oz.au/~sulzmann/manuscript/objects-unify-type-classes-gadts.ps ↩
4. The Comonad.Reader http://comonad.com/reader/2011/what-constraints-entail-part-1/ ↩
