Is `data PoE a = Empty | Pair a a` a monad?

Question

This question comes from this answer in example of a functor that is Applicative but not a Monad: It is claimed that the

data PoE a = Empty | Pair a a deriving (Functor,Eq)

cannot have a monad instance, but I fail to see that with:

instance Applicative PoE where
    pure x = Pair x x
    Pair f g <*> Pair x y = Pair (f x) (g y)
    _        <*> _        = Empty
instance Monad PoE where
    Empty    >>= _ = Empty
    Pair x y >>= f = case (f x, f y) of 
                       (Pair x' _,Pair _ y') -> Pair x' y'
                       _ -> Empty

The actual reason why I believe this to be a monad is that it is isomorphic to Maybe (Pair a) with Pair a = P a a. They are both monads, both traversables so their composition should form a monad, too. Oh, I just found out not always.

Which counter-example failes which monad law? (and how to find that out systematically?)

---

edit: I did not expect such an interest in this question. Now I have to make up my mind if I accept the best example or the best answer to the "systematically" part.

Meanwhile, I want to visualize how join works for the simpler Pair a = P a a:

                   P
          ________/ \________
         /                   \
        P                     P
       / \                   / \
      1   2                 3   4

it always take the outer path, yielding P 1 4, more commonly known as a diagonal in a matrix representation. For monad associativy I need three dimensions, a tree visualization works better. Taken from chi's answer, this is the failing example for join, and how I can comprehend it.

                  Pair
          _________/\_________
         /                    \
       Pair                   Pair
        /\                     /\
       /  \                   /  \
    Pair  Empty           Empty  Pair
     /\                           /\
    1  2                         3  4

Now you do the join . fmap join by collapsing the lower levels first, for join . join collapse from the root.

Answer 1

Apparently, it is not a monad. One of the monad "join" laws is

join . join = join . fmap join

Hence, according to the law above, these two outputs should be equal, but they are not.

main :: IO ()
main = do
  let x = Pair (Pair (Pair 1 2) Empty) (Pair Empty (Pair 7 8))
  print (join . join $ x)
  -- output: Pair 1 8
  print (join . fmap join $ x)
  -- output: Empty

The problem is that

join x      = Pair (Pair 1 2) (Pair 7 8)
fmap join x = Pair Empty Empty

Performing an additional join on those does not make them equal.

how to find that out systematically?

join . join has type m (m (m a)) -> m (m a), so I started with a triple-nested Pair-of-Pair-of-Pair, using numbers 1..8. That worked fine. Then, I tried to insert some Empty inside, and quickly found the counterexample above.

This approach was possible since a m (m (m Int)) only contains a finite amount of integers inside, and we only have constructors Pair and Empty to try.

For these checks, I find the join law easier to test than, say, associativity of >>=.