为什么 AccValidation 不能有 Monad 实例？

Question

来自 validation 包的文档：

The AccValidation data type is isomorphic to Either, but has an instance of Applicative that accumulates on the error side. That is to say, if two (or more) errors are encountered, they are appended using a Semigroup operation.

As a consequence of this Applicative instance, there is no corresponding Bind or Monad instance. AccValidation is an example of, "An applicative functor that is not a monad."

我不清楚为什么会这样。我可以想象 AccValidation 的 Monad 实例的行为类似于 Either - 什么会导致这种行为不合法？

Answer 1

从机制上讲，AccValidation 的 Either-ish Monad 实例将是

-- The (Monoid err) context is not used for anything, 
-- it's just there to satisfy the Applicative super-instance
instance (Monoid err) => Monad (AccValidation err) where
    return = AccSuccess
    AccFailure err >>= f = AccFailure err
    AccSuccess x >>= f = f x

这意味着我们有

AccFailure err1 <*> AccFailure err2 = AccFailure (err1 <> err2)
AccFailure err1 `ap` AccFailure err2 = AccFailure err1

这违反了 <*> = ap 的单子法则。

直觉上，它不能成为 monad，因为在 monad 中，计算的效果（即验证失败）可能取决于先前绑定的结果。但是在失败的情况下，是没有结果的。所以 Either 在这种情况下别无选择，只能短路故障，因为没有任何东西可以提供给 (>>=) 右侧的后续功能。

这与应用函子形成鲜明对比，应用函子的效果（在本例中为验证失败）不能依赖于其他结果，这就是为什么我们可以得到所有验证失败而不必提供结果（它们会在哪里来自？）从一个计算到另一个。

Answer 2

The (<*>) = ap exigence 可以用 (>>=):

明确表示

u <*> v = u >>= \f -> fmap f v -- [1]

现在，给定 AccValidation 的 Functor 和 Applicative 个实例，我们有：

fmap _ (AccFailure e) = AccFailure e -- [2]

AccFailure e1 <*> AccFailure e2 = AccFailure (e1 <> e2) -- [3]

如果我们在 [1] 中生成 u = AccFailure e1 和 v = AccFailure e2，我们得到：

AccFailure e1 <*> AccFailure e2 = AccFailure e1 >>= \f -> fmap f (AccFailure e2)

将 [2] 和 [3] 代入其中，我们得到：

AccFailure (e1 <> e2) = AccFailure e1 >>= \_ -> AccFailure e2 -- [4]

问题是不可能写出 (>>=) 使得 [4] 成立。左侧取决于 e2 值，该值必须在右侧源自应用 \_ -> AccFailure e2 :: Semigroup e => a -> AccValidation e b。但是，没有什么可以应用它的——特别是 e1 的类型错误。（有关这一点的进一步讨论，请参阅 Cactus 答案的最后两段。）因此，无法为 AccValidation 提供与其 Applicative 实例一致的 Monad 实例。

为什么 AccValidation 不能有 Monad 实例？

Why can AccValidation not have a Monad instance?

monads

haskell

applicative