-For each assertion in the context:
-<orderedlist>
-<listitem><para>No type variable has more occurrences in the assertion than in the head</para></listitem>
-<listitem><para>The assertion has fewer constructors and variables (taken together
- and counting repetitions) than the head</para></listitem>
-</orderedlist>
-</para></listitem>
-
-<listitem><para>The coverage condition. For each functional dependency,
-<replaceable>tvs</replaceable><subscript>left</subscript> <literal>-></literal>
-<replaceable>tvs</replaceable><subscript>right</subscript>, of the class,
-every type variable in
-S(<replaceable>tvs</replaceable><subscript>right</subscript>) must appear in
-S(<replaceable>tvs</replaceable><subscript>left</subscript>), where S is the
-substitution mapping each type variable in the class declaration to the
-corresponding type in the instance declaration.
-</para></listitem>
-</orderedlist>
-These restrictions ensure that context reduction terminates: each reduction
-step makes the problem smaller by at least one
-constructor. For example, the following would make the type checker
-loop if it wasn't excluded:
-<programlisting>
- instance C a => C a where ...
-</programlisting>
-For example, these are OK:
-<programlisting>
- instance C Int [a] -- Multiple parameters
- instance Eq (S [a]) -- Structured type in head
-
- -- Repeated type variable in head
- instance C4 a a => C4 [a] [a]
- instance Stateful (ST s) (MutVar s)
-
- -- Head can consist of type variables only
- instance C a
- instance (Eq a, Show b) => C2 a b
-
- -- Non-type variables in context
- instance Show (s a) => Show (Sized s a)
- instance C2 Int a => C3 Bool [a]
- instance C2 Int a => C3 [a] b
-</programlisting>
-But these are not:
-<programlisting>
- -- Context assertion no smaller than head
- instance C a => C a where ...
- -- (C b b) has more more occurrences of b than the head
- instance C b b => Foo [b] where ...
-</programlisting>
-</para>
-
-<para>
-The same restrictions apply to instances generated by
-<literal>deriving</literal> clauses. Thus the following is accepted:
-<programlisting>
- data MinHeap h a = H a (h a)
- deriving (Show)
-</programlisting>
-because the derived instance
-<programlisting>
- instance (Show a, Show (h a)) => Show (MinHeap h a)
-</programlisting>
-conforms to the above rules.
-</para>
-
-<para>
-A useful idiom permitted by the above rules is as follows.
-If one allows overlapping instance declarations then it's quite
-convenient to have a "default instance" declaration that applies if
-something more specific does not:
-<programlisting>
- instance C a where
- op = ... -- Default
-</programlisting>
-</para>
-<para>You can find lots of background material about the reason for these
-restrictions in the paper <ulink
-url="http://research.microsoft.com/%7Esimonpj/papers/fd%2Dchr/">
-Understanding functional dependencies via Constraint Handling Rules</ulink>.
-</para>
-</sect3>
-
-<sect3 id="undecidable-instances">
-<title>Undecidable instances</title>
-
-<para>
-Sometimes even the rules of <xref linkend="instance-rules"/> are too onerous.
-For example, sometimes you might want to use the following to get the
-effect of a "class synonym":
-<programlisting>
- class (C1 a, C2 a, C3 a) => C a where { }
-
- instance (C1 a, C2 a, C3 a) => C a where { }
-</programlisting>
-This allows you to write shorter signatures:
-<programlisting>
- f :: C a => ...
-</programlisting>
-instead of
-<programlisting>
- f :: (C1 a, C2 a, C3 a) => ...
-</programlisting>
-The restrictions on functional dependencies (<xref
-linkend="functional-dependencies"/>) are particularly troublesome.
-It is tempting to introduce type variables in the context that do not appear in
-the head, something that is excluded by the normal rules. For example:
-<programlisting>
- class HasConverter a b | a -> b where
- convert :: a -> b
-
- data Foo a = MkFoo a
-
- instance (HasConverter a b,Show b) => Show (Foo a) where
- show (MkFoo value) = show (convert value)
-</programlisting>
-This is dangerous territory, however. Here, for example, is a program that would make the
-typechecker loop:
-<programlisting>
- class D a
- class F a b | a->b
- instance F [a] [[a]]
- instance (D c, F a c) => D [a] -- 'c' is not mentioned in the head
-</programlisting>
-Similarly, it can be tempting to lift the coverage condition:
-<programlisting>
- class Mul a b c | a b -> c where
- (.*.) :: a -> b -> c
-
- instance Mul Int Int Int where (.*.) = (*)
- instance Mul Int Float Float where x .*. y = fromIntegral x * y
- instance Mul a b c => Mul a [b] [c] where x .*. v = map (x.*.) v
-</programlisting>
-The third instance declaration does not obey the coverage condition;
-and indeed the (somewhat strange) definition:
-<programlisting>
- f = \ b x y -> if b then x .*. [y] else y
-</programlisting>
-makes instance inference go into a loop, because it requires the constraint
-<literal>(Mul a [b] b)</literal>.
-</para>
-<para>
-Nevertheless, GHC allows you to experiment with more liberal rules. If you use
-the experimental flag <option>-fallow-undecidable-instances</option>
-<indexterm><primary>-fallow-undecidable-instances
-option</primary></indexterm>, you can use arbitrary
-types in both an instance context and instance head. Termination is ensured by having a
-fixed-depth recursion stack. If you exceed the stack depth you get a
-sort of backtrace, and the opportunity to increase the stack depth
-with <option>-fcontext-stack=</option><emphasis>N</emphasis>.
-</para>
-
-</sect3>
-
-
-<sect3 id="instance-overlap">
-<title>Overlapping instances</title>
-<para>
-In general, <emphasis>GHC requires that that it be unambiguous which instance
-declaration
-should be used to resolve a type-class constraint</emphasis>. This behaviour
-can be modified by two flags: <option>-fallow-overlapping-instances</option>
-<indexterm><primary>-fallow-overlapping-instances
-</primary></indexterm>
-and <option>-fallow-incoherent-instances</option>
-<indexterm><primary>-fallow-incoherent-instances
-</primary></indexterm>, as this section discusses. Both these
-flags are dynamic flags, and can be set on a per-module basis, using
-an <literal>OPTIONS_GHC</literal> pragma if desired (<xref linkend="source-file-options"/>).</para>
-<para>
-When GHC tries to resolve, say, the constraint <literal>C Int Bool</literal>,
-it tries to match every instance declaration against the
-constraint,
-by instantiating the head of the instance declaration. For example, consider
-these declarations:
-<programlisting>
- instance context1 => C Int a where ... -- (A)
- instance context2 => C a Bool where ... -- (B)
- instance context3 => C Int [a] where ... -- (C)
- instance context4 => C Int [Int] where ... -- (D)
-</programlisting>
-The instances (A) and (B) match the constraint <literal>C Int Bool</literal>,
-but (C) and (D) do not. When matching, GHC takes
-no account of the context of the instance declaration
-(<literal>context1</literal> etc).
-GHC's default behaviour is that <emphasis>exactly one instance must match the
-constraint it is trying to resolve</emphasis>.
-It is fine for there to be a <emphasis>potential</emphasis> of overlap (by
-including both declarations (A) and (B), say); an error is only reported if a
-particular constraint matches more than one.
-</para>
-
-<para>
-The <option>-fallow-overlapping-instances</option> flag instructs GHC to allow
-more than one instance to match, provided there is a most specific one. For
-example, the constraint <literal>C Int [Int]</literal> matches instances (A),
-(C) and (D), but the last is more specific, and hence is chosen. If there is no
-most-specific match, the program is rejected.
-</para>
-<para>
-However, GHC is conservative about committing to an overlapping instance. For example:
-<programlisting>
- f :: [b] -> [b]
- f x = ...
-</programlisting>
-Suppose that from the RHS of <literal>f</literal> we get the constraint
-<literal>C Int [b]</literal>. But
-GHC does not commit to instance (C), because in a particular
-call of <literal>f</literal>, <literal>b</literal> might be instantiate
-to <literal>Int</literal>, in which case instance (D) would be more specific still.
-So GHC rejects the program. If you add the flag <option>-fallow-incoherent-instances</option>,
-GHC will instead pick (C), without complaining about
-the problem of subsequent instantiations.
-</para>
-<para>
-The willingness to be overlapped or incoherent is a property of
-the <emphasis>instance declaration</emphasis> itself, controlled by the
-presence or otherwise of the <option>-fallow-overlapping-instances</option>
-and <option>-fallow-incoherent-instances</option> flags when that mdodule is
-being defined. Neither flag is required in a module that imports and uses the
-instance declaration. Specifically, during the lookup process:
-<itemizedlist>