-To start with an abstract example, consider a declaration such as:
-<programlisting>
- class C a b where ...
-</programlisting>
-which tells us simply that C can be thought of as a binary relation on types
-(or type constructors, depending on the kinds of a and b). Extra clauses can be
-included in the definition of classes to add information about dependencies
-between parameters, as in the following examples:
-<programlisting>
- class D a b | a -> b where ...
- class E a b | a -> b, b -> a where ...
-</programlisting>
-The notation <literal>a -> b</literal> used here between the | and where
-symbols --- not to be
-confused with a function type --- indicates that the a parameter uniquely
-determines the b parameter, and might be read as "a determines b." Thus D is
-not just a relation, but actually a (partial) function. Similarly, from the two
-dependencies that are included in the definition of E, we can see that E
-represents a (partial) one-one mapping between types.
-</para>
-<para>
-More generally, dependencies take the form <literal>x1 ... xn -> y1 ... ym</literal>,
-where x1, ..., xn, and y1, ..., yn are type variables with n>0 and
-m>=0, meaning that the y parameters are uniquely determined by the x
-parameters. Spaces can be used as separators if more than one variable appears
-on any single side of a dependency, as in <literal>t -> a b</literal>. Note that a class may be
-annotated with multiple dependencies using commas as separators, as in the
-definition of E above. Some dependencies that we can write in this notation are
-redundant, and will be rejected because they don't serve any useful
-purpose, and may instead indicate an error in the program. Examples of
-dependencies like this include <literal>a -> a </literal>,
-<literal>a -> a a </literal>,
-<literal>a -> </literal>, etc. There can also be
-some redundancy if multiple dependencies are given, as in
-<literal>a->b</literal>,
- <literal>b->c </literal>, <literal>a->c </literal>, and
-in which some subset implies the remaining dependencies. Examples like this are
-not treated as errors. Note that dependencies appear only in class
-declarations, and not in any other part of the language. In particular, the
-syntax for instance declarations, class constraints, and types is completely
-unchanged.
-</para>
-<para>
-By including dependencies in a class declaration, we provide a mechanism for
-the programmer to specify each multiple parameter class more precisely. The
-compiler, on the other hand, is responsible for ensuring that the set of
-instances that are in scope at any given point in the program is consistent
-with any declared dependencies. For example, the following pair of instance
-declarations cannot appear together in the same scope because they violate the
-dependency for D, even though either one on its own would be acceptable:
-<programlisting>
- instance D Bool Int where ...
- instance D Bool Char where ...
-</programlisting>
-Note also that the following declaration is not allowed, even by itself:
-<programlisting>
- instance D [a] b where ...
-</programlisting>
-The problem here is that this instance would allow one particular choice of [a]
-to be associated with more than one choice for b, which contradicts the
-dependency specified in the definition of D. More generally, this means that,
-in any instance of the form:
-<programlisting>
- instance D t s where ...
-</programlisting>
-for some particular types t and s, the only variables that can appear in s are
-the ones that appear in t, and hence, if the type t is known, then s will be
-uniquely determined.
-</para>
-<para>
-The benefit of including dependency information is that it allows us to define
-more general multiple parameter classes, without ambiguity problems, and with
-the benefit of more accurate types. To illustrate this, we return to the
-collection class example, and annotate the original definition of <literal>Collects</literal>
-with a simple dependency:
-<programlisting>
- class Collects e ce | ce -> e where
- empty :: ce
- insert :: e -> ce -> ce
- member :: e -> ce -> Bool
-</programlisting>
-The dependency <literal>ce -> e</literal> here specifies that the type e of elements is uniquely
-determined by the type of the collection ce. Note that both parameters of
-Collects are of kind *; there are no constructor classes here. Note too that
-all of the instances of Collects that we gave earlier can be used
-together with this new definition.
-</para>
-<para>
-What about the ambiguity problems that we encountered with the original
-definition? The empty function still has type Collects e ce => ce, but it is no
-longer necessary to regard that as an ambiguous type: Although the variable e
-does not appear on the right of the => symbol, the dependency for class
-Collects tells us that it is uniquely determined by ce, which does appear on
-the right of the => symbol. Hence the context in which empty is used can still
-give enough information to determine types for both ce and e, without
-ambiguity. More generally, we need only regard a type as ambiguous if it
-contains a variable on the left of the => that is not uniquely determined
-(either directly or indirectly) by the variables on the right.
-</para>
-<para>
-Dependencies also help to produce more accurate types for user defined
-functions, and hence to provide earlier detection of errors, and less cluttered
-types for programmers to work with. Recall the previous definition for a
-function f:
-<programlisting>
- f x y = insert x y = insert x . insert y
-</programlisting>
-for which we originally obtained a type: