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.
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.