6.19.3. Generic programming

Using a combination of DeriveGeneric, DefaultSignatures, and DeriveAnyClass, you can easily do datatype-generic programming using the GHC.Generics framework. This section gives a very brief overview of how to do it.

Generic programming support in GHC allows defining classes with methods that do not need a user specification when instantiating: the method body is automatically derived by GHC. This is similar to what happens for standard classes such as Read and Show, for instance, but now for user-defined classes.

Note

GHC used to have an implementation of generic classes as defined in the paper “Derivable type classes”, Ralf Hinze and Simon Peyton Jones, Haskell Workshop, Montreal Sept 2000, pp. 94-105. These have been removed and replaced by the more general support for generic programming.

6.19.3.1. Deriving representations

The first thing we need is generic representations. The GHC.Generics module defines a couple of primitive types that are used to represent Haskell datatypes:

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

-- | Constants, additional parameters and recursion of kind Type
newtype K1 i c p = K1 { unK1 :: c }

-- | Meta-information (constructor names, etc.)
newtype M1 i c f p = M1 { unM1 :: f p }

-- | Sums: encode choice between constructors
infixr 5 :+:
data (:+:) f g p = L1 (f p) | R1 (g p)

-- | Products: encode multiple arguments to constructors
infixr 6 :*:
data (:*:) f g p = f p :*: g p

The Generic and Generic1 classes mediate between user-defined datatypes and their internal representation as a sum-of-products:

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

class Generic1 (f :: k -> Type) where
  type Rep1 f :: k -> Type

  from1  :: f a -> Rep1 f a
  to1    :: Rep1 f a -> f a

Generic1 is used for functions that can only be defined over type containers, such as map. Note that Generic1 ranges over types of kind Type -> Type by default, but if the PolyKinds extension is enabled, then it can range of types of kind k -> Type, for any kind k.

DeriveGeneric

Since:7.2.1

Allow automatic deriving of instances for the Generic typeclass.

Instances of these classes can be derived by GHC with the DeriveGeneric extension, and are necessary to be able to define generic instances automatically.

For example, a user-defined datatype of trees

data UserTree a = Node a (UserTree a) (UserTree a) | Leaf

in a Main module in a package named foo will get the following representation:

instance Generic (UserTree a) where
  -- Representation type
  type Rep (UserTree a) =
    M1 D ('MetaData "UserTree" "Main" "package-name" 'False) (
          M1 C ('MetaCons "Node" 'PrefixI 'False) (
                M1 S ('MetaSel 'Nothing
                               'NoSourceUnpackedness
                               'NoSourceStrictness
                               'DecidedLazy)
                     (K1 R a)
            :*: M1 S ('MetaSel 'Nothing
                               'NoSourceUnpackedness
                               'NoSourceStrictness
                               'DecidedLazy)
                     (K1 R (UserTree a))
            :*: M1 S ('MetaSel 'Nothing
                               'NoSourceUnpackedness
                               'NoSourceStrictness
                               'DecidedLazy)
                     (K1 R (UserTree a)))
      :+: M1 C ('MetaCons "Leaf" 'PrefixI 'False) U1)

  -- Conversion functions
  from (Node x l r) = M1 (L1 (M1 (M1 (K1 x) :*: M1 (K1 l) :*: M1 (K1 r))))
  from Leaf         = M1 (R1 (M1 U1))
  to (M1 (L1 (M1 (M1 (K1 x) :*: M1 (K1 l) :*: M1 (K1 r))))) = Node x l r
  to (M1 (R1 (M1 U1)))                                      = Leaf

This representation is generated automatically if a deriving Generic clause is attached to the datatype. Standalone deriving can also be used.

6.19.3.2. Writing generic functions

A generic function is defined by creating a class and giving instances for each of the representation types of GHC.Generics. As an example we show generic serialization:

data Bin = O | I

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

instance GSerialize U1 where
  gput U1 = []

instance (GSerialize a, GSerialize b) => GSerialize (a :*: b) where
  gput (x :*: y) = gput x ++ gput y

instance (GSerialize a, GSerialize b) => GSerialize (a :+: b) where
  gput (L1 x) = O : gput x
  gput (R1 x) = I : gput x

instance (GSerialize a) => GSerialize (M1 i c a) where
  gput (M1 x) = gput x

instance (Serialize a) => GSerialize (K1 i a) where
  gput (K1 x) = put x

A caveat: this encoding strategy may not be reliable across different versions of GHC. When deriving a Generic instance is free to choose any nesting of :+: and :*: it chooses, so if GHC chooses (a :+: b) :+: c, then the encoding for a would be [O, O], b would be [O, I], and c would be [I]. However, if GHC chooses a :+: (b :+: c), then the encoding for a would be [O], b would be [I, O], and c would be [I, I]. (In practice, the current implementation tries to produce a more-or-less balanced nesting of :+: and :*: so that the traversal of the structure of the datatype from the root to a particular component can be performed in logarithmic rather than linear time.)

Typically this GSerialize class will not be exported, as it only makes sense to have instances for the representation types.

6.19.3.3. Unlifted representation types

The data family URec is provided to enable generic programming over datatypes with certain unlifted arguments. There are six instances corresponding to common unlifted types:

data family URec a p

data instance URec (Ptr ()) p = UAddr   { uAddr#   :: Addr#   }
data instance URec Char     p = UChar   { uChar#   :: Char#   }
data instance URec Double   p = UDouble { uDouble# :: Double# }
data instance URec Int      p = UInt    { uInt#    :: Int#    }
data instance URec Float    p = UFloat  { uFloat#  :: Float#  }
data instance URec Word     p = UWord   { uWord#   :: Word#   }

Six type synonyms are provided for convenience:

type UAddr   = URec (Ptr ())
type UChar   = URec Char
type UDouble = URec Double
type UFloat  = URec Float
type UInt    = URec Int
type UWord   = URec Word

As an example, this data declaration:

data IntHash = IntHash Int#
  deriving Generic

results in the following Generic instance:

instance 'Generic' IntHash where
  type 'Rep' IntHash =
    'D1' ('MetaData "IntHash" "Main" "package-name" 'False)
      ('C1' ('MetaCons "IntHash" 'PrefixI 'False)
        ('S1' ('MetaSel 'Nothing
                        'NoSourceUnpackedness
                        'NoSourceStrictness
                        'DecidedLazy)
              'UInt'))

A user could provide, for example, a GSerialize UInt instance so that a Serialize IntHash instance could be easily defined in terms of GSerialize.

6.19.3.4. Generic defaults

The only thing left to do now is to define a “front-end” class, which is exposed to the user:

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

  default put :: (Generic a, GSerialize (Rep a)) => a -> [Bin]
  put = gput . from

Here we use a default signature to specify that the user does not have to provide an implementation for put, as long as there is a Generic instance for the type to instantiate. For the UserTree type, for instance, the user can just write:

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

The default method for put is then used, corresponding to the generic implementation of serialization. If you are using DeriveAnyClass, the same instance is generated by simply attaching a deriving Serialize clause to the UserTree datatype declaration. For more examples of generic functions please refer to the generic-deriving package on Hackage.

6.19.3.5. More information

For more details please refer to the Haskell Wiki page or the original paper [Generics2010].

[Generics2010]

Jose Pedro Magalhaes, Atze Dijkstra, Johan Jeuring, and Andres Loeh. A generic deriving mechanism for Haskell. Proceedings of the third ACM Haskell symposium on Haskell (Haskell‘2010), pp. 37-48, ACM, 2010.