Почему у AccValidation нет экземпляра Monad?

Question

Из документации validation пакета:

Тип данных AccValidation изоморфно Either, но имеет экземпляр Applicative, который накапливается на стороне ошибки. То есть, если встречаются две (или более) ошибки, они добавляются с помощью операции Semigroup.

В результате этого примера Applicative нет соответствующего Bind или Monad экземпляра. AccValidation - пример «Прикладного функтора, который не является монадой».

Непонятно мне, почему это является следствием. Я могу представить пример Monad для AccValidation, который ведет себя как Either. Что сделало бы это незаконным?

Answer 1

Механически, экземпляр Either -ish Monad для AccValidation будет

-- 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.

Интуитивно это невозможно сделать монадой, потому что в монаде эффект (т. Е. Ошибки проверки) вычисления может зависеть от ранее связанных результатов. Но в случае неудачи результата нет. Таким образом, у Either нет выбора, кроме как для короткого замыкания на отказ в этом случае, так как для последующих функций на правых сторонах (>>=) s нет ничего.

Это резко контрастирует с аппликативными функторами, где эффект (в данном случае, ошибки проверки) не может зависеть от других результатов, поэтому мы можем получить все отказы валидации без необходимости кормить результаты (куда они придут от?) от одного вычисления к другому.

Answer 2

The (<*>) = ap exigence можно сформулировать в явном виде в терминах (>>=):

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

Теперь, учитывая экземпляры Functor и Applicative для AccValidation, мы имеем:

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

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

Если мы u = AccFailure e1 и v = AccFailure e2 в [ 1], мы получаем:

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 имеет неправильный тип. (См. Последние два абзаца ответа кактуса для дальнейшего обсуждения этого вопроса.) Поэтому нет способа дать AccValidation a Monad экземпляр, который соответствует его Applicative.