Wednesday, February 29, 2012

Haskell Supports First-Class Instances

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/

5 comments:

  1. Nice post!

    I usually call a Proxy with an argument 'Tagged'. (See Data.Tagged in 'tagged'), and reserve Proxy for a type that exists solely to carry around a phantom type argument.

    You can also probably simplify your Proxy/Tagged type so that you can share one between both of your use cases by using one with a polymorphic kind for the argument, which is available in 7.4.

    But, overall, this approach permits all sorts of evil to happen and you can violate almost any invariant you want, which is one reason why in my blog post I restricted the use of unsafeCoercing dictionaries to ones that if they existed, then by law or convention they would be required to be compatible with the one I supplied.

    This lets me dodge confluence issues.

    That said, in my 'constraints' package, you can already do this through 'underive'.

    https://github.com/ekmett/constraints/blob/master/Data/Constraint/Unsafe.hs

    which lets you lift a dictionary from a newtype to its body.

    Following your naming convention:

    newtype Stupid = Stupid Int deriving (Show) -- or otherwise
    instance Newtype Stupid Int where pack = Stupid; unpack (Stupid i) = i
    -- then you can use underive to get your result here.
    ghci> show (12 :: Int) \\ (underive Stupid :: Show Stupid :- Show Int)
    "Stupid 12"

    ReplyDelete
    Replies
    1. Thanks!

      I like the name "tagged" better. Thanks.

      I had thought about using Kind Polymorphism for this, but hadn't tried it when I wrote the post.

      I'm not sure what I think about consistency issues. Really there are two different concerns 1. are unrestricted overlapping named instances a good idea? 2. Is this the right way to achieve them?

      As to the first question it seems they are dangerous in Haskell because existing libraries may depend on the assumption that there is only one Instance for a given type. On the other-hand, first-class instances work out fine in Scala and the dependently typed languages, and I think that collapsing (extensible) records and instances will be the way forward for almost all future languages. The only exception I can think of is very performance oriented languages that require compile time resolution (C++ and similar).

      The idea of using the "Proxy"/"Tagged" type was that we would know for sure that we were really dealing with a newtype, although I guess Control.Newtype is reasonable. But, doing it this way is still broken because you can produce memory errors when it is combined with type families.

      So, its still an open question how to get more of the Scala functionality into Haskell in a safe way. In the meantime, this code (or yours) will work at the risk of invariant breaking and general unsafe badness.

      Anyways, the Constraint package is awesome.

      Delete
  2. No, no, no! Don't use unsafeCoerce, please! Play safe whenever you can - and you really can:

    {-# LANGUAGE ConstraintKinds, FlexibleInstances, GeneralizedNewtypeDeriving, MultiParamTypeClasses #-}
    module FirstClass where
    class UnProxyDict p q where unProxyDict_ :: Dict (c q) -> Dict (c p)
    instance UnProxyDict p p where unProxyDict_ = id
    newtype Proxy label p = Proxy p deriving (UnProxyDict p)
    unProxyDict :: Dict (c (Proxy label p)) -> Dict (c p)
    unProxyDict = unProxyDict_

    ReplyDelete
    Replies
    1. the safety characteristics are identical

      Delete
  3. You can use PolyKinds here, but it would require StandaloneDeriving:

    newtype Proxy label p = Proxy p
    deriving instance UnProxyDict p (Proxy label p)
    newtype Proxy1 label p x = Proxy1 (p x)
    deriving instance UnProxyDict p (Proxy1 label p)

    ReplyDelete