Overlapping instances that don't seem to overlap

Question

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.

Answer 1

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.

Answer 2

With DerivingVia you can give this behaviour to a newtype

type    Every :: (k -> Type) -> k -> Type
newtype Every t a = Every (t a)
  deriving
  stock Foldable

-- Foldable is sufficient
instance (Foldable t, Predicate a) => Predicate (Every t a) where
  test :: Every t a -> Bool
  test = all test

and derive Predicate via it, this is preferable to an overlapping instance like you have given.

{-# Language DerivingVia #-}

type Tree :: Type -> Type
data Tree a = Leaf a | Branch (Tree a) (Tree a)
  deriving
  stock Foldable

  deriving Predicate
  via Every Tree a

This opens the possibility for alternative definitions

type    Some :: (k -> Type) -> k -> Type
newtype Some t a = Some (t a)
  deriving
  stock Foldable

-- This derives alternative behaviour, here using `any' in lieu of `all' 
instance (Foldable t, Predicate a) => Predicate (Some t a) where
  test :: Some t a -> Bool
  test = any test

Just like the Ap f a newtype is a better solution than defining instances that are incompatible with Monoid [a] and other common instances.

instance (Applicative f, Semigroup a) => Semigroup (f a) where
  (<>) :: f a -> f a -> f a
  (<>) = liftA2 (<>)

instance (Applicative f, Monoid a) => Monoid (f a) where
  mempty :: f a
  mempty = pure mempty