Search code examples
haskellderivingvia

Overlapping instances that don't seem to overlap


Consider the following (close to minimal) example:

{-# Language FlexibleInstances #-}

class Predicate a where
    test :: a -> Bool

instance (Predicate a, Traversable t) => Predicate (t a) where
    test = all test

data Bar = Bar
instance Predicate Bar where
    test Bar = False

data Baz a = Baz a
instance Predicate a => Predicate (Baz a) where
    test (Baz x) = test x

main :: IO ()
main = print $ test $ Baz Bar

Looking at test $ Baz Bar, you'd expect a result of False, as we have the instances Predicate Bar and Predicate a => Predicate (Baz a).

But GHC 8.6.3 and 8.0.1 both reject this:

test.hs:18:16: error:
    • Overlapping instances for Predicate (Baz Bar)
        arising from a use of ‘test’
      Matching instances:
        instance (Predicate a, Traversable t) => Predicate (t a)
          -- Defined at test.hs:6:10
        instance Predicate a => Predicate (Baz a)
          -- Defined at test.hs:14:10
    • In the second argument of ‘($)’, namely ‘test $ Baz Bar’
      In the expression: print $ test $ Baz Bar
      In an equation for ‘main’: main = print $ test $ Baz Bar
   |
18 | main = print $ test $ Baz Bar
   |                ^^^^^^^^^^^^^^

And yet there's no overlap: we can confirm there's no instance of Traversable Baz by commenting out the Predicate (Baz a) instance, in which case we get the error:

test.hs:18:16: error:
    • No instance for (Traversable Baz) arising from a use of ‘test’
    • In the second argument of ‘($)’, namely ‘test $ Baz Bar’
      In the expression: print $ test $ Baz Bar
      In an equation for ‘main’: main = print $ test $ Baz Bar
   |
18 | main = print $ test $ Baz Bar
   |                ^^^^^^^^^^^^^^

I'm assuming this is a limitation of FlexibleInstances? If so, why, and is there an approved workaround?


Okay, turns out this is a consequence of GHC deciding on which instance to use independently of the constraints on the instance, as described here. That trick doesn't seem to work here though:

instance (b ~ Baz, Predicate a) => Predicate (b a) where

Gives a Duplicate instance declarations error, so I'm leaving the question open for a solution that works in this case.


Solution

  • The problem is that those instance indeed overlap, since the instance resolution mechanism only looks at the instance head when deciding which instance to take, and only later, after an instance has been chosen, it checks the constraints to see that it is met (and otherwise throws and error).

    I suggest reading the documentation on instance resolution

    One way to fix your problem (other than redesigning your solution, which is probably the right thing to do), is to tell GHC that a certain instance is "less important" (or overlappable).
    This basically means that GHC will choose a more specific instance if it's available (what more specific means you can read in the documentation linked above).
    This is achieved by using the pragma {-# OVERLAPPABLE #-} or {-# OVERLAPS #-} (read the documentation to see the difference, basically the former is more specific).

    The resulting code would look something like this

    {-# Language FlexibleInstances #-}
    
    class Predicate a where
        test :: a -> Bool
    
    instance {-# OVERLAPPABLE #-} (Predicate a, Traversable t) => Predicate (t a) where
        test = all test
    
    data Bar = Bar
    instance Predicate Bar where
        test Bar = False
    
    data Baz a = Baz a
    instance Predicate a => Predicate (Baz a) where
        test (Baz x) = test x
    
    main :: IO ()
    main = do
       print . test $ Baz Bar
       print . test $ ([] :: [Bar])
       print . test $ [Bar]
       print . test $ Baz ([] :: [Bar])
    

    And the result from running it is

    False
    True
    False
    True
    

    as expected.