A Generic Deriving Mechanism for Haskell
José Pedro Magalhães1

Atze Dijkstra1

Johan Jeuring1,2

Andres Löh1

1 Department of Information and Computing Sciences, Utrecht University, P.O. Box 80.089, 3508 TB Utrecht, The Netherlands
2 School of Computer Science, Open University of the Netherlands, P.O. Box 2960, 6401 DL Heerlen, The Netherlands{jpm,atze,johanj,andres}@cs.uu.nl

Abstract
Haskell’s deriving mechanism supports the automatic generationof instances for a number of functions. The Haskell 98 Report
only specifies how to generate instances for the Eq, Ord, Enum,
Bounded, Show, and Read classes. The description of how to generate instances is largely informal. The generation of instances
imposes restrictions on the shape of datatypes, depending on theparticular class to derive. As a consequence, the portability of instances across different compilers is not guaranteed.
We propose a new approach to Haskell’s deriving mechanism,
which allows users to specify how to derive arbitrary class instances using standard datatype-generic programming techniques.
Generic functions, including the methods from six standard Haskell
98 derivable classes, can be specified entirely within Haskell 98
plus multi-parameter type classes, making them lightweight andportable. We can also express Functor, Typeable, and many otherderivable classes with our technique. We implemented our deriving
mechanism together with many new derivable classes in the Utrecht
Haskell Compiler.
Categories and Subject Descriptors D.1.1 [Programming Techniques]: Functional Programming
General Terms Languages

approach (SYB, Lämmel and Peyton Jones 2003, 2004) is due to its
availability: it comes with the Glasgow Haskell Compiler (GHC),
the main Haskell compiler, which can even derive the necessary
type class instances to make everything work without clutter.
To improve the usability of generics in Haskell, we believea tighter integration with the compiler is necessary. In fact, theHaskell 98 standard already contains some generic programming,in the form of derived instances (Peyton Jones et al. 2003, Chapter
10). Unfortunately, the report does not formally specify how toderive instances, and it restricts the classes that can be derived to
six only (Eq, Ord, Enum, Bounded, Show, and Read). GHC has
since long extended these with Data and Typeable (the basis of
SYB), and more recently with Functor, Foldable and Traversable.
Due to the lack of a unifying formalism, these extensions are noteasily mimicked in other compilers, which need to reimplement the
instance code generation mechanism.
To address these issues, we propose an approach to specifying
how to derive an instance of a class, together with new behavior forthe deriving mechanism in Haskell to automatically derive sucha class. To allow for portability across compilers, our approachrequires only Haskell 98 with multi-parameter type classes andsupport for a new compiler pragma. Specifically, our contributionsare:• We describe a new datatype-generic programming library for

1.

Introduction

Generic programming has come a long way: from its roots in
category theory (Backhouse et al. 1999), passing through dedicated languages (Jansson and Jeuring 1997), language extensions
and pre-processors (Hinze et al. 2007; Löh 2004) until the flurryof library-based approaches of today (Rodriguez Yakushev et al.
2008). In this evolution, expressivity has not always increased:
many generic programming libraries of today still cannot competewith the Generic Haskell pre-processor, for instance. The same applies to performance, as libraries tend to do little regarding code
optimization, whereas meta-programming techniques such as Template Haskell (Sheard and Peyton Jones 2002) can generate nearoptimal code. Instead, generic programming techniques seem to
evolve in the direction of better availability and usability: it shouldbe easy to define generic functions and it should be trivial to use
them. Certainly some of the success of the Scrap Your Boilerplate

Permission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citationon the first page. To copy otherwise, to republish, to post on servers or to redistributeto lists, requires prior specific permission and/or a fee.
Haskell’10, September 30, 2010, Baltimore, Maryland, USA.
Copyright c 2010 ACM 978-1-4503-0252-4/10/09. . . $10.00

Haskell. Although similar in many aspects to other approaches,
our library requires almost no extensions to Haskell 98; themost significant requirement is support for multi-parameter
type classes.
• We show how this library can be used to extend the deriving

mechanism in Haskell, and provide sample derivings, notably
for the Functor class.
• We provide a detailed description of how the representation fora datatype is generated. In particular, we can represent almost
all Haskell 98 datatypes.
• We provide a fully functional implementation of our libraryin the Utrecht Haskell Compiler (UHC, Dijkstra et al. 2009).
Many useful generic functions are defined using generic deriving in the compiler.
We also provide a package which compiles both in UHC and GHC,
showing in detail the code that needs to added to the compiler, thecode that should be generated by the compiler, and the code that is
portable between compilers.1
The remainder of this paper is structured as follows: first we
give a brief introduction to generic programming in Haskell (Section 2), which also introduces the particular library we use. We proceed to show how to define generic functions (Section 3), and then
1 http://dreixel.net/research/code/gdmh.tar.gz

data U1
ρ = U1
data (+) φ ψ ρ = L1 {unL1 :: φ ρ } | R1 {unR1 :: ψ ρ }data (×) φ ψ ρ = φ ρ × ψ ρ

describe the necessary modifications to the compiler for supporting
our approach (Section 4). Finally, we discuss alternative designs(Section 5), review related work (Section 6), propose future work
(Section 7) and conclude in Section 8.

2.

Generic programming

We use the generic function encode as a running example throughout this paper. This function transforms a value into a sequence ofbits:
data Bit = 0 | 1
class Encode α where
encode :: α → [Bit ]We want the user to be able to write
data Exp = Const Int | Plus Exp Exp
deriving (Show, Encode)

We encode lifted sums with (+) and lifted products with (×).
Nullary products are encoded with lifted unit (U1 ).2
The type variable ρ is present in all representation types: it
represents the parameter over which we abstract. We use an explicit
combinator to mark the occurrence of this parameter:
newtype Par1 ρ = Par1 {unPar1 :: ρ }As our representation is functorial, we can encode composition.
Although we cannot express this in the kind system, we require thefirst argument of composition to be a representable type constructor. The second argument can only be the parameter, a recursive
occurrence of a functorial datatype, or again a composition. We use
Rec1 to represent recursion, and (◦) for composition:
newtype Rec1 φ ρ = Rec1 {unRec1 :: φ ρ }newtype (◦) φ ψ ρ = Comp1 (φ (ψ ρ))and to use encode like
test :: [Bit ]test = encode (Plus (Const 1) (Const 2))
This should be all that is necessary to use encode. The user shouldneed no further knowledge of generics, and encode can be used in
the same way as show, for instance.
Behind the scenes, the compiler generates an instance for
Encode Exp based on a generic specification of instances of class
Encode. There are several ways to specify such an instance,
both using code generation and datatype-generic approaches. We
choose a datatype-generic approach because it is type-safe and elegant (Hinze et al. 2007). We will discuss alternative designs andmotivate our choice in more detail in Section 5. For now we proceed to describe our new generic programming library. The threebasic ingredients for generic programming, as described by Hinze
and Löh (2009), are:

PolyP (Jansson and Jeuring 1997) treats composition in a similarway.
Finally, we have two types for representing meta-informationand tagging:newtype K1 ι γ ρ = K1 {unK1 :: γ }newtype M1 ι γ φ ρ = M1 {unM1 :: φ ρ }We use K1 for tagging and M1 for storing meta-information. The
role of the ι parameter in these types is made explicit by thefollowing type synonyms:
data Ddata C
data S
data Rdata P

1. Support for overloaded functions
2. A run-time type representation
3. A generic view on data
Since we use Haskell, (1) is easy: an overloaded (ad-hoc polymorphic) function is a method of a type class. For (2), we introduce atype representation similar to the one used in the regular (Van
Noort et al. 2008) and instant-generics (Chakravarty et al.
2009) libraries, in Section 2.1. For (3), we again use type classes
to encode embedding-projection pairs for user-defined datatypes in
Section 2.3.
2.1

