From HaskellWiki
Revision as of 09:07, 11 May 2011 by Dreixel (talk | contribs) (Changes from the paper)

Jump to: navigation, search

GHC 7.2 includes support for datatype-generic programming. This means you can have more classes for which you do not have to give an instance, like Show or Functor. This is accomplished through two new features, enabled with two new flags: DeriveGeneric and DefaultSignatures. We'll show how this all works in this page, starting with a detailed example.

Example: serialization

Suppose you are writing a class for serialization of data. You have a type Bit representing bits, and a class Serialize:

data Bit = O | I

class Serialize a where
  put :: a -> [Bit]

You might have written some instances already:

instance Serialize Int where
  put i = serializeInt i

instance Serialize a => Serialize [a] where
  put []    = []
  put (h:t) = put h ++ put t



He will have to specify an instance Serialize (UserTree a) where ... himself. This, however, is tedious, especially because most instances will probably be rather trivial, and should be derived automatically.


Generic serialization


Representation types


-- | Unit: used for constructors without arguments
data U1 p = U1

-- | Constants, additional parameters and recursion of kind *


-- | Sums: encode choice between constructors
infixr 5 :+:

-- | Products: encode multiple arguments to constructors
infixr 6 :*:


type RepUserTree a =


type RealRepUserTree a =
  -- Information about the datatype
  M1 D Data_UserTree (
  -- Leaf, with information about the constructor
      M1 C Con_Leaf U1
  -- Node, with information about the constructor
  :+: M1 C Con_Node (
            -- Constructor argument, which could have information
            -- about a record selector label
            M1 S NoSelector (
              -- Argument, tagged with P because it is a parameter
              K1 P a)
        -- Another argument, tagged with R because it is 
        -- a recursive occurrence of a type
        -- Idem


A generic function


class GSerialize f where
  gput :: f a -> [Bin]

This class looks very much like the original Serialize class, just that the type argument is of kind * -> *, since our generic representation types have this p parameter lying around. Now we need to give instances for each of the basic types. For units there's nothing to serialize:

instance GSerialize U1 where
  gput U1 = []




  gput (L1 x) = O : gput x
  gput (R1 x) = I : gput x


  gput (M1 x) = gput x

Finally, we're only left with the arguments. For these we will just use our first class, Serialize, again:

  gput (K1 x) = put x

So, if a user datatype has a parameter which is instantiated to Int, at this stage we will use the library instance for Serialize Int.

Default implementations



class Generic a where
  -- Encode the representation of a user datatype
  type Rep a :: * -> *
  -- Convert from the datatype to its representation
  from  :: a -> (Rep a) x
  -- Convert from the representation to the datatype
  to    :: (Rep a) x -> a

So, for the UserTree datatype shown before, GHC generates the following instance:

instance Generic (UserTree a) where
  type Rep (UserTree a) = RepUserTree a

  from Leaf         = L1 U1

  to (L1 U1)              = Leaf

(Note that we are using the simpler representation RepUserTree instead of the real representation RealRepUserTree, just for simplicity.)

Equipped with a Generic instance, we are ready to tell the compiler how it can serialize any representable type:

putDefault a = gput (from a)

The type of putDefault says that we can serialize any a into a list of bits, as long as that a is Generic, and its representation Rep a has a GSerialize instance. The implementation is very simple: first convert the value to its representation using from, and then call gput on that representation.

However, we still have to write a Serialize instance for the user dataype:

  put = putDefault

Using GHC's new features


Deriving representations

The Representable0 class, and all the representation types, come with GHC in the GHC.Generics module. GHC can also derive Representable0 for user types, so all the user has to do is:

{-# LANGUAGE DeriveRepresentable #-}

  deriving Representable0


More general default methods

We don't want the user to have to write the instance Serialize (UserTree a) himself, since most of the times it will just be putDefault. However, we cannot make putDefault the default implementation of the put method, because that would require adding the (Representable0 a, GSerialize (Rep0 a)) constraint to the class head. This would restrict the ability to give ad-hoc instances for types that are not representable, for instance.


{-# LANGUAGE DefaultSignatures #-}

class Serialize a where
  put :: a -> [Bit]

  put a = gput (from0 a)

With the new language pragma DefaultSignatures, GHC allows you to put the keyword default before a (new) type signature for a method inside a class declaration. If you give such a default type signature, then you have to provide a default method implementation, which will be type-checked using the default signature, and not the original one.

Now the user can simply write:

instance (Serialize a) => Serialize (UserTree a)

GHC fills out the implementation for put using the default method. It will type-check correctly because we have a Representable0 instance for UserTree, and GSerialize instances for all the representation types.

Different perspectives


The end-user


instance (Serialize a) => Serialize (UserTree a)


The generic programmer


The GHC hacker


Changes from the paper


class Encode a where
  encode :: a -> [Bit]
  encode = encode1 . from
  • To derive generic functionality to a user type, the user no longer uses deriving instance (Section 4.6.1). Instead, the user gives an instance without defining the method; GHC then uses the generic default. For instance:


  • We do not yet allow deriving Generic1 clauses. This means that functions like fmap cannot yet be easily expressed generically in GHC.
  • We cannot derive Generic instances for:
    • Datatypes with a context;
    • Existentially-quantified datatypes;
    • GADTs.