Adrian Hey wrote:
-- Instances of GT are instances of Eq -- instance (GT map key, Eq a) => Eq (map a) where map1 == map2 = assocsAscending map1 == assocsAscending map2 ... Overlapping instances for Eq [(key, a)] arising from use of `==' at Test.hs:10:16-59 Matching instances: instance (Eq a) => Eq [a] -- Defined in GHC.Base instance (GT map key, Eq a) => Eq (map a) -- Defined at Test.hs:9:0
How can my new instance overlap with the old (ghc) instance unless [] is also an instance of GT for some key type (which it isn't). Could someone explain?
You are right in your explanation of the GHC behavior. Your instance |Eq (map a)| indeed overlaps the `standard` instance |Eq [a]|. The overlap may be easier to see if we write [a] as ([] a), which is what it is, an application of the type constructor [] to the type variable a. So, the type [a] (aka [] a) is a particular instance of the type (map a), with `map' being []. This is the overlapping that GHC is complaining about. Regarding the need for -fallow-undecidable-instance: GHC is not a general purpose termination checker. Furthermore, it seems reasonable for GHC to employ simple termination heuristics, which can be decided quickly, syntactically and locally (that is, considering only the instance in question, rather than collection of all instances in the program). Thus GHC employs a set of heuristics that look if the instance constraints are `smaller' than the instance head. That will assure termination. That criterion is of course not complete, so there are (many) terminating, decidable typeclass program that fail simple GHC termination tests and thus require -fallow-undecidable-instance extension. One method of avoiding overlapping instances is to define a newtype wrapper: newtype MyMap map a = MyMap{unMyMap::map a} class Ord key => GT map key | map -> key where assocsAscending :: map a -> [(key,a)] -- Just 1 of many methods instance GT (MyMap Data.IntMap) Int where ... The drawback is writing MyMap and unMyMap in many places. That spoils the appearance, but rarely fatal. Another solution is replacing the general instance instance (GT map key, Eq a) => Eq (map a) where map1 == map2 = assocsAscending map1 == assocsAscending map2 with its instantiations, for all `maps' in question: instance Eq a => Eq (Data.IntMap a) where ... instance Eq a => Eq (Data.Map key a) where ... instance Eq a => Eq (Data.IntSet a) where ...
oleg@pobox.com wrote:
Adrian Hey wrote:
-- Instances of GT are instances of Eq -- instance (GT map key, Eq a) => Eq (map a) where map1 == map2 = assocsAscending map1 == assocsAscending map2 ... Overlapping instances for Eq [(key, a)] arising from use of `==' at Test.hs:10:16-59 Matching instances: instance (Eq a) => Eq [a] -- Defined in GHC.Base instance (GT map key, Eq a) => Eq (map a) -- Defined at Test.hs:9:0
How can my new instance overlap with the old (ghc) instance unless [] is also an instance of GT for some key type (which it isn't). Could someone explain?
You are right in your explanation of the GHC behavior. Your instance |Eq (map a)| indeed overlaps the `standard` instance |Eq [a]|. The overlap may be easier to see if we write [a] as ([] a), which is what it is, an application of the type constructor [] to the type variable a. So, the type [a] (aka [] a) is a particular instance of the type (map a), with `map' being []. This is the overlapping that GHC is complaining about.
So if I understand correctly, it's complaining about a potential overlap, not an actual overlap (there is no actual overlap until [] is made an instance of GT AFAICS). 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?
Another solution is replacing the general instance instance (GT map key, Eq a) => Eq (map a) where map1 == map2 = assocsAscending map1 == assocsAscending map2
with its instantiations, for all `maps' in question: instance Eq a => Eq (Data.IntMap a) where ... instance Eq a => Eq (Data.Map key a) where ... instance Eq a => Eq (Data.IntSet a) where ...
This seems like the more attractive option if my current approach is unworkable, but it seems strange that I should have to do this. Thanks -- Adrian Hey
Adrian Hey wrote:
oleg@pobox.com wrote:
Adrian Hey wrote:
-- Instances of GT are instances of Eq -- instance (GT map key, Eq a) => Eq (map a) where map1 == map2 = assocsAscending map1 == assocsAscending map2 ... Overlapping instances for Eq [(key, a)] arising from use of `==' at Test.hs:10:16-59 Matching instances: instance (Eq a) => Eq [a] -- Defined in GHC.Base instance (GT map key, Eq a) => Eq (map a) -- Defined at Test.hs:9:0
How can my new instance overlap with the old (ghc) instance unless [] is also an instance of GT for some key type (which it isn't). Could someone explain?
You are right in your explanation of the GHC behavior. Your instance |Eq (map a)| indeed overlaps the `standard` instance |Eq [a]|. The overlap may be easier to see if we write [a] as ([] a), which is what it is, an application of the type constructor [] to the type variable a. So, the type [a] (aka [] a) is a particular instance of the type (map a), with `map' being []. This is the overlapping that GHC is complaining about.
So if I understand correctly, it's complaining about a potential overlap, not an actual overlap (there is no actual overlap until [] is made an instance of GT AFAICS).
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?
Ah, this brings me to something else I don't quite understand about this error, but kind of explains the absence of similar errors for Maybe. It's the "arising from use of `==' at Test.hs:10:16-59" part. 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. So it's not objecting to such instances in general, but rather the specific use of == in the definition. So now I'm really confused. Why, if it's possible that this instance overlaps with another for [], does it make any difference whether or not I've used == in the definition? Surely, if there's any ambiguity about which instance of Eq to use for [] (should [] be made an instance of GT), then the ambiguity exists whether or not I've used == in the definition. Hmm.. Regards -- Adrian Hey
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.
oleg@pobox.com wrote:
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.
Thankyou for your patience. I think I'm getting what's going on now. The flags that allow undecidable or overlapping instances don't really mean quite what they say for complete programs (I was wondering how they could :-), but actually mean don't reject modules if it cannot be (easily) be proven that that they are decidable and non-overlapping at the time that module is compiled. Instead you may get some kind of error later on (if it turns out the instances really are undecidable or overlapping). Hence the error, despite [] not being an instance of GT. (Hope I've got that right now). Of course the code I posted is a gross over-simplification of the real code I'm trying to compile, and though using these flags seems to work for this simple module I still get errors for my real code, (haven't quite figured out why yet) which made me wonder if I was doing something wrong that required the use of these flags in the first place. I think I'll try the approach you suggested of doing this for individual GT types and see how I get on. Actually this shouldn't be too bad in my case as the intention is to have GT types and the corresponding GT instances generated automatically in the longer term. Thanks -- Adrian Hey
participants (2)
-
Adrian Hey -
oleg＠pobox.com