`data PoE a = Empty | Pair a a`能否构成Monad实例？

嘿，咱们来好好捋一捋你写的这个PoE类型的Monad实例到底合不合法。首先先把你定义的代码贴出来，方便对照：

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

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

很多人说PoE没法成为Monad，但你这个实例看起来有模有样，那关键就是要验证它是否满足Monad的三大定律，同时还要确保它和已有的Applicative实例兼容（因为Monad是Applicative的扩展，必须满足一致性）。

一、验证Monad定律 #

1. 左单位律：pure x >>= f ≡ f x #

• 当f x是Pair a b时：
  左边pure x >>= f展开为Pair x x >>= f，匹配case (f x, f x)也就是(Pair a b, Pair a b)，结果是Pair a b，和右边f x完全相等。
• 当f x是Empty时：
  左边pure x >>= f会进入case的_ -> Empty分支，结果是Empty，和右边f x一致。
  左单位律成立。

2. 右单位律：m >>= pure ≡ m #

• 当m是Empty时：左边直接返回Empty，和m相等。
• 当m是Pair x y时：
  左边展开为case (pure x, pure y)，pure x是Pair x x，pure y是Pair y y，匹配分支后结果是Pair x y，和m完全一致。
  右单位律成立。

3. 结合律：(m >>= f) >>= g ≡ m >>= (\x -> f x >>= g) #

我们可以通过具体例子验证：
假设：

m = Pair 1 2
f x = Pair x (x + 10)
g x = Pair (x * 100) (x * 200)

• 左边计算：(Pair 1 2 >>= f) >>= g
  • Pair 1 2 >>= f → case (f 1, f 2) → (Pair 1 11, Pair 2 12) → 结果Pair 1 12
  • Pair 1 12 >>= g → case (g 1, g 12) → (Pair 100 200, Pair 1200 2400) → 结果Pair 100 2400
• 右边计算：Pair 1 2 >>= (\x -> f x >>= g)
  • 先算\x -> f x >>= g：
    • x=1时：f 1 >>= g → case (g 1, g 11) → (Pair 100 200, Pair 1100 2200) → 结果Pair 100 2200
    • x=2时：f 2 >>= g → case (g 2, g 12) → (Pair 200 400, Pair 1200 2400) → 结果Pair 200 2400
  • 再算Pair 1 2 >>= 上述函数 → case (Pair 100 2200, Pair 200 2400) → 结果Pair 100 2400
    左右两边结果一致，结合律成立。

二、验证与Applicative的兼容性 #

Monad作为Applicative的扩展，必须满足：(<*>) ≡ ap（其中ap f x = f >>= \f' -> x >>= \x' -> pure (f' x')）。我们用例子验证：
取f = Pair (+1) (*2)，x = Pair 3 4：

• Applicative的<*>结果：Pair ((+1) 3) ((*2) 4) = Pair 4 8
• Monad的ap结果：

  ap f x = Pair (+1) (*2) >>= \f' -> Pair 3 4 >>= \x' -> pure (f' x')
  

  内层Pair 3 4 >>= \x' -> pure (f' x')对每个f'返回Pair (f' 3) (f' 4)，所以外层展开为case (Pair 4 5, Pair 6 8) → 结果Pair 4 8
  两者完全一致，兼容性满足。

结论 #

你写的这个PoE的Monad实例是完全合法的，它满足Monad的三大定律，并且和给定的Applicative实例兼容。之前有人声称它无法拥有Monad实例，可能是基于对Pair行为的直觉预期（比如认为Pair x y >>= f应该合并两个f结果的其他组合），但从纯代数的角度，只要满足定律，就是有效的Monad实例。

内容的提问来源于stack exchange，提问作者Franky