GHC.Internal.Generics

The key to defining your own datatype-generic functions is to understand how to represent datatypes using the given set of type constructors.

Let us look at an example first:

data Tree a = Leaf a | Node (Tree a) (Tree a)
  deriving Generic

The above declaration (which requires the language pragma DeriveGeneric) causes the following representation to be generated:

instance Generic (Tree a) where
  type Rep (Tree a) =
    D1 ('MetaData "Tree" "Main" "package-name" 'False)
      (C1 ('MetaCons "Leaf" 'PrefixI 'False)
         (S1 ('MetaSel 'Nothing
                         'NoSourceUnpackedness
                         'NoSourceStrictness
                         'DecidedLazy)
                (Rec0 a))
       :+:
       C1 ('MetaCons "Node" 'PrefixI 'False)
         (S1 ('MetaSel 'Nothing
                         'NoSourceUnpackedness
                         'NoSourceStrictness
                         'DecidedLazy)
               (Rec0 (Tree a))
          :*:
          S1 ('MetaSel 'Nothing
                         'NoSourceUnpackedness
                         'NoSourceStrictness
                         'DecidedLazy)
               (Rec0 (Tree a))))
  ...

Hint: You can obtain information about the code being generated from GHC by passing the -ddump-deriv flag. In GHCi, you can expand a type family such as Rep using the :kind! command.

This is a lot of information! However, most of it is actually merely meta-information that makes names of datatypes and constructors and more available on the type level.

Here is a reduced representation for Tree with nearly all meta-information removed, for now keeping only the most essential aspects:

instance Generic (Tree a) where
  type Rep (Tree a) =
    Rec0 a
    :+:
    (Rec0 (Tree a) :*: Rec0 (Tree a))

The Tree datatype has two constructors. The representation of individual constructors is combined using the binary type constructor :+:.

The first constructor consists of a single field, which is the parameter a. This is represented as Rec0 a.

The second constructor consists of two fields. Each is a recursive field of type Tree a, represented as Rec0 (Tree a). Representations of individual fields are combined using the binary type constructor :*:.

Now let us explain the additional tags being used in the complete representation:

• The S1 ('MetaSel 'Nothing 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) tag indicates several things. The 'Nothing indicates that there is no record field selector associated with this field of the constructor (if there were, it would have been marked 'Just "recordName" instead). The other types contain meta-information on the field's strictness:

• There is no {-# UNPACK #-} or {-# NOUNPACK #-} annotation in the source, so it is tagged with 'NoSourceUnpackedness.

• There is no strictness (!) or laziness (~) annotation in the source, so it is tagged with 'NoSourceStrictness.

• The compiler infers that the field is lazy, so it is tagged with 'DecidedLazy. Bear in mind that what the compiler decides may be quite different from what is written in the source. See DecidedStrictness for a more detailed explanation.

The 'MetaSel type is also an instance of the type class Selector, which can be used to obtain information about the field at the value level.

• The C1 ('MetaCons "Leaf" 'PrefixI 'False) and C1 ('MetaCons "Node" 'PrefixI 'False) invocations indicate that the enclosed part is the representation of the first and second constructor of datatype Tree, respectively. Here, the meta-information regarding constructor names, fixity and whether it has named fields or not is encoded at the type level. The 'MetaCons type is also an instance of the type class Constructor. This type class can be used to obtain information about the constructor at the value level.

• The D1 ('MetaData "Tree" "Main" "package-name" 'False) tag indicates that the enclosed part is the representation of the datatype Tree. Again, the meta-information is encoded at the type level. The 'MetaData type is an instance of class Datatype, which can be used to obtain the name of a datatype, the module it has been defined in, the package it is located under, and whether it has been defined using data or newtype at the value level.

There are many datatype-generic functions that do not distinguish between positions that are parameters or positions that are recursive calls. There are also many datatype-generic functions that do not care about the names of datatypes and constructors at all. To keep the number of cases to consider in generic functions in such a situation to a minimum, it turns out that many of the type constructors introduced above are actually synonyms, defining them to be variants of a smaller set of constructors.

The type constructor Rec0 is a variant of K1:

type Rec0 = K1 R

Here, R is a type-level proxy that does not have any associated values.

There used to be another variant of K1 (namely Par0), but it has since been deprecated.

The type constructors S1, C1 and D1 are all variants of M1:

type S1 = M1 S
type C1 = M1 C
type D1 = M1 D

The types S, C and D are once again type-level proxies, just used to create several variants of M1.

Next to K1, M1, :+: and :*: there are a few more type constructors that occur in the representations of other datatypes.

For empty datatypes, V1 is used as a representation. For example,

data Empty deriving Generic

yields

instance Generic Empty where
  type Rep Empty =
    D1 ('MetaData "Empty" "Main" "package-name" 'False) V1

If a constructor has no arguments, then U1 is used as its representation. For example the representation of Bool is

instance Generic Bool where
  type Rep Bool =
    D1 ('MetaData "Bool" "Data.Bool" "package-name" 'False)
      (C1 ('MetaCons "False" 'PrefixI 'False) U1 :+: C1 ('MetaCons "True" 'PrefixI 'False) U1)

As :+: and :*: are just binary operators, one might ask what happens if the datatype has more than two constructors, or a constructor with more than two fields. The answer is simple: the operators are used several times, to combine all the constructors and fields as needed. However, users /should not rely on a specific nesting strategy/ for :+: and :*: being used. The compiler is free to choose any nesting it prefers. (In practice, the current implementation tries to produce a more-or-less balanced nesting, 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.)

A datatype-generic function comprises two parts:

1. Generic instances for the function, implementing it for most of the representation type constructors introduced above.

2. A wrapper that for any datatype that is in Generic, performs the conversion between the original value and its Rep-based representation and then invokes the generic instances.

As an example, let us look at a function encode that produces a naive, but lossless bit encoding of values of various datatypes. So we are aiming to define a function

encode :: Generic a => a -> [Bool]

where we use Bool as our datatype for bits.

For part 1, we define a class Encode'. Perhaps surprisingly, this class is parameterized over a type constructor f of kind * -> *. This is a technicality: all the representation type constructors operate with kind * -> * as base kind. But the type argument is never being used. This may be changed at some point in the future. The class has a single method, and we use the type we want our final function to have, but we replace the occurrences of the generic type argument a with f p (where the p is any argument; it will not be used).

class Encode' f where
  encode' :: f p -> [Bool]

With the goal in mind to make encode work on Tree and other datatypes, we now define instances for the representation type constructors V1, U1, :+:, :*:, K1, and M1.

In order to be able to do this, we need to know the actual definitions of these types:

data    V1        p                       -- lifted version of Empty
data    U1        p = U1                  -- lifted version of ()
data    (:+:) f g p = L1 (f p) | R1 (g p) -- lifted version of Either
data    (:*:) f g p = (f p) :*: (g p)     -- lifted version of (,)
newtype K1    i c p = K1 { unK1 :: c }    -- a container for a c
newtype M1  i t f p = M1 { unM1 :: f p }  -- a wrapper

So, U1 is just the unit type, :+: is just a binary choice like Either, :*: is a binary pair like the pair constructor (,), and K1 is a value of a specific type c, and M1 wraps a value of the generic type argument, which in the lifted world is an f p (where we do not care about p).

To deal with the V1 case, we use the following code (which requires the pragma EmptyCase):

instance Encode' V1 where
  encode' x = case x of { }

There are no values of type V1 p to pass, so it is impossible for this function to be invoked. One can ask why it is useful to define an instance for V1 at all in this case? Well, an empty type can be used as an argument to a non-empty type, and you might still want to encode the resulting type. As a somewhat contrived example, consider [Empty], which is not an empty type, but contains just the empty list. The V1 instance ensures that we can call the generic function on such types.

There is exactly one value of type U1, so encoding it requires no knowledge, and we can use zero bits:

instance Encode' U1 where
  encode' U1 = []

In the case for :+:, we produce False or True depending on whether the constructor of the value provided is located on the left or on the right:

instance (Encode' f, Encode' g) => Encode' (f :+: g) where
  encode' (L1 x) = False : encode' x
  encode' (R1 x) = True  : encode' x

(Note that this encoding strategy may not be reliable across different versions of GHC. Recall that the compiler is free to choose any nesting of :+: it chooses, so if GHC chooses (a :+: b) :+: c, then the encoding for a would be [False, False], b would be [False, True], and c would be [True]. However, if GHC chooses a :+: (b :+: c), then the encoding for a would be [False], b would be [True, False], and c would be [True, True].)

In the case for :*:, we append the encodings of the two subcomponents:

instance (Encode' f, Encode' g) => Encode' (f :*: g) where
  encode' (x :*: y) = encode' x ++ encode' y

The case for K1 is rather interesting. Here, we call the final function encode that we yet have to define, recursively. We will use another type class Encode for that function:

instance (Encode c) => Encode' (K1 i c) where
  encode' (K1 x) = encode x

Note how we can define a uniform instance for M1, because we completely disregard all meta-information:

instance (Encode' f) => Encode' (M1 i t f) where
  encode' (M1 x) = encode' x

Unlike in K1, the instance for M1 refers to encode', not encode.

We now define class Encode for the actual encode function:

class Encode a where
  encode :: a -> [Bool]
  default encode :: (Generic a, Encode' (Rep a)) => a -> [Bool]
  encode x = encode' (from x)

The incoming x is converted using from, then we dispatch to the generic instances using encode'. We use this as a default definition for encode. We need the default encode signature because ordinary Haskell default methods must not introduce additional class constraints, but our generic default does.

Defining a particular instance is now as simple as saying

instance (Encode a) => Encode (Tree a)

The generic default is being used. In the future, it will hopefully be possible to use deriving Encode as well, but GHC does not yet support that syntax for this situation.

Having Encode as a class has the advantage that we can define non-generic special cases, which is particularly useful for abstract datatypes that have no structural representation. For example, given a suitable integer encoding function encodeInt, we can define

instance Encode Int where
  encode = encodeInt

It is not always required to provide instances for all the generic representation types, but omitting instances restricts the set of datatypes the functions will work for:

• If no :+: instance is given, the function may still work for empty datatypes or datatypes that have a single constructor, but will fail on datatypes with more than one constructor.

• If no :*: instance is given, the function may still work for datatypes where each constructor has just zero or one field, in particular for enumeration types.

• If no K1 instance is given, the function may still work for enumeration types, where no constructor has any fields.

• If no V1 instance is given, the function may still work for any datatype that is not empty.

• If no U1 instance is given, the function may still work for any datatype where each constructor has at least one field.

An M1 instance is always required (but it can just ignore the meta-information, as is the case for encode above).

Datatype-generic functions as defined above work for a large class of datatypes, including parameterized datatypes. (We have used Tree as our example above, which is of kind * -> *.) However, the Generic class ranges over types of kind *, and therefore, the resulting generic functions (such as encode) must be parameterized by a generic type argument of kind *.

What if we want to define generic classes that range over type constructors (such as Data.Functor.Functor, Data.Traversable.Traversable, or Data.Foldable.Foldable)?

Like Generic, there is a class Generic1 that defines a representation Rep1 and conversion functions from1 and to1, only that Generic1 ranges over types of kind * -> *. (More generally, it can range over types of kind k -> *, for any kind k, if the PolyKinds extension is enabled. More on this later.) The Generic1 class is also derivable.

The representation Rep1 is ever so slightly different from Rep. Let us look at Tree as an example again:

data Tree a = Leaf a | Node (Tree a) (Tree a)
  deriving Generic1

The above declaration causes the following representation to be generated:

instance Generic1 Tree where
  type Rep1 Tree =
    D1 ('MetaData "Tree" "Main" "package-name" 'False)
      (C1 ('MetaCons "Leaf" 'PrefixI 'False)
         (S1 ('MetaSel 'Nothing
                         'NoSourceUnpackedness
                         'NoSourceStrictness
                         'DecidedLazy)
               Par1)
       :+:
       C1 ('MetaCons "Node" 'PrefixI 'False)
         (S1 ('MetaSel 'Nothing
                         'NoSourceUnpackedness
                         'NoSourceStrictness
                         'DecidedLazy)
               (Rec1 Tree)
          :*:
          S1 ('MetaSel 'Nothing
                         'NoSourceUnpackedness
                         'NoSourceStrictness
                         'DecidedLazy)
               (Rec1 Tree)))
  ...

The representation reuses D1, C1, S1 (and thereby M1) as well as :+: and :*: from Rep. (This reusability is the reason that we carry around the dummy type argument for kind-*-types, but there are already enough different names involved without duplicating each of these.)

What's different is that we now use Par1 to refer to the parameter (and that parameter, which used to be a), is not mentioned explicitly by name anywhere; and we use Rec1 to refer to a recursive use of Tree a.

Unlike Rec0, the Par1 and Rec1 type constructors do not map to K1. They are defined directly, as follows:

newtype Par1   p = Par1 { unPar1 ::   p } -- gives access to parameter p
newtype Rec1 f p = Rec1 { unRec1 :: f p } -- a wrapper

In Par1, the parameter p is used for the first time, whereas Rec1 simply wraps an application of f to p.

Note that K1 (in the guise of Rec0) can still occur in a Rep1 representation, namely when the datatype has a field that does not mention the parameter.

The declaration

data WithInt a = WithInt Int a
  deriving Generic1

yields

instance Generic1 WithInt where
  type Rep1 WithInt =
    D1 ('MetaData "WithInt" "Main" "package-name" 'False)
      (C1 ('MetaCons "WithInt" 'PrefixI 'False)
        (S1 ('MetaSel 'Nothing
                        'NoSourceUnpackedness
                        'NoSourceStrictness
                        'DecidedLazy)
              (Rec0 Int)
         :*:
         S1 ('MetaSel 'Nothing
                         'NoSourceUnpackedness
                         'NoSourceStrictness
                         'DecidedLazy)
              Par1))

If the parameter a appears underneath a composition of other type constructors, then the representation involves composition, too:

data Rose a = Fork a [Rose a]

yields

instance Generic1 Rose where
  type Rep1 Rose =
    D1 ('MetaData "Rose" "Main" "package-name" 'False)
      (C1 ('MetaCons "Fork" 'PrefixI 'False)
        (S1 ('MetaSel 'Nothing
                        'NoSourceUnpackedness
                        'NoSourceStrictness
                        'DecidedLazy)
              Par1
         :*:
         S1 ('MetaSel 'Nothing
                         'NoSourceUnpackedness
                         'NoSourceStrictness
                         'DecidedLazy)
              ([] :.: Rec1 Rose)))

where

newtype (:.:) f g p = Comp1 { unComp1 :: f (g p) }

The Generic1 class can be generalized to range over types of kind k -> *, for any kind k. To do so, derive a Generic1 instance with the PolyKinds extension enabled. For example, the declaration

data Proxy (a :: k) = Proxy deriving Generic1

yields a slightly different instance depending on whether PolyKinds is enabled. If compiled without PolyKinds, then Rep1 Proxy :: * -> *, but if compiled with PolyKinds, then Rep1 Proxy :: k -> *.

If one were to attempt to derive a Generic instance for a datatype with an unlifted argument (for example, Int#), one might expect the occurrence of the Int# argument to be marked with Rec0 Int#. This won't work, though, since Int# is of an unlifted kind, and Rec0 expects a type of kind *.

One solution would be to represent an occurrence of Int# with 'Rec0 Int' instead. With this approach, however, the programmer has no way of knowing whether the Int is actually an Int# in disguise.

Instead of reusing Rec0, a separate data family URec is used to mark occurrences of 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 = UFloat  { uFloat#  :: Float#  }
data instance URec Float    p = UInt    { uInt#    :: Int#    }
data instance URec Word     p = UWord   { uWord#   :: Word#   }

Several 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

The declaration

data IntHash = IntHash Int#
  deriving Generic

yields

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))

Currently, only the six unlifted types listed above are generated, but this may be extended to encompass more unlifted types in the future.