We use Rec0 to tag occurrences of (possibly recursive) types ofkind ? and Par0 to mark additional parameters of kind ? (other than
ρ). For meta-information, we use D1 for datatype information, C1
for constructor information and S1 for record selector information.
We group five combinators into two because in many generic functions the behavior is independent of the meta-information or tags.
In this way, fewer trivial cases have to be given. We present themeta-information associated with M1 in detail in the next section.
Note that we abstract over a single parameter ρ of kind ?. Thismeans we will be able to express generic functions such as

A run-time type representation

The choice of a run-time type representation affects not only thecompiler writer but also the expressiveness of the whole approach.
A simple representation is easier to derive, but might not allow
the definition of some generic functions. More complex representations are more expressive, but require more work for the automatic
derivation of instances.
We present a set of representation types that tries to balancethese factors. We use the common sum-of-products representation
without explicit fixpoints but with explicit abstraction over a single parameter. Therefore, representable types are functors, and we
can compose types. Additionally, we provide useful types for encoding meta-information (such as constructor names) and tagging
arguments to constructors. We show examples of how these representation types are used in Section 2.4.
The basic ingredients of the sum-of-products representation
types are:type D1 = M1 D
type C1 = M1 C
type S1 = M1 S
type Rec0 = K1 R
type Par0 = K1 P

fmap :: (α → β ) → φ α → φ β
but not
bimap :: (α → γ) → (β → δ ) → φ α β → φ γ δFor bimap we need another type representation that can distinguishbetween the parameters. All representation types need to carry one
additional type argument. However, we think that, in practice, few
generic functions require abstraction over more than a single typeparameter.
2.2

Meta-information

For some generic functions we need information about datatypes,
constructors, and records. This information is stored in the type
representation:
2 We also have lifted void (V ) to represent nullary sums, but for simplicity
1

we omit it from this discussion and from the generic functions in Section 3.

class Datatype γ where
datatypeName :: γ → String
moduleName :: γ → Stringclass Selector γ where
selName :: γ → String
selName = const ""class Constructor γ where
conName :: γ → String
conFixity :: γ → Fixity
conFixity = const Prefix
conIsRecord :: γ → BoolconIsRecord = const False
Names are unqualified. We provide the datatype name together withthe module name. This is the only meta-information we store for adatatype, although it could be easily extended to add the kind, forexample. We only store the name of a selector. For a constructor, we
also store its fixity and mark if it has fields. This last information is
not strictly necessary, as it can be inferred by looking for non-empty
selNames, but it simplifies some generic function definitions. The
datatypes Fixity and Associativity are unsurprising:data Fixity = Prefix | Infix Associativity Int
data Associativity = LeftAssociative | RightAssociative| NotAssociative
We provide default definitions for conFixity and conIsRecord tosimplify instantiation for prefix constructors that do not use record
notation.3
Finally, we tie the meta-information to the representation:
instance (Datatype γ) ⇒ Datatype (M1 D γ φ ρ) where
datatypeName = datatypeName ◦ unMeta
moduleName = moduleName ◦ unMeta
instance (Constructor γ) ⇒ Constructor (M1 C γ φ ρ) where
conName = conName ◦ unMeta
instance (Selector γ) ⇒ Selector (M1 S γ φ ρ) where
selName = selName ◦ unMeta
unMeta :: M1 ι γ φ ρ → γ
unMeta = ⊥Function unMeta operates at the type-level only, so it does not need
an implementation. We provide more details in Section 4.5, and theexamples later in Section 2.4 and Section 3.6 also clarify how we
use these classes.
Note that we could encode the meta information as an extra
argument to M1 :data M1 ι γ φ ρ = M1 Meta (φ ρ)data Meta = Meta String Fixity . . .
However, with this encoding we have trouble writing generic producers, since when we are producing an M1 we have to produce
a Meta for which we have no information. With the above representation we avoid this problem by using type-classes to fill in theright information for us. See Section 3.5 for an example of how thisworks.
3 We also provide an empty default selName because all constructor argu-

ments will be wrapped in an S1 , independently of using record notation ornot. We omit this in the example representations of this section for spacereasons, but it becomes clear in Section 4.

2.3

A generic view on data

We obtain a generic view on data by defining an embeddingprojection pair between a datatype and its type representation. We
use the following classes for this purpose:
class Representable0 α τ where
from0 :: α → τ χ
to0 :: τ χ → αclass Representable1 φ τ wherefrom1 :: φ ρ → τ ρ
to1 :: τ ρ → φ ρ
We use τ to encode the representation of a standard type. Since τ isbuilt from representation types, it is functorial. In Representable1 ,we encode types of kind ? → ?, so we have the parameter ρ. In
Representable0 there is no parameter, so we invent a variable χwhich is never used.
All types need to have an instance of Representable0 . Types ofkind ? → ? also need an instance of Representable1 . This separation is necessary because some generic functions (like fmap ortraverse) require explicit abstraction from a single type parameter, whereas others (like show or enum) do not. Given the different
kinds involved, it is unavoidable to have two type classes for thisrepresentation. Note, however, that we have a single set of representation types (apart from the duplication for tagging recursion
and parameters).
Avoiding extensions Since we want to avoid using advanced
Haskell extensions such as type families (Schrijvers et al. 2008)
or functional dependencies (Jones 2000), we use a simple multiparameter type class for embedding-projection pairs. In fact, τ isuniquely determined by α (and φ ). We could encode the representation type more naturally with a type family:class Representable0 α wheretype Rep0 α :: ? → ?
from0 :: α → Rep0 α χ
to0 :: Rep0 α χ → α
Since type families and functional dependencies are not yet partof any Haskell standard, we do not use them. Instead, we use
multi-parameter type classes, and solve the ambiguities that arise
by coercing with asTypeOf .
2.4

Example representations

We now show how to represent some standard datatypes. Notethat all the code in this section is automatically generated by thecompiler, as described in Section 4.
Representing Exp. The meta-information for datatype Exp looks
as follows:data $Exp
data $ConstExp
data $PlusExp
instance Datatype $Exp wheremoduleName= "ModuleName"
datatypeName = "Exp"instance Constructor $ConstExp where conName
instance Constructor $PlusExp where conName= "Const"= "Plus"

In moduleName, "ModuleName" is the name of the module where
Exp lives. The particular datatypes we use for representing themeta-information at the type-level are not needed for defining
generic functions, so they are not visible to the user. In this paper, we prefix them with a $.
The type representation ties the meta-information to the sumof-products representation of Exp:

Exp

type Rep0 =D1 $Exp ( C1 $ConstExp (Rec0 Int)+ C1 $PlusExp (Rec0 Exp × Rec0 Exp))
Note that the representation is shallow: at the recursive occurrencesExp
we use Exp, and not Rep0 .
The embedding-projection pair implements the isomorphismExp
between Exp and Rep0 :Exp

instance Representable0 Exp Rep0 where
from0 (Const n) = M1 (L1 (M1 (K1 n)))from0 (Plus e e0 ) = M1 (R1 (M1 (K1 e × K1 e0 )))to0 (M1 (L1 (M1 (K1 n))))= Const n
to0 (M1 (R1 (M1 (K1 e × K1 e0 )))) = Plus e e0
Here it is clear that from0 and to0 are inverses: the pattern of from0is the same as the expression in to0 , and vice-versa.
Representing lists. The representation for a type of kind ? → ?
requires an instance for both Representable1 and Representable0 .
For lists
data List ρ = Nil | Cons ρ (List ρ) deriving (Show, Encode)
we generate the following code:
type RepList
0 ρ=
D1 $List ( C1 $NilList U1+ C1 $ConsList (Par0 ρ × Rec0 (List ρ)))instance Representable0 (List ρ) (RepList
0 ρ) where
from0 Nil
= M1 (L1 (M1 U1 ))from0 (Cons h t) = M1 (R1 (M1 (K1 h × K1 t)))to0 (M1 (L1 (M1 U1 )))= Nil
to0 (M1 (R1 (M1 (K1 h × K1 t)))) = Cons h t
We omit the definitions for the meta-information, which are similar
to the previous example. We use Par0 to tag the parameter ρ, as weview lists as a kind ? datatype for Representable0 . This is different
in the Representable1 instance:
type RepList
1 = D1 $List ( C1 $NilList U1+ C1 $ConsList (Par1 × Rec1 List))
instance Representable1 List RepList
1 wherefrom1 Nil
= M1 (L1 (M1 U1 ))from1 (Cons h t) = M1 (R1 (M1 (Par1 h × Rec1 t)))to1 (M1 (L1 (M1 U1 )))= Nil
to1 (M1 (R1 (M1 (Par1 h × Rec1 t)))) = Cons h t
List
We treat parameters and recursion differently in RepList
0 and Rep1 .
List
List
In Rep0 we use Par0 and Rec0 for mere tagging; in Rep1 we use
Par1 and Rec1 instead, which store the parameter and the recursive
occurrence of a type constructor, respectively. We will see later
when defining generic functions (Section 3) how these are used.

