DeriveFoldable for data types with existential constraints (#10447)

Reviewers: dolio, shachaf, ekmett, austin, #core_libraries_committee,
simonpj, bgamari

Reviewed By: simonpj, bgamari

Subscribers: thomie, bgamari

Differential Revision: https://phabricator.haskell.org/D1031

GHC Trac Issues: #10447

1 files changed, 257 insertions, 2 deletions

diff --git a/docs/users_guide/glasgow_exts.xml b/docs/users_guide/glasgow_exts.xml
index 51448d545b..22934fa94c 100644
--- a/docs/users_guide/glasgow_exts.xml
+++ b/docs/users_guide/glasgow_exts.xml
@@ -4019,7 +4019,7 @@ as described in <xref linkend="generic-programming"/>.
 
 <listitem><para> With <option>-XDeriveFunctor</option>, you can derive instances of
 the class <literal>Functor</literal>,
-defined in <literal>GHC.Base</literal>.
+defined in <literal>GHC.Base</literal>. See <xref linkend="deriving-functor"/>.
 </para></listitem>
 
 <listitem><para> With <option>-XDeriveDataTypeable</option>, you can derive instances of
@@ -4030,7 +4030,7 @@ deriving <literal>Typeable</literal>.
 
 <listitem><para> With <option>-XDeriveFoldable</option>, you can derive instances of
 the class <literal>Foldable</literal>,
-defined in <literal>Data.Foldable</literal>.
+defined in <literal>Data.Foldable</literal>. See <xref linkend="deriving-foldable"/>.
 </para></listitem>
 
 <listitem><para> With <option>-XDeriveTraversable</option>, you can derive instances of
@@ -4040,6 +4040,7 @@ instance dictates the instances of <literal>Functor</literal> and
 <literal>Foldable</literal>, you'll probably want to derive them too, so
 <option>-XDeriveTraversable</option> implies
 <option>-XDeriveFunctor</option> and <option>-XDeriveFoldable</option>.
+See <xref linkend="deriving-traversable"/>.
 </para></listitem>
 </itemizedlist>
 You can also use a standalone deriving declaration instead
@@ -4051,6 +4052,260 @@ can be mentioned in the <literal>deriving</literal> clause.
 </para>
 </sect2>
 
+<sect2 id="deriving-functor">
+<title>Deriving <literal>Functor</literal> instances</title>
+
+<para>With <option>-XDeriveFunctor</option>, one can derive
+<literal>Functor</literal> instances for data types of kind
+<literal>* -> *</literal>. For example, this declaration:
+
+<programlisting>
+data Example a = Ex a Char (Example a) (Example Char)
+  deriving Functor
+</programlisting>
+
+would generate the following instance:
+
+<programlisting>
+instance Functor Example where
+  fmap f (Ex a1 a2 a3 a4) = Ex (f a1) a2 (fmap f a3) a4
+</programlisting>
+</para>
+
+<para>The basic algorithm for <option>-XDeriveFunctor</option> walks the
+arguments of each constructor of a data type, applying a mapping function
+depending on the type of each argument. Suppose we are deriving
+<literal>Functor</literal> for a data type whose last type parameter is
+<literal>a</literal>. Then we write the derivation of <literal>fmap</literal>
+code over the type variable <literal>a</literal> for type
+<literal>b</literal> as <literal>$(fmap 'a 'b)</literal>.
+
+<itemizedlist>
+<listitem><para>If the argument's type is <literal>a</literal>, then
+map over it.
+
+<programlisting>
+$(fmap 'a 'a) = f
+</programlisting>
+</para></listitem>
+
+<listitem><para>If the argument's type does not mention <literal>a</literal>,
+then do nothing to it.
+
+<programlisting>
+$(fmap 'a 'b) = \x -> x -- when b does not contain a
+</programlisting>
+</para></listitem>
+
+<listitem><para>If the argument has a tuple type, generate map code for each
+of its arguments.
+
+<programlisting>
+$(fmap 'a '(b1,b2)) = \x -> case x of (x1,x2) -> ($(fmap 'a 'b1) x1, $(fmap 'a 'b2) x2)
+</programlisting>
+</para></listitem>
+
+<listitem><para>If the argument's type is a data type that mentions
+<literal>a</literal>, apply <literal>fmap</literal> to it with the generated
+map code for the data type's last type parameter.
+
+<programlisting>
+$(fmap 'a '(T b1 b2)) = fmap $(fmap 'a 'b2) -- when a only occurs in the last parameter, b2
+</programlisting>
+</para></listitem>
+
+<listitem><para>If the argument has a function type, apply generated
+<literal>$(fmap)</literal> code to the result type, and apply generated
+<literal>$(cofmap)</literal> code to the argument type.
+
+<programlisting>
+$(fmap 'a '(b -> c)) = \x b -> $(fmap 'a' 'c) (x ($(cofmap 'a 'b) b))
+</programlisting>
+
+<literal>$(cofmap)</literal> is needed because the type parameter
+<literal>a</literal> can occur in a contravariant position, which means we
+need to derive a function like:
+
+<programlisting>
+cofmap :: (a -> b) -> f b -> f a
+</programlisting>
+
+This is pretty much the same as <literal>$(fmap)</literal>, only without the
+<literal>$(cofmap 'a 'a)</literal> case:
+
+<programlisting>
+$(cofmap 'a 'b)         = \x -> x     -- when b does not contain a
+$(cofmap 'a 'a)         = error "type variable in contravariant position"
+$(cofmap 'a '(b1,b2))   = \x -> case x of (x1,x2) -> ($(cofmap 'a 'b1) x1, $(cofmap 'a 'b2) x2)
+$(cofmap 'a '[b])       = map $(cofmap 'a 'b)
+$(cofmap 'a '(T b1 b2)) = fmap $(cofmap 'a 'b2) -- when a only occurs in the last parameter, b2
+$(cofmap 'a '(b -> c))  = \x b -> $(cofmap 'a' 'c) (x ($(fmap 'a 'c) b))
+</programlisting>
+
+For more information on contravariance, see
+<ulink url="https://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/DeriveFunctor#Covariantandcontravariantpositions">
+this wiki page</ulink>.
+</para></listitem>
+</itemizedlist>
+</para>
+
+<para>A data type can have a derived <literal>Functor</literal> instance if:
+
+<itemizedlist>
+<listitem><para>It has at least one type parameter.
+</para></listitem>
+
+<listitem><para>It does not use the last type parameter contravariantly.
+</para></listitem>
+
+<listitem><para>It does not use the last type parameter in the "wrong place"
+in any of the argument data types. For example, in:
+
+<programlisting>
+data Right a = Right [a] (Either Int a)
+</programlisting>
+
+the type parameter <literal>a</literal> is only ever used as the last type
+argument in <literal>[]</literal> and <literal>Either</literal>, so both
+<literal>[a]</literal> and <literal>Either Int a</literal> can be
+<literal>fmap</literal>ped. However, in:
+
+<programlisting>
+data Wrong a = Wrong (Either a a)
+</programlisting>
+
+the type variable <literal>a</literal> appears in a position other than the
+last, so trying to <literal>fmap</literal> an <literal>Either a a</literal>
+value would not typecheck in a <literal>Functor</literal> instance.
+
+Note that there are two exceptions to this rule: tuple and function types, as
+described above.
+</para></listitem>
+
+<listitem><para>Its last type variable cannot be used in a
+<option>-XDatatypeContexts</option> constraint.
+</para></listitem>
+
+<listitem><para>Its last type variable cannot be used in an
+<option>-XExistentialQuantification</option> or <option>-XGADTs</option>
+constraint.
+</para></listitem>
+</itemizedlist>
+
+</para>
+</sect2>
+
+<sect2 id="deriving-foldable">
+<title>Deriving <literal>Foldable</literal> instances</title>
+
+<para>With <option>-XDeriveFoldable</option>, one can derive
+<literal>Foldable</literal> instances for data types of kind
+<literal>* -> *</literal>. For example, this declaration:
+
+<programlisting>
+data Example a = Ex a Char (Example a) (Example Char)
+  deriving Functor
+</programlisting>
+
+would generate the following instance:
+
+<programlisting>
+instance Foldable Example where
+  foldr f z (Ex a1 a2 a3 a4) = f a1 (foldr f z a3)
+  foldMap f (Ex a1 a2 a3 a4) = mappend (f a1)
+                                       (mappend mempty
+                                                (mappend (foldMap f a3)
+                                                         mempty))
+</programlisting>
+
+The algorithm for <option>-XDeriveFoldable</option> is very similar to that of
+<option>-XDeriveFunctor</option>, except that <literal>Foldable</literal>
+instances are not possible for function types. The cases are:
+
+<programlisting>
+$(foldr 'a 'b)         = \x z -> z -- when b does not contain a
+$(foldr 'a 'a)         = f
+$(foldr 'a '(b1,b2))   = \x z -> case x of (x1,x2) -> $(foldr 'a 'b1) x1 ( $(foldr 'a 'b2) x2 z )
+$(foldr 'a '(T b1 b2)) = \x z -> foldr $(foldr 'a 'b2) z x -- when a only occurs in the last parameter, b2
+</programlisting>
+
+Another difference between <option>-XDeriveFoldable</option> and
+<option>-XDeriveFunctor</option> is that <option>-XDeriveFoldable</option>
+instances can be derived for data types with existential constraints. For
+example, the following data type:
+
+<programlisting>
+data E a where
+    E1 :: (a ~ Int) =&gt; a   -> E a
+    E2 ::              Int -> E Int
+    E3 :: (a ~ Int) =&gt; a   -> E Int
+    E4 :: (a ~ Int) =&gt; Int -> E a
+
+deriving instance Foldable E
+</programlisting>
+
+would have the following <literal>Foldable</literal> instance:
+
+<programlisting>
+instance Foldable E where
+    foldr f z (E1 e) = f e z
+    foldr f z (E2 e) = z
+    foldr f z (E3 e) = z
+    foldr f z (E4 e) = z
+
+    foldMap f (E1 e) = f e
+    foldMap f (E2 e) = mempty
+    foldMap f (E3 e) = mempty
+    foldMap f (E4 e) = mempty
+</programlisting>
+
+Notice that only the argument in <literal>E1</literal> is folded over. This is
+because we only fold over constructor arguments (1) whose types are
+syntactically equivalent to the last type parameter and (2) when the last type
+parameter is not refined to a specific type. Only <literal>E1</literal>
+satisfies both of these criteria. For more information, see
+<ulink url="https://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/DeriveFunctor">
+this wiki page</ulink>.
+</para>
+</sect2>
+
+<sect2 id="deriving-traversable">
+<title>Deriving <literal>Traversable</literal> instances</title>
+
+<para>With <option>-XDeriveTraversable</option>, one can derive
+<literal>Traversable</literal> instances for data types of kind
+<literal>* -> *</literal>. For example, this declaration:
+
+<programlisting>
+data Example a = Ex a Char (Example a) (Example Char)
+  deriving Functor
+</programlisting>
+
+would generate the following instance:
+
+<programlisting>
+instance Foldable Example where
+  traverse f (Ex a1 a2 a3 a4)
+    = fmap Ex (f a)
+        &lt;*&gt; pure a2
+        &lt;*&gt; traverse f a3
+        &lt;*&gt; pure a4
+</programlisting>
+
+The algorithm for <option>-XDeriveTraversable</option> is very similar to that
+of <option>-XDeriveTraversable</option>, except that
+<literal>Traversable</literal> instances are not possible for function types.
+The cases are:
+
+<programlisting>
+1812   $(traverse 'a 'b)         = pure -- when b does not contain a
+1813   $(traverse 'a 'a)         = f
+1814   $(traverse 'a '(b1,b2))   = \x -> case x of (x1,x2) -> fmap (,) $(traverse 'a 'b1) x1 &lt;*&gt; $(traverse 'a 'b2) x2
+1815   $(traverse 'a '(T b1 b2)) = traverse $(traverse 'a 'b2) -- when a only occurs in the last parameter, b2
+</programlisting>
+</para>
+</sect2>
+
 <sect2 id="deriving-typeable">
 <title>Deriving <literal>Typeable</literal> instances</title>