Update the User Guide with generics stuff.

2 files changed, 202 insertions, 212 deletions

diff --git a/docs/users_guide/flags.xml b/docs/users_guide/flags.xml
index 4a502b4b8c..982c681e55 100644
--- a/docs/users_guide/flags.xml
+++ b/docs/users_guide/flags.xml
@@ -682,7 +682,10 @@
 	    </row>
 	    <row>
 	      <entry><option>-XGenerics</option></entry>
-	      <entry>Enable <link linkend="generic-classes">generic classes</link></entry>
+	      <entry>Enables <option>-XDeriveRepresentable</option> and <option>-XDefaultSignatures</option>. 
+               No longer enables <link linkend="generic-classes">generic classes</link>.
+               See also GHC's support for
+               <link linkend="generic-programming">generic programming</link>.</entry>
 	      <entry>dynamic</entry>
 	      <entry><option>-XNoGenerics</option></entry>
 	    </row>
@@ -977,6 +980,12 @@
 	      <entry><option>-XNoDeriveDataTypeable</option></entry>
 	    </row>
 	    <row>
+	      <entry><option>-XDeriveRepresentable</option></entry>
+	      <entry>Enable <link linkend="deriving-typeable">deriving for the Representable0 class</link>.</entry>
+	      <entry>dynamic</entry>
+	      <entry><option>-XNoDeriveRepresentable</option></entry>
+	    </row>
+	    <row>
 	      <entry><option>-XGeneralizedNewtypeDeriving</option></entry>
 	      <entry>Enable <link linkend="newtype-deriving">newtype deriving</link>.</entry>
 	      <entry>dynamic</entry>
@@ -1008,6 +1017,12 @@
 	      <entry><option>-XNoConstrainedClassMethods</option></entry>
 	    </row>
 	    <row>
+	      <entry><option>-XDefaultSignatures</option></entry>
+	      <entry>Enable <link linkend="class-default-signatures">default signatures</link>.</entry>
+	      <entry>dynamic</entry>
+	      <entry><option>-XNoDefaultSignatures</option></entry>
+	    </row>
+	    <row>
 	      <entry><option>-XMultiParamTypeClasses</option></entry>
 	      <entry>Enable <link linkend="multi-param-type-classes">multi parameter type classes</link>.</entry>
 	      <entry>dynamic</entry>
diff --git a/docs/users_guide/glasgow_exts.xml b/docs/users_guide/glasgow_exts.xml
index 89198c4264..178f79a95b 100644
--- a/docs/users_guide/glasgow_exts.xml
+++ b/docs/users_guide/glasgow_exts.xml
@@ -3212,6 +3212,12 @@ then writing the data type instance by hand.
 </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>.
@@ -3533,6 +3539,47 @@ GHC lifts this restriction (flag <option>-XConstrainedClassMethods</option>).
 
 
 </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">
@@ -9139,257 +9186,185 @@ allows you to fool the type checker.
 <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>