Representing type composition. We now present a larger example, involving more complex datatypes, to show the expressivenessof our approach. Datatype Expr represents abstract syntax trees ofa small language:
infixr 6 ∗data Expr ρ = Const Int| Expr ρ ∗ Expr ρ| VarExpr {unVar :: Var ρ }| Let [Decl ρ ] (Expr ρ)
data Decl ρ = Decl (Var ρ) (Expr ρ)

data Var ρ = Var ρ | VarL (Var [ρ ])Note that Expr makes use of an infix constructor (∗), has a selector(unVar), and uses lists in Let. Datatype Var is nested, since in the
VarL constructor Var is called with [ρ ]. These oddities are present
only for illustrating how our approach represents them. We show
only the essentials of the encoding of this set of mutually recursive
datatypes, starting with the meta-information:
data $TimesExpr
data $VarExpr Exprdata $UnVar
instance Constructor $TimesExpr where
conName= "*"= Infix RightAssociative 6
conFixity
instance Constructor $VarExpr Expr where
conName= "Var_Expr"conIsRecord = True
instance Selector $UnVar where selName = "unVar"
We have to store the fixity of the ∗ constructor, and also the fact that
VarExpr has a record. We store its name in the instance for Selector,
and tie the meta-information to the representation:
Expr

type Rep1 = D1 $Expr( ( C1 $ConstExpr (Rec0 Int)+ C1 $TimesExpr (Rec1 Expr × Rec1 Expr))+ ( C1 $VarExpr Expr (S1 $UnVar (Rec1 Var))+ C1 $LetExpr(([ ] ◦ Rec1 Decl) × Rec1 Expr)))Expr

In Rep1
we see the use of S1 . Also interesting is the representation of the Let constructor: the list datatype is applied not to theparameter ρ but to Decl ρ, so we use composition to denote this.
Note also that we are using a balanced encoding for the sums (andalso for the products). This improves the performance of the typechecker, and makes generic encoding more space-efficient, for instance.
We omit the representation for Decl. For Var we use composition again:
type RepVar
1 = D1 $Var(
C1 $VarVar Par1
+ C1 $VarLVar (Var ◦ Rec1 [ ]))In the VarL constructor, Var is applied to [ρ ]. We represent this asa composition with Rec1 [ ].
When we use composition, the embedding-projection pairs become slightly more complicated:Expr

instance Representable1 Expr Rep1 wherefrom1 (Const i) = M1 (L1 (L1 (M1 (K1 i))))from1 (e1 ∗ e2 ) = M1 (L1 (R1 (M1 (Rec1 e1 × Rec1 e2 ))))
from1 (VarExpr v) = M1 (R1 (L1 (M1 (M1 (Rec1 v)))))
from1 (Let d e) =M1 (R1 (R1 (M1 (Comp1 (fmap Rec1 d) × Rec1 e))))to1 (M1 (L1 (L1 (M1 (K1 i)))))= Const i
to1 (M1 (L1 (R1 (M1 (Rec1 e1 × Rec1 e2 ))))) = e1 ∗ e2
to1 (M1 (R1 (L1 (M1 (M1 (Rec1 v))))))= VarExpr v
to1 (M1 (R1 (R1 (M1 (Comp1 d × Rec1 e))))) =Let (fmap unRec1 d) e
We need to use fmap to apply the Rec1 constructor inside the lists.
In this case we could use map instead, but in general we require thefirst argument to ◦ to have a Functor instance so we can use fmap.
In to1 we need to convert back, this time mapping unRec1 .

For Var, the embedding-projection pair is similar:
instance Representable1 Var RepVar
1 wherefrom1 (Var x) = M1 (L1 (M1 (Par1 x)))from1 (VarL xs) = M1 (R1 (M1 (Comp1 (fmap Rec1 xs))))to1 (M1 (L1 (M1 (Par1 x))))= Var xto1 (M1 (R1 (M1 (Comp1 xs)))) = VarL (fmap unRec1 xs)
Note that composition is used both in the representation for the
first argument of constructor Let (of type [Decl ρ ]) and in the nested
recursion of VarL (of type Var [ρ ]). In both cases, we have a recursive occurrence of a parametrized datatype where the parameter is
not just the variable ρ. Recall our definition of composition:

because we need a two-level approach to deal with recursion: for
the K1 instance, we recursively call encode instead of encode1 . Recall our representation for Exp (simplified and with type synonyms
expanded):Exp

type Rep0= K1 R Int + K1 R Exp × K1 R Exp

Since Int and Exp appear as arguments to K1 , and our instanceof Encode1 for K1 ι φ requires an instance of Encode φ , we needinstances of Encode for Int and for Exp. We deal with Int in the next
section, and Exp in Section 3.3. Finally, note that we do not need
Encode1 instances for Rec1 , Par1 or (◦). These are only requiredfor generic functions which make use of the Representable1 class.
We will see an example in Section 3.4.

data (◦) φ ψ ρ = Comp1 (φ (ψ ρ))
The type φ is applied not to ρ, but to the result of applying ψ to ρ.
This is why we use ◦ when the recursive argument to a datatype isnot ρ, like in [Decl ρ ] and Var [ρ ]. When it is ρ, we can simply
use Rec1 .
We have seen how to represent many features of Haskell
datatypes in our approach. We give a detailed discussion of the
supported datatypes in Section 7.1.

3.

Generic functions

In this section we show how to define type classes with derivablefunctions.
3.1

Generic function definition

Function encode is a method of a type-class:data Bit = 0 | 1
class Encode α where
encode :: α → [Bit ]We cannot provide instances of Encode for our representation
types, as those have kind ? → ?, and Encode expects a parameter ofkind ?. We therefore define a helper class, this time parametrized
over a variable of kind ? → ?:class Encode1 φ where
encode1 :: φ χ → [Bit ]For constructors without arguments we return the empty list, as
there is nothing to encode. Meta-information is discarded:
instance Encode1 U1 where
encode1 = [ ]instance (Encode1 φ ) ⇒ Encode1 (M1 ι γ φ ) where
encode1 (M1 a) = encode1 a
For a value of a sum type we produce a single bit to record the
choice. For products we concatenate the encoding of each element:
instance (Encode1 φ , Encode1 ψ) ⇒ Encode1 (φ + ψ) where
encode1 (L1 a) = 0 : encode1 a
encode1 (R1 a) = 1 : encode1 a
instance (Encode1 φ , Encode1 ψ) ⇒ Encode1 (φ × ψ) where
encode1 (a × b) = encode1 a ++ encode1 b
It remains to encode constants. Since constant types have kind ?,we resort to Encode:
instance (Encode φ ) ⇒ Encode1 (K1 ι φ ) where
encode1 (K1 a) = encode a
Note that while the instances for the representation types are given
for the Encode1 class, only the Encode class is exported and allowed to be derived. This is because its type is more general, and3.2

Base types

We have to provide the instances of Encode for the base types:
instance Encode Int where encode = . . .
instance Encode Char where encode = . . .
Since Encode is exported, a user can also provide additional basetype instances, or ad-hoc instances (types for which the required
implementation is different from the derived generic behavior).
3.3

Default definition

