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.