</para>
</listitem>
+<listitem><para> With <option>-XDeriveRepresentable</option>, you can derive
+instances of the class <literal>Representable0</literal>, defined in
+<literal>GHC.Generics</literal>. You can use these to define generic functions,
+as described in <xref linkend="generic-programming"/>.
+</para></listitem>
+
<listitem><para> With <option>-XDeriveFunctor</option>, you can derive instances of
the class <literal>Functor</literal>,
defined in <literal>GHC.Base</literal>.
</sect3>
+
+
+<sect3 id="class-default-signatures">
+<title>Default signatures</title>
+
+<para>
+Haskell 98 allows you to define a default implementation when declaring a class:
+<programlisting>
+ class Enum a where
+ enum :: [a]
+ enum = []
+</programlisting>
+The type of the <literal>enum</literal> method is <literal>[a]</literal>, and
+this is also the type of the default method. You can lift this restriction
+and give another type to the default method using the flag
+<option>-XDefaultSignatures</option>. For instance, if you have written a
+generic implementation of enumeration in a class <literal>GEnum</literal>
+with method <literal>genum</literal> in terms of <literal>GHC.Generics</literal>,
+you can specify a default method that uses that generic implementation:
+<programlisting>
+ class Enum a where
+ enum :: [a]
+ default enum :: (Representable0 a, GEnum (Rep0 a)) => [a]
+ enum = map to0 genum
+</programlisting>
+We reuse the keyword <literal>default</literal> to signal that a signature
+applies to the default method only; when defining instances of the
+<literal>Enum</literal> class, the original type <literal>[a]</literal> of
+<literal>enum</literal> still applies. When giving an empty instance, however,
+the default implementation <literal>map to0 genum</literal> is filled-in,
+and type-checked with the type
+<literal>(Representable0 a, GEnum (Rep0 a)) => [a]</literal>.
+</para>
+
+<para>
+We use default signatures to simplify generic programming in GHC
+(<xref linkend="generic-programming"/>).
+</para>
+
+
+</sect3>
</sect2>
<sect2 id="functional-dependencies">
<title>Generic classes</title>
<para>
-The ideas behind this extension are described in detail in "Derivable type classes",
-Ralf Hinze and Simon Peyton Jones, Haskell Workshop, Montreal Sept 2000, pp94-105.
-An example will give the idea:
+GHC used to have an implementation of generic classes as defined in the paper
+"Derivable type classes", Ralf Hinze and Simon Peyton Jones, Haskell Workshop,
+Montreal Sept 2000, pp94-105. These have been removed and replaced by the more
+general <link linkend="generic-programming">support for generic programming</link>.
</para>
-<programlisting>
- import Data.Generics
-
- class Bin a where
- toBin :: a -> [Int]
- fromBin :: [Int] -> (a, [Int])
-
- toBin {| Unit |} Unit = []
- toBin {| a :+: b |} (Inl x) = 0 : toBin x
- toBin {| a :+: b |} (Inr y) = 1 : toBin y
- toBin {| a :*: b |} (x :*: y) = toBin x ++ toBin y
-
- fromBin {| Unit |} bs = (Unit, bs)
- fromBin {| a :+: b |} (0:bs) = (Inl x, bs') where (x,bs') = fromBin bs
- fromBin {| a :+: b |} (1:bs) = (Inr y, bs') where (y,bs') = fromBin bs
- fromBin {| a :*: b |} bs = (x :*: y, bs'') where (x,bs' ) = fromBin bs
- (y,bs'') = fromBin bs'
-</programlisting>
-<para>
-This class declaration explains how <literal>toBin</literal> and <literal>fromBin</literal>
-work for arbitrary data types. They do so by giving cases for unit, product, and sum,
-which are defined thus in the library module <literal>Data.Generics</literal>:
-</para>
-<programlisting>
- data Unit = Unit
- data a :+: b = Inl a | Inr b
- data a :*: b = a :*: b
-</programlisting>
-<para>
-Now you can make a data type into an instance of Bin like this:
-<programlisting>
- instance (Bin a, Bin b) => Bin (a,b)
- instance Bin a => Bin [a]
-</programlisting>
-That is, just leave off the "where" clause. Of course, you can put in the
-where clause and over-ride whichever methods you please.
-</para>
+</sect1>
- <sect2>
- <title> Using generics </title>
- <para>To use generics you need to</para>
- <itemizedlist>
- <listitem>
- <para>
- Use the flags <option>-XGenerics</option> (to enable the
- extra syntax and generate extra per-data-type code),
- and <option>-package syb</option> (to make the
- <literal>Data.Generics</literal> module available.
- </para>
- </listitem>
- <listitem>
- <para>Import the module <literal>Data.Generics</literal> from the
- <literal>syb</literal> package. This import brings into
- scope the data types <literal>Unit</literal>,
- <literal>:*:</literal>, and <literal>:+:</literal>. (You
- don't need this import if you don't mention these types
- explicitly; for example, if you are simply giving instance
- declarations.)</para>
- </listitem>
- </itemizedlist>
- </sect2>
-<sect2> <title> Changes wrt the paper </title>
-<para>
-Note that the type constructors <literal>:+:</literal> and <literal>:*:</literal>
-can be written infix (indeed, you can now use
-any operator starting in a colon as an infix type constructor). Also note that
-the type constructors are not exactly as in the paper (Unit instead of 1, etc).
-Finally, note that the syntax of the type patterns in the class declaration
-uses "<literal>{|</literal>" and "<literal>|}</literal>" brackets; curly braces
-alone would ambiguous when they appear on right hand sides (an extension we
-anticipate wanting).
-</para>
-</sect2>
+<sect1 id="generic-programming">
+<title>Generic programming</title>
-<sect2> <title>Terminology and restrictions</title>
<para>
-Terminology. A "generic default method" in a class declaration
-is one that is defined using type patterns as above.
-A "polymorphic default method" is a default method defined as in Haskell 98.
-A "generic class declaration" is a class declaration with at least one
-generic default method.
+Using a combination of <option>-XDeriveRepresentable</option>
+(<xref linkend="deriving-typeable"/>) and
+<option>-XDefaultSignatures</option> (<xref linkend="class-default-signatures"/>),
+or simply <option>-XGenerics</option>, you can easily do datatype-generic
+programming using the <literal>GHC.Generics</literal> framework. This section
+gives a very brief overview of how to do it. For more detail please refer to the
+<ulink url="http://www.haskell.org/haskellwiki/Generics">HaskellWiki page</ulink>
+or the original paper:
</para>
-<para>
-Restrictions:
<itemizedlist>
<listitem>
<para>
-Alas, we do not yet implement the stuff about constructor names and
-field labels.
+José Pedro Magalhães, Atze Dijkstra, Johan Jeuring, and Andres Löh.
+<ulink url="http://dreixel.net/research/pdf/gdmh.pdf">
+ A generic deriving mechanism for Haskell</ulink>.
+<citetitle>Proceedings of the third ACM Haskell symposium on Haskell</citetitle>
+(Haskell'2010), pp. 37-48, ACM, 2010.
</para>
</listitem>
+</itemizedlist>
-<listitem>
-<para>
-A generic class can have only one parameter; you can't have a generic
-multi-parameter class.
-</para>
-</listitem>
+<emphasis>Note</emphasis>: the current support for generic programming in GHC
+is preliminary. In particular, we only allow deriving instances for the
+<literal>Representable0</literal> class. Support for deriving
+<literal>Representable1</literal> (and thus enabling generic functions of kind
+<literal>* -> *</literal> such as <literal>fmap</literal>) will come at a
+later stage.
-<listitem>
-<para>
-A default method must be defined entirely using type patterns, or entirely
-without. So this is illegal:
-<programlisting>
- class Foo a where
- op :: a -> (a, Bool)
- op {| Unit |} Unit = (Unit, True)
- op x = (x, False)
-</programlisting>
-However it is perfectly OK for some methods of a generic class to have
-generic default methods and others to have polymorphic default methods.
-</para>
-</listitem>
-<listitem>
-<para>
-The type variable(s) in the type pattern for a generic method declaration
-scope over the right hand side. So this is legal (note the use of the type variable ``p'' in a type signature on the right hand side:
-<programlisting>
- class Foo a where
- op :: a -> Bool
- op {| p :*: q |} (x :*: y) = op (x :: p)
- ...
-</programlisting>
-</para>
-</listitem>
+<sect2>
+<title>Deriving representations</title>
-<listitem>
<para>
-The type patterns in a generic default method must take one of the forms:
-<programlisting>
- a :+: b
- a :*: b
- Unit
-</programlisting>
-where "a" and "b" are type variables. Furthermore, all the type patterns for
-a single type constructor (<literal>:*:</literal>, say) must be identical; they
-must use the same type variables. So this is illegal:
+The first thing we need is generic representations. The
+<literal>GHC.Generics</literal> module defines a couple of primitive types
+that can be used to represent most Haskell datatypes:
+
<programlisting>
- class Foo a where
- op :: a -> Bool
- op {| a :+: b |} (Inl x) = True
- op {| p :+: q |} (Inr y) = False
+-- | Unit: used for constructors without arguments
+data U1 p = U1
+
+-- | Constants, additional parameters and recursion of kind *
+newtype K1 i c p = K1 { unK1 :: c }
+
+-- | Meta-information (constructor names, etc.)
+newtype M1 i c f p = M1 { unM1 :: f p }
+
+-- | Sums: encode choice between constructors
+infixr 5 :+:
+data (:+:) f g p = L1 (f p) | R1 (g p)
+
+-- | Products: encode multiple arguments to constructors
+infixr 6 :*:
+data (:*:) f g p = f p :*: g p
+</programlisting>
+
+For example, a user-defined datatype of trees <literal>data UserTree a = Node a
+(UserTree a) (UserTree a) | Leaf</literal> gets the following representation:
+
+<programlisting>
+-- Representation type
+type instance Rep0 (UserTree a) =
+ M1 D D1UserTree (
+ M1 C C1_0UserTree (
+ M1 S NoSelector (K1 P a)
+ :*: M1 S NoSelector (K1 R (UserTree a))
+ :*: M1 S NoSelector (K1 R (UserTree a)))
+ :+: M1 C C1_1UserTree U1)
+
+-- Representable0 instance
+instance Representable0 (UserTree a) where
+ from0 (Node x l r) = M1 (L1 (M1 (M1 (K1 x) :*: M1 (K1 l) :*: M1 (K1 r))))
+ from0 Leaf = M1 (R1 (M1 U1))
+ to0 (M1 (L1 (M1 (M1 (K1 x) :*: M1 (K1 l) :*: M1 (K1 r))))) = Node x l r
+ to0 (M1 (R1 (M1 U1))) = Leaf
+
+-- Meta-information
+data D1UserTree
+data C1_0UserTree
+data C1_1UserTree
+
+instance Datatype D1UserTree where
+ datatypeName _ = "UserTree"
+ moduleName _ = "Main"
+
+instance Constructor C1_0UserTree where
+ conName _ = "Node"
+
+instance Constructor C1_1UserTree where
+ conName _ = "Leaf"
</programlisting>
-The type patterns must be identical, even in equations for different methods of the class.
-So this too is illegal:
-<programlisting>
- class Foo a where
- op1 :: a -> Bool
- op1 {| a :*: b |} (x :*: y) = True
- op2 :: a -> Bool
- op2 {| p :*: q |} (x :*: y) = False
-</programlisting>
-(The reason for this restriction is that we gather all the equations for a particular type constructor
-into a single generic instance declaration.)
+This representation is generated automatically if a
+<literal>deriving Representable0</literal> clause is attached to the datatype.
+<link linkend="stand-alone-deriving">Standalone deriving</link> can also be
+used.
</para>
-</listitem>
+</sect2>
-<listitem>
-<para>
-A generic method declaration must give a case for each of the three type constructors.
-</para>
-</listitem>
+<sect2>
+<title>Writing generic functions</title>
-<listitem>
<para>
-The type for a generic method can be built only from:
- <itemizedlist>
- <listitem> <para> Function arrows </para> </listitem>
- <listitem> <para> Type variables </para> </listitem>
- <listitem> <para> Tuples </para> </listitem>
- <listitem> <para> Arbitrary types not involving type variables </para> </listitem>
- </itemizedlist>
-Here are some example type signatures for generic methods:
+A generic function is defined by creating a class and giving instances for
+each of the representation types of <literal>GHC.Generics</literal>. As an
+example we show generic serialization:
<programlisting>
- op1 :: a -> Bool
- op2 :: Bool -> (a,Bool)
- op3 :: [Int] -> a -> a
- op4 :: [a] -> Bool
-</programlisting>
-Here, op1, op2, op3 are OK, but op4 is rejected, because it has a type variable
-inside a list.
-</para>
-<para>
-This restriction is an implementation restriction: we just haven't got around to
-implementing the necessary bidirectional maps over arbitrary type constructors.
-It would be relatively easy to add specific type constructors, such as Maybe and list,
-to the ones that are allowed.</para>
-</listitem>
+data Bin = O | I
-<listitem>
-<para>
-In an instance declaration for a generic class, the idea is that the compiler
-will fill in the methods for you, based on the generic templates. However it can only
-do so if
- <itemizedlist>
- <listitem>
- <para>
- The instance type is simple (a type constructor applied to type variables, as in Haskell 98).
- </para>
- </listitem>
- <listitem>
- <para>
- No constructor of the instance type has unboxed fields.
- </para>
- </listitem>
- </itemizedlist>
-(Of course, these things can only arise if you are already using GHC extensions.)
-However, you can still give an instance declarations for types which break these rules,
-provided you give explicit code to override any generic default methods.
-</para>
-</listitem>
+class GSerialize f where
+ gput :: f a -> [Bin]
-</itemizedlist>
-</para>
+instance GSerialize U1 where
+ gput U1 = []
-<para>
-The option <option>-ddump-deriv</option> dumps incomprehensible stuff giving details of
-what the compiler does with generic declarations.
-</para>
+instance (GSerialize a, GSerialize b) => GSerialize (a :*: b) where
+ gput (a :*: b) = gput a ++ gput b
+
+instance (GSerialize a, GSerialize b) => GSerialize (a :+: b) where
+ gput (L1 x) = O : gput x
+ gput (R1 x) = I : gput x
+instance (GSerialize a) => GSerialize (M1 i c a) where
+ gput (M1 x) = gput x
+
+instance (Serialize a) => GSerialize (K1 i c a) where
+ gput (K1 x) = put x
+</programlisting>
+
+Typically this class will not be exported, as it only makes sense to have
+instances for the representation types.
+</para>
</sect2>
-<sect2> <title> Another example </title>
+<sect2>
+<title>Generic defaults</title>
+
<para>
-Just to finish with, here's another example I rather like:
+The only thing left to do now is to define a "front-end" class, which is
+exposed to the user:
<programlisting>
- class Tag a where
- nCons :: a -> Int
- nCons {| Unit |} _ = 1
- nCons {| a :*: b |} _ = 1
- nCons {| a :+: b |} _ = nCons (bot::a) + nCons (bot::b)
+class Serialize a where
+ put :: a -> [Bin]
- tag :: a -> Int
- tag {| Unit |} _ = 1
- tag {| a :*: b |} _ = 1
- tag {| a :+: b |} (Inl x) = tag x
- tag {| a :+: b |} (Inr y) = nCons (bot::a) + tag y
+ default put :: (Representable0 a, GSerialize (Rep0 a)) => a -> [Bit]
+ put a = gput (from0 a)
+</programlisting>
+Here we use a <link linkend="class-default-signatures">default signature</link>
+to specify that the user does not have to provide an implementation for
+<literal>put</literal>, as long as there is a <literal>Representable0</literal>
+instance for the type to instantiate. For the <literal>UserTree</literal> type,
+for instance, the user can just write:
+
+<programlisting>
+instance (Serialize a) => Serialize (UserTree a)
</programlisting>
+
+The default method for <literal>put</literal> is then used, corresponding to the
+generic implementation of serialization.
</para>
</sect2>
+
</sect1>
+
<sect1 id="monomorphism">
<title>Control over monomorphism</title>
projects / ghc-hetmet.git / commitdiff