If you're usingGHC.Generics, you should consider using thehttp://hackage.haskell.org/package/generic-deriving package, which contains many useful generic functions.

Since: 4.6.0.0

Datatype-generic functions are based on the idea of converting values of a datatypeT into corresponding values of a (nearly) isomorphic typeRep T. The typeRep T is built from a limited set of type constructors, all provided by this module. A datatype-generic function is then an overloaded function with instances for most of these type constructors, together with a wrapper that performs the mapping betweenT andRep T. By using this technique, we merely need a few generic instances in order to implement functionality that works for any representable type.

Representable types are collected in theGeneric class, which defines the associated typeRep as well as conversion functionsfrom andto. Typically, you will not defineGeneric instances by hand, but have the compiler derive them for you.

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

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

instanceGeneric (Tree a) where  typeRep (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 asRep 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 forTree with nearly all meta-information removed, for now keeping only the most essential aspects:

instanceGeneric (Tree a) where  typeRep (Tree a) =Rec0 a:+:    (Rec0 (Tree a):*:Rec0 (Tree a))

TheTree 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 parametera. This is represented asRec0 a.

The second constructor consists of two fields. Each is a recursive field of typeTree a, represented asRec0 (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:

• TheS1 ('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. SeeDecidedStrictness for a more detailed explanation.

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

• TheC1 ('MetaCons "Leaf" 'PrefixI 'False) andC1 ('MetaCons "Node" 'PrefixI 'False) invocations indicate that the enclosed part is the representation of the first and second constructor of datatypeTree, 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 classConstructor. This type class can be used to obtain information about the constructor at the value level.
• TheD1 ('MetaData "Tree" "Main" "package-name" 'False) tag indicates that the enclosed part is the representation of the datatypeTree. Again, the meta-information is encoded at the type level. The'MetaData type is an instance of classDatatype, 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 usingdata ornewtype 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 constructorRec0 is a variant ofK1:

typeRec0 =K1R

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

There used to be another variant ofK1 (namelyPar0), but it has since been deprecated.

The type constructorsS1,C1 andD1 are all variants ofM1:

typeS1 =M1StypeC1 =M1CtypeD1 =M1D

The typesS,C andD are once again type-level proxies, just used to create several variants ofM1.

Next toK1,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 derivingGeneric

yields

instanceGeneric Empty where  typeRep Empty =D1 ('MetaData "Empty" "Main" "package-name" 'False)V1

If a constructor has no arguments, thenU1 is used as its representation. For example the representation ofBool is

instanceGeneric Bool where  typeRep 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. Awrapper that for any datatype that is inGeneric, performs the conversion between the original value and itsRep-based representation and then invokes the generic instances.

As an example, let us look at a functionencode 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 useBool as our datatype for bits.

For part 1, we define a classEncode'. Perhaps surprisingly, this class is parameterized over a type constructorf 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 argumenta withf p (where thep is any argument; it will not be used).

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

With the goal in mind to makeencode work onTree and other datatypes, we now define instances for the representation type constructorsV1,U1,:+:,:*:,K1, andM1.

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

dataV1        p                       -- lifted version of EmptydataU1        p =U1                  -- lifted version of ()data    (:+:) f g p =L1 (f p) |R1 (g p) -- lifted version ofEitherdata    (:*:) f g p = (f p):*: (g p)     -- lifted version of (,)newtypeK1    i c p =K1 {unK1 :: c }    -- a container for a cnewtypeM1  i t f p =M1 {unM1 :: f p }  -- a wrapper

So,U1 is just the unit type,:+: is just a binary choice likeEither,:*: is a binary pair like the pair constructor(,), andK1 is a value of a specific typec, andM1 wraps a value of the generic type argument, which in the lifted world is anf p (where we do not care aboutp).

The instance forV1 is slightly awkward (but also rarely used):

instance Encode'V1 where  encode' x = undefined

There are no values of typeV1 p to pass (except undefined), so this is actually impossible. One can ask why it is useful to define an instance forV1 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. TheV1 instance ensures that we can call the generic function on such types.

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

instance Encode'U1 where  encode'U1 = []

In the case for:+:, we produceFalse orTrue 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 fora would be[False, False],b would be[False, True], andc would be[True]. However, if GHC choosesa:+: (b:+: c), then the encoding fora would be[False],b would be[True, False], andc 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 forK1 is rather interesting. Here, we call the final functionencode that we yet have to define, recursively. We will use another type classEncode for that function:

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

Note howPar0 andRec0 both being mapped toK1 allows us to define a uniform instance here.

Similarly, we can define a uniform instance forM1, because we completely disregard all meta-information:

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

Unlike inK1, the instance forM1 refers toencode', notencode.

We now define classEncode for the actualencode function:

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

The incomingx is converted usingfrom, then we dispatch to the generic instances usingencode'. We use this as a default definition forencode. 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)

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 noK1 instance is given, the function may still work for enumeration types, where no constructor has any fields.
• If noV1 instance is given, the function may still work for any datatype that is not empty.
• If noU1 instance is given, the function may still work for any datatype where each constructor has at least one field.

AnM1 instance is always required (but it can just ignore the meta-information, as is the case forencode above).

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

What if we want to define generic classes that range over type constructors (such asFunctor,Traversable, orFoldable)?

LikeGeneric, there is a classGeneric1 that defines a representationRep1 and conversion functionsfrom1 andto1, only thatGeneric1 ranges over types of kind* -> *. (More generally, it can range over types of kindk -> *, for any kindk, if thePolyKinds extension is enabled. More on this later.) TheGeneric1 class is also derivable.

The representationRep1 is ever so slightly different fromRep. Let us look atTree as an example again:

data Tree a = Leaf a | Node (Tree a) (Tree a)  derivingGeneric1

The above declaration causes the following representation to be generated:

instanceGeneric1 Tree where  typeRep1 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 reusesD1,C1,S1 (and therebyM1) as well as:+: and:*: fromRep. (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 usePar1 to refer to the parameter (and that parameter, which used to bea), is not mentioned explicitly by name anywhere; and we useRec1 to refer to a recursive use ofTree a.

UnlikeRec0, thePar1 andRec1 type constructors do not map toK1. They are defined directly, as follows:

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

InPar1, the parameterp is used for the first time, whereasRec1 simply wraps an application off top.

Note thatK1 (in the guise ofRec0) can still occur in aRep1 representation, namely when the datatype has a field that does not mention the parameter.

The declaration

data WithInt a = WithInt Int a  derivingGeneric1

yields

instanceGeneric1 WithInt where  typeRep1 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 parametera appears underneath a composition of other type constructors, then the representation involves composition, too:

data Rose a = Fork a [Rose a]

yields

instanceGeneric1 Rose where  typeRep1 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) }

TheGeneric1 class can be generalized to range over types of kindk -> *, for any kindk. To do so, derive aGeneric1 instance with thePolyKinds extension enabled. For example, the declaration

data Proxy (a :: k) = Proxy derivingGeneric1

yields a slightly different instance depending on whetherPolyKinds is enabled. If compiled withoutPolyKinds, thenRep1 Proxy :: * -> *, but if compiled withPolyKinds, thenRep1 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 theInt# argument to be marked withRec0Int#. This won't work, though, sinceInt# is of an unlifted kind, andRec0 expects a type of kind*.

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

Instead of reusingRec0, a separate data familyURec is used to mark occurrences of common unlifted types:

data family URec a pdata instanceURec (Ptr ()) p =UAddr   {uAddr#   ::Addr#   }data instanceURecChar     p =UChar   {uChar#   ::Char#   }data instanceURecDouble   p =UDouble {uDouble# ::Double# }data instanceURecInt      p =UFloat  {uFloat#  ::Float#  }data instanceURecFloat    p =UInt    {uInt#    ::Int#    }data instanceURecWord     p =UWord   {uWord#   ::Word#   }

Several type synonyms are provided for convenience:

typeUAddr   =URec (Ptr ())typeUChar   =URecChartypeUDouble =URecDoubletypeUFloat  =URecFloattypeUInt    =URecInttypeUWord   =URecWord

The declaration

data IntHash = IntHash Int#  derivingGeneric

yields

instanceGeneric IntHash where  typeRep 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.

dataV1 (p :: k)Source#

dataU1 (p :: k)Source#

newtypePar1 pSource#

newtypeRec1 (f :: k ->Type) (p :: k)Source#

newtypeK1 (i ::Type) c (p :: k)Source#

newtypeM1 (i ::Type) (c ::Meta) (f :: k ->Type) (p :: k)Source#

data ((f :: k ->Type):+: (g :: k ->Type)) (p :: k)infixr 5Source#

data ((f :: k ->Type):*: (g :: k ->Type)) (p :: k)infixr 6Source#