We miss an instance of Encode for Exp. Instances of generic functions for representable types rely on the embedding-projection
pair to convert from/to the type representation and then apply thegeneric function:
encodeDefault :: (Representable0 α τ, Encode1 τ)⇒ τ χ → α → [Bit ]encodeDefault rep x = encode1 ((from0 x) ‘asTypeOf ‘ rep)
Function encodeDefault tells the compiler what to fill in for the
instance of each of the derived types. Because we do not want
to use functional dependencies for portability reasons, we pass
the representation type explicitly to function encodeDefault . Thisfunction uses the representation type to coerce the result type of
from0 with asTypeOf . This slight complication is a small price to
pay for extended portability.
Now we can show the instance of Encode for Exp and List:instance Encode Exp whereExp
encode = encodeDefault (⊥ :: Rep0 χ)
instance (Encode ρ) ⇒ Encode (List ρ) where
encode = encodeDefault (⊥ :: RepList
0 ρ χ)
Both instances look similar and trivial. However, the instance for
List requires scoped type variables to type-check. We can avoid theneed for scoped type variables if we create an auxiliary local function encodeList with the same type and behavior of encodeDefault :instance (Encode ρ) ⇒ Encode (List ρ) where
encode = encodeList ⊥ where
encodeList :: (Encode ρ) ⇒ RepList
0 ρ χ → List ρ → [Bit ]encodeList = encodeDefault
Here, the local function encodeList encodes in its type the correspondence between the type List ρ and its representation RepList
0 ρ.
Its type signature is required, but can easily be obtained from thetype of encodeDefault by replacing the type variables α and τ withthe concrete types for this instance.
For completeness, we give the instance for Exp in the same
fashion:instance Encode Exp where
encode = encodeExp ⊥ whereExp

instance Functor1 Par1 wherefmap1 f (Par1 a) = Par1 (f a)encodeExp :: Rep0 χ → Exp → [Bit ]encodeExp = encodeDefault
It might seem strange that we choose not to use Haskell’s builtin functionality for default definitions for class methods. Unfortunately we cannot use default methods, for two reasons:

Unit and constant values do not change, as there is nothing we canmap over. We apply fmap1 recursively to meta-information, sums
and products:

1. Since we avoid using type families and functional dependencies, we need to explicitly pass the representation type as anargument to encodeDefault .

instance Functor1 U1 wherefmap1 f U1
= U1
instance Functor1 (K1 ι γ) wherefmap1 f (K1 a) = K1 a
instance (Functor1 φ ) ⇒ Functor1 (M1 ι γ φ ) wherefmap1 f (M1 a) = M1 (fmap1 f a)
instance (Functor1 φ , Functor1 ψ) ⇒ Functor1 (φ + ψ) wherefmap1 f (L1 a) = L1 (fmap1 f a)
fmap1 f (R1 a) = R1 (fmap1 f a)
instance (Functor1 φ , Functor1 ψ) ⇒ Functor1 (φ × ψ) wherefmap1 f (a × b) = fmap1 f a × fmap1 f b

2. A default case would force us to move the Representable0 α τand Encode1 τ class constraints to the Encode class, possibly
preventing ad-hoc instances for non-representable types andexposing Encode1 to the user.
However, if the compiler is to generate instances for Exp andother representable datatypes automatically, how does it know
which function to use as default? The alternative to standard
Haskell default methods is to use a naming convention for thisfunction (like appending Default to the class function name, as in
our example). It is more reliable to use a pragma:

If we find a recursive occurrence of a functorial type, we call fmap
again, to tie the recursive knot:{−# DERIVABLE Encode encode encodeDefault #−}instance (Functor φ ) ⇒ Functor1 (Rec1 φ ) wherefmap1 f (Rec1 a) = Rec1 (fmap f a)

This pragma takes three arguments, which represent (respectively):
1. The class which we are defining as derivable

The remaining case is composition:

2. The method of the class which is generic (and therefore needs
a default definition)

instance (Functor φ , Functor1 ψ) ⇒ Functor1 (φ ◦ ψ) wherefmap1 f (Comp1 x) = Comp1 (fmap (fmap1 f ) x)

3. The name of the function which serves as a default definition

Recall that we require the first argument of (◦) to be a user-defined
datatype, and the second to be a representation type. Therefore, we
use fmap1 for the inner mapping (as it will map over a representation type) but fmap for the outer mapping (as it will require anembedding-projection pair). This is the general structure of the instance of (◦) for a generic function.
Finally, we define the default method:

Such a pragma also has the advantage of indicating derivability
for a particular class. We could use a keyword such as derivable tosignal that a class is allowed to be derived:
derivable class Encode α where . . .
However, by using a pragma instead (as described above) we ensure
more portability, as compilers without support for our derivabletype classes can still compile the code.
Since a class can have multiple generic methods, multiple pragmas can be used for this purpose. Note, however, that a derivableclass can only have non-generic methods if there is a default definition for these, as otherwise we have no means for implementing the non-generic methods. Alternatively, we could treat genericmethods as default methods, filling in the generic definition automatically if the user does not give a definition. This would allow
classes to have normal, generic, and default methods. However, it
would complicate the code generation mechanism.
3.4{−# DERIVABLE Functor fmap fmapDefault #−}fmapDefault :: (Representable1 φ τ, Functor1 τ)⇒ τ ρ → (ρ → α) → φ ρ → φ α
fmapDefault rep f x = to1 (fmap1 f (from1 x ‘asTypeOf ‘ rep))
Now Functor can be derived for user-defined datatypes. The usual
restrictions apply: only types with at least one type parameter andwhose last type argument is of kind ? can derive Functor. The
compiler derives the following instance for List:instance Functor List wherefmap = fmapList (⊥ :: RepList
1 ρ) where
fmapList :: RepList
1 ρ → (ρ → α) → List ρ → List α
fmapList = fmapDefault

Generic map

In this subsection we define the generic map function fmap, which
implements the Prelude’s fmap. Function fmap requires access tothe parameter in the representation type. As before, we export asingle class together with an internal class where we define thegeneric instances:class Functor φ wherefmap :: (ρ → α) → φ ρ → φ αclass Functor1 φ wherefmap1 :: (ρ → α) → φ ρ → φ α
Unlike in Encode, the type arguments to Functor and Functor1
have the same kind, so we do not really need two classes. However, for consistency, we use the same style as for kind ? genericfunctions.
We apply the argument function in the parameter case:

Note that the instance Functor List also guarantees that we can use
List as the first argument to (◦), as the embedding-projection pairs
for such compositions need to use fmap.
The instances derived for Expr, Decl, and Var are similar.
3.5

Generic empty

We can also easily express generic producers: functions which
produce data. We will illustrate this with function empty, which
produces a single value of a given type:class Empty α where empty :: αThis function is perhaps the simplest generic producer, as it consumes no data. It relies only on the structure of the datatype to produce values. Other examples of generic producers are the methods
in Read and the Arbitrary class from QuickCheck, and binary’s
get. As usual, we define an auxiliary type class:class Empty1 φ where
empty0 :: φ χ
Most instances of Empty1 are straightforward:
instance Empty1 U1 where
empty0 = U1
instance (Empty1 φ ) ⇒ Empty1 (M1 ι γ φ ) where
empty0 = M1 empty0
instance (Empty1 φ , Empty1 ψ) ⇒ Empty1 (φ × ψ) where
empty0 = empty0 × empty0
instance (Empty φ ) ⇒ Empty1 (K1 ι φ ) where
empty0 = K1 empty
For units we can only produce U1 . Meta-information is producedwith M1 , and since we encode the meta-information using typeclasses (instead of using extra arguments to M1 ) we do not have touse ⊥ here. An empty product is the product of empty components,and for K1 we recursively call empty. The only interesting choice
is for the sum type:instance (Empty1 φ ) ⇒ Empty1 (φ + ψ) where
empty0 = L1 empty0
In a sum, we always take the leftmost constructor for the empty
value. Since the leftmost constructor might be recursive, function
empty might not terminate. More complex implementations canlook ahead to spot recursion, or choose alternative constructors after recursive calls, for instance. Note also the similarity between our
Empty class and Haskell’s Bounded: if we were defining minBoundand maxBound generically, we could choose L1 for minBound and
R1 for maxBound. This way we would preserve the semantics
for derived Bounded instances, as defined by Peyton Jones et al.
(2003), while at the same time lifting the restrictions on types thatcan derive Bounded. Alternatively, to keep the Haskell 98 behavior,
we could give no instance for ×, as enumeration types will not havea product in their representations.
The default method simply applies to0 to empty0 :{−# DERIVABLE Empty empty emptyDefault #−}emptyDefault :: (Representable0 α τ, Empty1 τ)⇒τ χ →αemptyDefault rep = to0 (empty0 ‘asTypeOf ‘ rep)
Now the compiler can produce instances such as:
instance Empty Exp where
empty = emptyExp ⊥ whereExp
emptyExp :: Rep0 χ → Exp
emptyExp = emptyDefault
instance (Empty ρ) ⇒ Empty (List ρ) where
empty = emptyList ⊥ where
emptyList :: (Empty ρ) ⇒ RepList
0 ρ χ → List ρ
emptyList = emptyDefault
Instances for other types are similar.
3.6

Generic show

To illustrate the use of constructor and selector labels, we define
the shows function generically:class Show α whereshows :: α → ShowS
show :: α → String
show x = shows x ""We define a helper class Show1 , with shows1 as the only method.
For each representation type there is an instance of Show1 . The

extra Bool argument will be explained later. Datatype meta-information and sums are ignored. For units we have nothing to show,
and for constants we call shows recursively:
class Show1 φ whereshows1 :: Bool → φ χ → ShowS
instance (Show1 φ ) ⇒ Show1 (D1 γ φ ) whereshows1 b (M1 a) = shows1 b a
instance (Show1 φ , Show1 ψ) ⇒ Show1 (φ + ψ) whereshows1 b (L1 a) = shows1 b ashows1 b (R1 a) = shows1 b a
instance Show1 U1 where= idshows1 U1instance (Show φ ) ⇒ Show1 (K1 ι φ ) whereshows1 (K1 a) = shows a
The most interesting instances are for the meta-information of aconstructor and a selector. For simplicity, we always place parentheses around a constructor and ignore infix operators. We do display a labeled constructor with record notation. At the constructorlevel, we use conIsRecord to decide if we print surrounding brackets or not. We use the Bool argument to shows1 to encode that weare inside a labeled field, as we will need this for the product case:instance (Show1 φ , Constructor γ) ⇒ Show1 (M1 C γ φ ) whereshows1 c@(M1 a) =showString "(" ◦ showString (conName c)◦ showString " "◦ wrapRecord(shows1 (conIsRecord c) a ◦ showString ")")
where
wrapRecord :: ShowS → ShowS
wrapRecord s | conIsRecord c = showString "{ " ◦ s◦ showString " }"wrapRecord s | otherwise= s
For a selector, we print its label (as long as it is not empty), followedby an "=" and the value. In the product, we use the Bool to decide
if we print a space (unlabeled constructors) or a comma:
instance (Show1 φ , Selector γ) ⇒ Show1 (M1 S γ φ ) whereshows1 b s@(M1 a)| null (selName s) = shows1 b a| otherwise= showString (selName s)◦ showString " = " ◦ shows1 b a
instance (Show1 φ , Show1 ψ) ⇒ Show1 (φ × ψ) whereshows1 b (a × c) = shows1 b a◦ showString (if b then "," else " ")◦ shows1 b c
Finally, we provide the default:{−# DERIVABLE Show shows showsDefault #−}showsDefault :: (Representable0 α τ, Show1 τ)⇒ τ χ → α → ShowS
showsDefault rep x = shows1 False (from0 x ‘asTypeOf ‘ rep)
We have shown how to use meta-information to define a genericshow function. If we additionally account for infix constructors
and operator precedence for avoiding unnecessary parentheses,
we obtain a formal specification of how show behaves on every
Haskell 98 datatype.

4.

Compiler support

We now describe in detail the required compiler support for our
generic deriving mechanism.
We start by defining two predicates on types, isRep0 (φ )and isRep1 (φ ), which hold if φ can be made an instance ofRepresentable0 and Representable1 , respectively. The statement
isRep0 (φ ) holds if φ is any of the following:
1. A regular Haskell 98 datatype without context
2. An empty datatype
3. A type variable of kind ?
We also require that for every type ψ that appears as an argument
to a constructor of φ , isRep0 (ψ) holds. φ cannot use existential
quantification, type equalities or any other extensions.
The statement isRep1 (φ ) holds if the following conditions bothhold:
1. isRep0 (φ )2. φ is of kind ? → ? or k → ? → ?, for any kind k
Note that isRep0 holds for all the types of Section 2.4, while isRep1
holds for List, Expr, Decl, and Var.
Furthermore, we define the predicate ground (φ ) to determine whether or not a datatype has type variables. For instance,
ground ([Int ]) holds, but ground ([α ]) not. Finally, we assume thejexistence of an indexed fresh variable generator fresh pi , whichjbinds pi to a unique fresh variable.
For the remainder of this section, we consider a user-defined
datatype
data D α1 . . . αn = Con1 {l11 :: p11 , . . . , l1o1 :: po11 }..
.
1 :: p1 , . . . , lom :: pom }| Conm {lmmmmwith n type parameters, m constructors and possibly labeled paramj
jeter li of type pi at position j of constructor Coni .
4.1

Type representation (kind ?)In Figure 1, we show how we generate type representations fora datatype D satisfying isRep0 (D). We generate a number of
empty datatypes which we use in the meta-information: one for thedatatype, one for each constructor and one for each argument to a
constructor.
The type representation is a type synonym (RepD
0 ) with as many
type variables as D. It is a wrapped sum of wrapped products: thewrapping encodes the meta-information. We wrap all arguments toconstructors, even if the constructor is not a record. Since we use
a balanced sum (resp. product) encoding, a generic function can
use the meta-information to find out when the sum (resp. product)
structure ends, which is when we reach C1 (resp. S1 ). Each argument is tagged with Par0 if it is one of the type variables, or Rec0
if it is anything else (type application or a concrete datatype).
4.2 Representable0 instance
The instance Representable0 RepD
0 is defined in Figure 2, as introduced in Section 2. The patterns of the from0 function are theconstructors of the datatype applied to fresh variables. The same
patterns become expressions in function to0 . The patterns of to0
are also the same as the expressions of from0 , and they represent
the different values of a balanced sum of balanced products, properly wrapped to account for the meta-information. Note that, forRepresentable0 , the functions tuple and wrap do not behave differently depending on whether we are in from0 or to0 , so for thesedeclarations the dir argument is not needed. Similarly, the wrap

function could have been inlined. These definitions will be refinedin Section 4.4.
4.3Type representation (kind ? → ?)See Figure 3 for the type representation of type constructors.
We keep the sum-of-products structure and meta-information unchanged. At the arguments, however, we can use Par0 , Par1 , Rec0 ,Rec1 , or composition. We use Par1 for the type variable α, andPar0 for other type variables of kind ?. A recursive occurrence ofa type containing αn is marked with Rec1 . A recursive occurrenceof a type with no type variables is marked with Rec0 , as there isno variable to abstract from. Finally, for a recursive occurrence ofa type which contains something else than αn we use composition,and recursively analyze the contained type.
4.4 Representable1 instanceThe definition of the embedding-projection pair for kind ? → ?
datatypes, shown in Figure 4, reflects the more complicated type
representation. The patterns are unchanged. However, the expressions in to1 need some additional unwrapping. This is encoded in
var and unwC: an application to a type variable other than αn has
been encoded as a composition, so we need to unwrap the elementsof the contained type. We use fmap for this purpose: since we require isRep1 (φ ), we know that we can use fmap (see Section 3.4).
The user should always derive Functor for container types, as thesecan appear to the left of a composition.
Unwrapping is dual to wrapping: we use Par1 for the type parameter αn , Rec1 for containers of αn , K1 for other type parametersand ground types, and composition for application to types otherthan αn . Considering composition, in to1 we generate only Comp1applied to a fresh variable, as this is a pattern; the necessary unwrapping of the contained elements is performed in the right-handside expression. In from1 the contained elements are tagged properly: this is performed by wCα .
4.5

Meta-information

We generate three meta-information instances. For datatypes, we
generate
instance Datatype $D wheremoduleName= mNamedatatypeName = dName ,where dName is a String with the unqualified name of datatype D
and mName is a String with the name of the module in which D is
defined.
For constructors, we generateinstance Constructor $Coni where= nameconName{conFixity= fixity}{conIsRecord = True} ,where i ∈ 1..m, and name is the unqualified name of constructor
Coni . The braces around conFixity indicate that this method isonly defined if Coni is an infix constructor. In that case, fixity
is Infix assoc prio, where prio is an integer denoting the priorityof Coni , and assoc is one of LeftAssociative, RightAssociative, or
NotAssociative. These are derived from the declaration of Coni as
an infix constructor. The braces around conIsRecord indicate that
this method is only defined if Coni uses record notation.
For all i ∈ {1..m}, we generatejinstance Selector $Li {where selNamej= li } ,where j ∈ {1..oi }. The brackets indicate that the instance is only
given a body if Coni uses record notation. Otherwise, the default
implementation for selName is used, i.e. const "".

data $Djdata $Con1..
.
data $Conm
data $L11..
.
omdata $Lmjommtype RepD
0 α1 . . . αn = D1 $D (∑i=1 (C1 $Coni (∏j=1 (S1 $Li (arg pi )))))= V1∑ni=1 x | n ≡ 0
|n≡1
=x
n−m
| otherwise = ∑mi=1 x + ∑i=1 x where m = bn / 2c

j

j

j

arg pi | ∃k ∈ {1..n} : pi ≡ αk = Par0 pi| otherwise∏ni=1 x | n ≡ 0

j= Rec0 pi

= U1
|n≡1
=x
n−m
| otherwise = ∏mi=1 x × ∏i=1 x where m = bn / 2c
Figure 1. Code generation for the type representation (kind ?)instance Representable0 (D α1 . . . αn ) (RepD
0 α1 . . . αn ) where {
from
from
to
from0 pat1 = exp1 ;to0 patto
1 = exp1 ;
..
..
.
.
from
from
to
from0 patm = expm ;to0 pattom = expm ; }inji,m x | m ≡ 0 = ⊥|m≡1=x| i 6 m0 = L1 (inji,m0 x)| i > m0 = R1 (inji0 ,m−m0 x)
where m0 = bm / 2ci0 = bi / 2c

from

expto
i
from

expi

= pati= Coni (fresh p1i ) . . . (fresh poi i )= pattoi= M1 (inji,m (M1 (tuplei (p1i . . . poi i ))))

joi
tupledir= M1 U1i (pi . . . pi ) | oi ≡ 0
j| oi ≡ j= M1 (wrapdir (fresh pi ))
k+1
1
k
dir
| otherwise = (tupledir. . . pmi ))i (pi . . . pi )) × (tuplei (piwhere k = boi / 2c

wrapdir p = K1 p
Figure 2. Code generation for the Representable0 instance
j

j

om
m
type RepD
1 α1 . . . αn−1 = D1 $D (∑i=1 (C1 $Coni (∏j=1 (S1 $Li (arg pi )))))jjj

arg pi | ∃k ∈ {1..n−1} : pi ≡ αk

= Par0 pi

j| pi ≡ αn= Par1jj| pi ≡ φ αn ∧ isRep1 (φ )= Rec1 pi
j| pi ≡ φ β ∧ isRep1 (φ ) ∧ ¬ ground (β ) = φ ◦ arg βj| otherwise= Rec0 pin∑mi=1 x and ∏j=1 x as in Figure 1.

Figure 3. Code generation for the type representation (kind ? → ?)instance Representable1 (D α1 . . . αn−1 ) (RepD
1 α1 . . . αn−1 ) where {
from
from
from1 pat1 = exp1 ;to1 patto
=
expto
1
1;
..
..
.
.
from
from
to
from1 patm = expm ;to1 pattom = expm ; }from

patdiri , expijjjvar pi | pi ≡ φ α ∧ α 6≡ αnj∧ isRep1 (φ ) = fmap unwCα (fresh pi )j| otherwise= fresh pi

dir x).
, inji,m x, and tuplediri (p1 . . . pm ) as in Figure 2 (but using the new wrapjj

wrapdir pi | pi ≡ αn
= Par1 (fresh pi )jj| pi ≡ φ αn ∧ isRep1 (φ ) = Rec1 (fresh pi )jj| ∃k ∈ {1..n} : pi ≡ αk
= K1 (fresh pi )
j

oi
1
expto
i = Coni (var pi ) . . . (var pi )j| pi ≡ φ α ∧ ¬ isRep1 (φ ) = K1 (fresh pi )jj| pi ≡ φ α ∧ dir ≡ from = Comp1 (fmap wCα (fresh pi ))j| otherwise= Comp1 (fresh pi )unwCα | α ≡ αn
= unPar1| α ≡ φ αn ∧ isRep1 (φ ) = unRec1| α ≡ φ β ∧ ground (β ) = unRec0| α ≡ φ β ∧ isRep1 (φ ) = fmap unwCβ ◦ unComp1
wCα | α ≡ αn
= Par1| ground (α)= K1| α ≡ φ αn ∧ isRep1 (φ ) = Rec1
| α ≡ φ β ∧ isRep1 (φ ) = Comp1 ◦ (fmap wCβ )Figure 4. Code generation for the Representable1 instance4.6

Default instances

The instances of a class representing the different cases of a genericfunction on representation types present somewhat more of a challenge because they refer to a specific function defined by thegeneric programmer (in our running example encodeDefault). The
compiler knows which function to use due to the DEFAULT pragma(Section 3.3).
After the default function has been determined, the only otherconcern is passing the explicit type representation, encoded as a
typed ⊥.
4.6.1

Generic functions on Representable0

For each generic function f that is a method of the type class F, andfor every datatype D with type arguments α1 . . . αn and associatedrepresentation type RepD
0 α1 . . . αn χ, the compiler generates:
instance (C . . .) ⇒ F (D α1 . . . αn ) wheref = fD ⊥ wherefD :: (C . . .) ⇒ RepD
0 α1 . . . αn χ → β
fD = fDefault
The type β is the type of f specialized to D, and χ is a freshtype variable. The context C is the same in the instance head andin function fD . The exact context generated depends on the way
the user specified the deriving. If deriving F was attached to the→, . . . , F −→, where →−datatype, we generate a context F −ααα is then1variable α applied to enough fresh type variables to achieve fullsaturation. This approach gives the correct behavior for Haskell 98
derivable classes like Show. In general, however, it is not correct:
we cannot assume that we require F αi for all i ∈ {1 . . n}: genericchildren, for instance, does not require any constraints, as it is
not a recursive function. Worse even, we might require constraints
other than these, as a generic function can use other functions, forinstance.
To avoid these problems we can use the standalone deriving
extension. If we have a standalone deriving
deriving instance (C . . .) ⇒ F (D α1 . . . αn )we can simply use this context for the instance. In general, however,the compiler should be able to infer the right context by analyzing
the context of the generic function and the structure of the datatype.
4.6.2

Generic functions on Representable1

For each generic function f that is a method of the type class F, andfor every datatype D with type arguments α1 . . . αn and associatedrepresentation type RepD
1 α1 . . . αn , the compiler generates:
instance (C . . .) ⇒ F (D α1 . . . αn−1 ) wheref = fD ⊥ wherefD :: (C . . .) ⇒ RepD
1 α1 . . . αn → β
fD = fDefault
The type β is the type of f specialized to D (in other words,
f :: β ). This code is almost the same as that for generic functions
on Representable0 , with a small exception for handling the lasttype variable (αn ). The context can be copied from the standalone
deriving, if one was used, or just inferred by the compiler.
4.7

UHC specifics

We have a prototype implementation of our deriving mechanism
in UHC. Although generating the required datatypes and instances
is straightforward, we have to resolve some subtle issues. In our
implementation, the following issues arose:
Which stage of the compiler pipeline generates the datatypes andinstances? Ideally, all deriving-related code is generated as earlyas possible, for example during desugaring, so later compiler stages
can type check the generated code. However, the generation needs
kind information of types and classes, which is only available after kind checking. In UHC, the datatypes and instances are directly
generated as intermediate Core, directed by kind information, andonly the derived instances are intertwined with type checking andcontext reduction because of the use of the default deriving functions.
Use of fmap. The generation of embedding-projection pairs fortypes with composition requires fmap, which in turn requires thecontext reduction machinery to resolve overloading. This complicates the interaction with the compiler pipeline, because the generation becomes not only kind-directed, but also context reduction
proof-directed. However, all occurrences of fmap are applied to theidentity function id, because wrappers like Par1 are defined as newtypes. In UHC, the use of context reduction is avoided assuming theequality fmap id ≡ id.
Code size. Some quick measurements show a 10% increase in
the size of the generated code. Although language pragmas like
GenericDeriving and NoGenericDeriving could selectively switch
this feature on or off, this would defeat the purpose of genericity. Once turned off for a datatype, no Representables are generated, and no generic instances can be defined anymore. Instead,later transformations should prune unused code. These issues needfurther investigation.
Bootstrapping. As soon as a user defines a datatype, code generation generates the supporting datatypes. Such datatypes (e.g.
$Con1 ) and the datatypes used by supporting datatypes (e.g. Bool,used in the return type of conIsRecord) are mutually dependent,
which is detected by binding group analysis. Each binding grouptype analysis must deal with mutually dependent datatypes. This
also means that the supporting definitions must be available in thefirst module that contains a datatype.
Interaction with desugaring. Currently, deriving clauses are justsyntactic sugar for standalone deriving. After desugaring, we cannot decide to generate a Representable0 or a Representable1 instance because kind information is not available. Automaticallygenerating the correct context for such an instance cannot be done
either. To work around this limitation, we only accept deriving
clauses for generic classes that use Representable0 . Derivings for
Representable1 classes have to use standalone deriving syntax,
since then we no longer need to infer a context, and can let the
programmer provide the required context.

5.

Alternatives

We have described how to implement a deriving mechanism thatcan be used to specify many datatype-generic functions in Haskell.
There are other alternatives, of varying complexity and type-safety.
5.1

Pre-processors

The simplest, most powerful and least type safe alternative to
our approach is to implement deriving by pre-processing thesource file(s), analyzing the datatypes definitions and generating
the required instances with a tool such as DrIFT (Winstanley and
Meacham 2008). This requires no work from the compiler writer,
but does not simplify the task of adding new derivable classes, as
programming by generating strings is not very convenient.
Staged meta-programming lies in between a pre-processor andan embedded datatype-generic representation. GHC supports Template Haskell (Sheard and Peyton Jones 2002), which has becomea standard tool for obtaining reflection in Haskell. While Template
Haskell provides possibly more flexibility than the purely librarybased approach we describe, it imposes a significant hurdle on thecompiler writer, who does not only have to implement a language
for staged programming (if one does not yet exist for the compiler, like in UHC), but also keep this complex component up-todate with the rest of the compiler, as it evolves. As an example,
Template Haskell support for GADTs and type families only arrived much later than the features themselves. Also, for the derivable class writer, using Template Haskell is more cumbersome anderror-prone than writing a datatype-generic definition in Haskell itself.
For these reasons we think that our library-based approach,while having some limitations, has a good balance of expressive
power, type safety, and the amount of implementation work required.
5.2

instance Show Exp whereshows (Plus e1 e2 ) = shows e1 ◦ showString "+" ◦ shows e2Expshows x= showsDefault (⊥ :: Rep0 χ) x

Generic programming libraries

Another design choice we made was in the specific library approach
to use. We have decided not to use any of the existing libraries but
instead to develop yet another one. However, our library is merely avariant of existing libraries, from which it borrows many ideas. We
see our representation as a mixture between regular (Van Noortet al. 2008) and instant-generics (Chakravarty et al. 2009). We
share the functorial view with regular; however, we abstract froma single type parameter, and not from the recursive occurrence. Our
library can also be seen as instant-generics extended with asingle type parameter. However, having one parameter allows us
to deal with composition effectively, and we do not duplicate therepresentation for types without parameters.
Since we wanted to avoid using GADTs, and we wanted an
extensible approach, we had to exclude most of the other generic
programming libraries. The only possible choice would have been
EMGM (Oliveira et al. 2007), which supports type parameters, ismodular and does not require fancy extensions. However, EMGM
duplicates the representation for higher arities, and encodes therepresentation of a type at the value level. We prefer encoding therepresentation only at the type level, as this has proven to allow for
type-indexed datatypes (see Section 7.2).

6.

that derive the corresponding class. We only miss the ability torepresent nested higher-kinded datatypes, as our representation abstracts only over a parameter of kind ?.
Regarding expressiveness, our library scores good for most criteria: we can abstract over type constructors, give ad-hoc definitions
for datatypes, our approach is extensible, supports multiple genericarguments, represents the constructor names and can express consumers, transformers, and producers. We cannot express gmapQ in
our approach, but our generic functions are still first-class: we cancall generic map with generic show as argument, for instance. Adhoc definitions for constructors would be of the form:

Related work

The generic programming library we present shares many aspects
with regular (Van Noort et al. 2008) and instant-generics(Chakravarty et al. 2009). Clean (Alimarine and Plasmeijer 2001)
has also integrated generic programming directly in the language.
We think our approach is more lightweight: we express our genericfunctions almost entirely in Haskell and require only one small
syntactic extension. On the other hand, the approach taken in Clean
allows defining generic functions with polykinded types (Hinze
2002), which means that the function bimap (see Section 2.1), forinstance, can be defined. Not all Clean datatypes are supported:
quantified types, for example, cannot derive generic functions. Our
approach does not support all features of Haskell datatypes, but
most common datatypes and generic functions are supported.
An extension for derivable type classes similar to ours has
been developed by Hinze and Peyton Jones (2001) in GHC. As
in Clean, this extension requires special syntax for defining genericfunctions, which makes it harder to implement and maintain. In
contrast, generic functions written in our approach are portable
across different compilers. Furthermore, Hinze and Peyton Jones’s
approach cannot express functions such as fmap, as their type
representation does not abstract over type variables.
Rodriguez Yakushev et al. (2008) give criteria for comparing
generic programming libraries. These criteria consider the library’s
use of types, and its expressiveness and usability. Regarding types,
our library scores very good: we can represent regular, higherkinded, nested, and mutually recursive datatypes. We can also express subuniverses: generic functions are only applicable to types

Exp

However, in our current implementation, Rep0 is an internal typesynonym not exposed to the user. Exposing it to the user would require a naming convention. If UHC supported type families (Schrijvers et al. 2008), Rep0 could be a visible type family, which would
solve our problem for ad-hoc definitions of constructors. It would
also remove the need for using asTypeOf in Section 2.3.
Regarding usability, our approach supports separate compilation, is highly portable, has automatic generation of its two representations, requires minimal work to instantiate and define ageneric function, is implemented in a compiler and is easy to use.
We have not yet benchmarked our library in UHC. In GHC, we
believe it will be as efficient as instant-generics and regular.

7.

Future work

Our solution is applicable to a wide range of datatypes and can
express many generic functions. However, some limitations still
remain, and many improvements are possible. In this section weoutline some possible directions for future research.
7.1

Supported datatypes

Our examples in Section 2 show that we can represent many common forms of datatypes. We believe that we can represent all of the
Haskell 98 standard datatypes in Representable0 , except for constrained datatypes. We could easily support constrained datatypes
by propagating the constraints to the generic instances.
Regarding Representable1 , we can represent many, but not all
datatypes. Consider a nested datatype for representing balanced
trees:
data Perfect ρ = Node ρ | Perfect (ρ, ρ)We cannot give a representation of kind ? → ? for Perfect, sincefor the Perfect constructor we would need something like Perfect ◦Rec1 ((, ) ρ). However, the type variable ρ is no longer available,
because we abstract from it. This limitation is caused by the factthat we abstract over a single type parameter. The approach taken
by Hesselink (2009) is more general and fits closely with ourapproach, but it is not clear if it is feasible without advanced
language extensions.
Note that for this particular case we could use a datatype whichpairs elements of a single type:
data Pair ρ = Pair ρ ρ
The representation for the Perfect constructor could then be Perfect ◦Rec1 Pair.
7.2

Type-indexed datatypes

Some generic functionality, like the zipper (Huet 1997) and genericrewriting (Van Noort et al. 2008), require not only type-indexed
functions but also type-indexed datatypes: types that depend on thestructure of other types (Hinze et al. 2002). We plan to investigate
how type-indexed datatypes can be integrated easily in our genericderiving mechanism, while still avoiding advanced language extensions.

grant. We thank Thomas van Noort and the anonymous reviewers
for their helpful feedback.

7.3

Artem Alimarine and Rinus Plasmeijer. A Generic Programming Extension
for Clean. In IFL’01, pages 168–185. Springer-Verlag, 2001.
Roland Backhouse, Patrik Jansson, Johan Jeuring, and Lambert Meertens.
Generic programming—an introduction. In AFP’98, volume 1608 of
LNCS, pages 28–115. Springer, 1999.
Manuel M. T. Chakravarty, Gabriel C. Ditu, and Roman Leshchinskiy.
Instant generics: Fast and easy, 2009. Draft version.
Atze Dijkstra, Jeroen Fokker, and S. Doaitse Swierstra. The architecture of
the Utrecht Haskell compiler. In Haskell’09, pages 93–104. ACM, 2009.
Erik Hesselink. Generic programming with fixed points for parametrized
datatypes. Master’s thesis, Utrecht University, 2009.

Generic functions

The representation types we propose limit the kind of generic functions we can define. We can express the Haskell 98 standard derivable classes Eq, Ord, Enum, Bounded, Show, and Read, even lifting some of the restrictions imposed on the Enum and Bounded
instances. All of these are expressible for Representable0 types.
Using Representable1 , we can implement Functor, as the parameter of the Functor class is of kind ? → ?. The same holds for
Foldable and Traversable. For Typeable we can express Typeable0
and Typeable1 .
On the other hand, the Data class has very complex genericfunctions which cannot be expressed with our representation. Function gfoldl, for instance, requires access to the original datatypeconstructor, something we cannot do with the current representation. In the future we plan to explore if and how we can change ourrepresentation to allow us to express more generic functions.
7.4

Efficiency

The instances derived in our approach are not specialized for adatatype and may therefore incur an unacceptable performance
penalty. However, our recent research (Magalhães et al. 2010) indicates that simple inlining and symbolic evaluation, present in someform in every optimizing compiler, suffice in most cases to optimize away all overhead from generic representations. We plan toinvestigate how these optimizations can be expressed and automatically applied without any user intervention in UHC.
7.5

Implementation in GHC

Our approach is designed to be as portable as possible. Therefore,
we would like to implement it in other compilers, most importantly in GHC. As a first step, we believe we can easily implement
most of our generic deriving mechanism in GHC using Template
Haskell. The code for the generic functions is kept intact: only the
DERIVABLE pragma needs a different syntax. For the user code, acode splice would trigger the generation of generic representations
and function instances.

8.

Conclusion

We have shown how datatype-generic programming can be better
integrated in Haskell by revisiting the deriving mechanism. All
Haskell 98 derivable type classes can be expressed as generic functions in our library, with the advantage of becoming easily readable and portable. Additionally, many other type classes, such as
Functor and Typeable, can be declared derivable. Our extension requires little extra syntax, so it is easy to implement. Adding new
generic derivings can be done by generic programmers in regular
Haskell; previously, this would be the compiler developer’s task,
and would be done using code generation, which is more errorprone and verbose.
We have implemented our solution in UHC and invite everyone
to derive instances for their favorite datatypes or even write theirown derivings. We hope our work paves the future for a redefinitionof the behavior of derived instances for Haskell Prime (Wallace
et al. 2007).

Acknowledgments
This work has been partially funded by the Portuguese Foundationfor Science and Technology (FCT) via the SFRH/BD/35999/2007

References

Ralf Hinze. Polytypic values possess polykinded types. SCP, 43(2-3):129–
159, 2002.
Ralf Hinze and Andres Löh. Generic programming in 3D. SCP, 74(8):590–628, 2009.
Ralf Hinze and Simon Peyton Jones. Derivable type classes. Electronic
Notes in Theoretical Computer Science, 41(1):5–35, 2001.
Ralf Hinze, Johan Jeuring, and Andres Löh. Type-indexed data types. In
MPC’02, volume 2386 of LNCS, pages 148–174. Springer, 2002.
Ralf Hinze, Johan Jeuring, and Andres Löh. Comparing approches togeneric programming in Haskell. In Datatype-Generic Programming,volume 4719 of LNCS, pages 72–149. Springer, 2007.
Gérard Huet. The zipper. JFP, 7(5):549–554, 1997.
Patrik Jansson and Johan Jeuring. PolyP—a polytypic programming language extension. In POPL’97, pages 470–482. ACM, 1997.
Mark Jones. Type classes with functional dependencies. In ESOP’00,
volume 1782 of LNCS, pages 230–244. Springer, 2000.
Ralf Lämmel and Simon Peyton Jones. Scrap your boilerplate: a practical
approach to generic programming. In TLDI’03, pages 26–37, 2003.
Ralf Lämmel and Simon Peyton Jones. Scrap more boilerplate: reflection,
zips, and generalised casts. In ICFP’04, pages 244–255. ACM, 2004.
Andres Löh. Exploring Generic Haskell. PhD thesis, Utrecht University,
2004.
José Pedro Magalhães, Stefan Holdermans, Johan Jeuring, and Andres Löh.
Optimizing generics is easy! In PEPM’10, pages 33–42. ACM, 2010.
Thomas van Noort, Alexey Rodriguez Yakushev, Stefan Holdermans, Johan
Jeuring, and Bastiaan Heeren. A lightweight approach to datatypegeneric rewriting. In WGP’08, pages 13–24. ACM, 2008.
Bruno C.d.S. Oliveira, Ralf Hinze, and Andres Löh. Extensible and modular
generics for the masses. In TFP’06, pages 199–216. Intellect, 2007.
Simon Peyton Jones et al. Haskell 98, Language and Libraries. The Revised
Report. Cambridge University Press, 2003. A special issue of JFP.
Alexey Rodriguez Yakushev, Johan Jeuring, Patrik Jansson, Alex Gerdes,
Oleg Kiselyov, and Bruno C.d.S. Oliveira. Comparing libraries forgeneric programming in Haskell. In Haskell’08, pages 111–122. ACM,
2008.
Tom Schrijvers, Simon Peyton Jones, Manuel M. T. Chakravarty, and Martin Sulzmann. Type checking with open type functions. In ICFP’08,
pages 51–62. ACM, 2008.
Tim Sheard and Simon Peyton Jones. Template metaprogramming for
Haskell. In Haskell’02, pages 1–16. ACM, 2002.
Malcom Wallace et al.
Derived instances—Haskell Prime.
http://hackage.haskell.org/trac/haskell-prime/wiki/
DerivedInstances, April 2007. [Online; accessed 07-June-2010].
Noel Winstanley and John Meacham.
DrIFT user guide.
http://repetae.net/computer/haskell/DrIFT/drift.html, February 2008. [Online; accessed 07-June-2010].