[Haskell-cafe] Instances that shouldn't overlap

[Miguel Mitrofanov]

Maybe it'd be more intuitive if written backwards:

AppEq f a <= (Applicative f, Eq a)

or even

AppEq f a => (Applicative f, Eq a)

On 27 Nov 2008, at 00:39, Ryan Ingram wrote:

> A common mistake (and a confusing bit about typeclasses) is that
> whether or not the constraints on an instance apply are irrelevant.
>
> Specifically, the code "instance (Applicative f, Eq a) => AppEq f a"
> means that, given any types f and a, I can tell you how to make them
> an instance of AppEq.  But I also ask you to please add the
> constraints "Applicative f" and "Eq a".  That is to say, only the
> stuff on the right of the => apply when determining whether an
> instance applies.
>
> If you take out the overlapping specific instance for Interval, the
> compiler will give you a different error:
>
> "No instance for Applicative Interval".  You can see what happened
> here: the compiler wants an instance for AppEq Interval Integer.  It
> sees the instance "AppEq f a" and adds the constraints "Ord Integer"
> and "Applicative Interval".  Ord Integer is already fulfilled, but it
> can't discharge the constraint on Applicative, so the compile fails.
>
> Similarily, in your case, the compiler can't decide whether to apply
> the "Ord a => AppEq Interval a" instance, or the "Applicative f, Eq a
> => AppEq f a" instance; the right hand sides of the instance
> declarations both match (and add different constraints to the left
> hand side).
>
> You can use -XOverlappingInstances, but beware, dragons lie in that  
> direction.
>
> I think this is a fundamental weakness of the typeclass system, but I
> haven't seen a design that avoids it for code as complicated as this.
>
> On Wed, Nov 26, 2008 at 12:05 PM, Paul Johnson <paul at cogito.org.uk>  
> wrote:
>> Hi,
>>
>> I'm trying to set up some operators for applicative versions of  
>> prelude
>> types.  For instance:
>>
>> -- | Applicative Equality.
>> class (Eq a) => AppEq f a where
>> (.==.), (./=.) :: f a -> f a -> f Bool
>>
>> instance (Applicative f, Eq a) => AppEq f a where
>> (.==.)  = liftA2 (==)
>> (./=.)  = liftA2 (/=)
>>
>>
>> Hopefully the intention is fairly straightforward: if "f" is an  
>> instance of
>> Applicative then the lifted implementation of the underlying type.
>> Otherwise I can just give my own instance, which is useful for  
>> things that
>> "wrap" prelude types but where "fmap" doesn't work.  For instance:
>>
>> data (Ord a) => Interval a = Interval a a
>>
>> instance (Ord a) => AppEq Interval a where
>> i1@(Interval _ u1) .==. i2@(Interval _ u2)
>>    | isSingleton i1 && isSingleton i2 && u1 == u2  = Interval True  
>> True
>>    | has i1 u2 || has i2 u1                        = Interval False  
>> True
>>    | otherwise                                     = Interval False  
>> False
>> i1 ./=. i2 = let Interval b1 b2 = (i1 .==. i2) in Interval (not b2)  
>> (not
>> b1)
>>
>> isSingleton :: (Ord a) => Interval a -> Bool
>> isSingleton (Interval lower upper) = lower == upper
>>
>> has :: (Ord a) => Interval a -> a -> Bool
>> has (Interval lower upper) v = v >= lower && v <= upper
>>
>>
>> You can't (easily) define fmap for Interval because the function  
>> given as an
>> argument might not be monotonic.  So instead you have to write custom
>> implementations for each lifted function, as shown here for (.==.)  
>> and
>> (./=.) .  The same principle works for AppOrd, AppNum etc, but I'm  
>> trying to
>> solve the problem for just AppEq for now.
>>
>> This compiles, but when I try to use it I get this in ghci:
>>
>> *Interval> let i1 = Interval 4 5
>> *Interval> let i2 = Interval 4 6
>> *Interval> i1 .==. i2
>>
>> <interactive>:1:0:
>> Overlapping instances for AppEq Interval Integer
>>   arising from a use of `.==.' at <interactive>:1:0-9
>> Matching instances:
>>   instance (Ord a) => AppEq Interval a
>>     -- Defined at Interval.hs:(22,0)-(27,78)
>>   instance (Control.Applicative.Applicative f, Eq a) => AppEq f a
>>     -- Defined at AppPrelude.hs:(32,0)-(34,23)
>> In the expression: i1 .==. i2
>> In the definition of `it': it = i1 .==. i2
>>
>> I'm puzzled, because Interval is not an instance of Applicative, so  
>> the
>> second instance doesn't apply.  Can anyone help me out?
>>
>> I'm using ghc 6.8.3, so its possible that this was a bug fixed in  
>> 6.10.
>>
>> Paul.
>> _______________________________________________
>> Haskell-Cafe mailing list
>> Haskell-Cafe at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe