haskell - `data PoE a = Empty | Pair a a` 是单子(monad)吗？

Question

这个问题来自这个答案
example of a functor that is Applicative but not a Monad :
据称，该

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

不能有一个单子(monad)实例，但我看不到:

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

我认为这是一个 monad 的真正原因是它与 Maybe (Pair a) 同构。与 Pair a = P a a .它们都是 monad，都是可遍历的，所以它们的组合也应该形成一个 monad。 Oh, I just found out not always .

哪个反例不符合哪个单子(monad)定律？ (以及如何系统地找出它？)

编辑:我没想到对这个问题有这么大的兴趣。现在，我必须下定决心，是否接受“系统地”部分的最佳示例或最佳答案。

同时，我想形象化 join适用于更简单的 Pair a = P a a :

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

它总是采用外部路径，产生 P 1 4 ，通常称为矩阵表示中的对角线。对于 monad 关联我需要三个维度，树可视化效果更好。取自 chi 的回答，这是 join 的失败示例，以及我如何理解它。

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

现在你做 join . fmap join通过首先折叠较低的级别，对于 join . join从根本上崩溃。

Answer 1

显然，它不是一个单子(monad)。单子(monad)“join”法则之一是

join . join = join . fmap join

因此，根据上述定律，这两个输出应该相等，但事实并非如此。

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

问题是

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

执行额外的 join那些并不使他们平等。

how to find that out systematically?

join . join有类型 m (m (m a)) -> m (m a) ，所以我从三重嵌套 Pair 开始-的- Pair -的- Pair , 使用数字 1..8 .那工作得很好。然后，我尝试插入一些 Empty里面，很快就找到了上面的反例。

这种方法是可能的，因为 m (m (m Int))里面只包含有限数量的整数，我们只有构造函数 Pair和 Empty尝试。

对于这些检查，我找到 join比 >>= 的关联性更容易测试的定律.