[Haskell-cafe] Re: Type class help please

[oleg at pobox.com]

> Also, I suspect I'm still missing something important here, for
> example I don't understand why, if it overlaps for [], it doesn't
> overlap with other instances (like Maybe for example). Or am I
> just not getting the error for Maybe because ghc stops after
> the first error?

One may think of instances as denoting sets of types that satisfy them.
For example,
	instance Eq a => Eq [a]
denotes list types, whose elements are themselves members of
Eq. Likewise, Eq (map a) denotes all those types that are constructed
by the application of something to something else. For example, [a], 
Maybe Int, Either a b all satisfy whereas Int does not. Normally
the sets of types denoted by all the instances in a class must be
disjoint. That is, given a type, one can always find an instance it is
a member of -- or fail. 

GHC however checks for overlapping lazily. GHC does not immediately
report that the set of types (i.e., the extension) of one instance is
a proper subset of the extension of another instance in the class. One
should note that if two extensions are identical, this is a duplicate
instance error. If two instance extensions have non-empty overlap but
one does not fully include the other, that is an incurable overlapping
error. GHC reports an error if, during typechecking of an expression,
it tries to find the instance a type is a member of -- and finds two
such instances. If GHC is never prompted to search for instances
for such a type, no error is reported in that particular program.

The original message gives an example of that:

>>> instance (GT map key, Eq a) => Eq (map a) where
>>>   map1 == map2 = assocsAscending map1 == assocsAscending map2
> I don't understand why, but if I use..
>
> -- Instances of GT are instances of Eq --
> instance (GT map key, Eq a) => Eq (map a) where
>   map1 == map2 = True
>
> ..the error goes away.

The function `assocsAscending'  returns the list [(key,a)]
pairs. So, to compile the operation
	assocsAscending map1 == assocsAscending map2
GHC needs to figure out how to compare lists for equality. So, GHC
needs to find an Eq instance that includes the type [(key,a)]. And
there it finds two such instances, Eq [a] and Eq (map a). Hence the
error. GHC is not asked to compare two Maybe values in that code,
hence it does not report overlapping there. Once you define
	   map1 == map2 = True
GHC no longer needs to know how to compare lists -- and so the
overlapping error went away.

Incidentally, Hugs reports the overlapping errors eagerly. It would
still complain about the changed code, because the error is with
instances rather with their use.