Насколько произвольна реализация "ap" для монад?

Ответ 1

В этом вопросе есть по крайней мере три важных аспекта.

• Учитывая экземпляр Monad m, какова спецификация его необходимого экземпляра суперкласса Applicative m? Ответ: pure - return, <*> - ap, поэтому

  mf <*> ms == do f <- mf; s <- ms; return (f s)
  

Обратите внимание, что эта спецификация не является законом класса Applicative. Это требование на Monad s, чтобы обеспечить согласованные шаблоны использования.

2. Учитывая, что спецификация (по реализации кандидата), является ap единственной приемлемой реализацией. Ответ: громко, нет. Зависимость значений, разрешенная типом >>=, может иногда приводить к неэффективному выполнению: бывают ситуации, когда <*> можно сделать более эффективным, чем ap, потому что вам не нужно ждать завершения первого вычисления до вас может сказать, что такое второе вычисление. Для того, чтобы использовать эту возможность, существует "апликативная" запись.

3. Выполняют ли какие-либо другие экземпляры-кандидаты для Applicative законы Applicative, даже если они не согласны с требуемыми экземплярами ap? Ответ: да. "Обратный" пример, предложенный вопросом, - это просто вещь. В самом деле, как замечает другой ответ, любое приложение может быть повернуто назад, и результат часто является другим зверем.

В следующем примере и упражнении для читателя обратите внимание, что непустые списки являются монадическими в обычном порядке из обычных списков.

  data Nellist x = x :& Maybe (Nellist x)

  necat :: Nellist x -> Nellist x -> Nellist x
  necat (x :& Nothing) ys = x :& Just ys
  necat (x :& Just xs) ys = x :& Just (necat xs ys)

  instance Monad Nellist where
    return x = x :& Nothing
    (x :& Nothing) >>= k = k x
    (x :& Just xs) >>= k = necat (k x) (xs >>= k)

Найдите по крайней мере четыре различных по-разному экземпляра Applicative Nellist, которые подчиняются прикладным законам.

Ответ 2

Начнем с очевидного факта: такое определение для <*> нарушает ap -law в том смысле, что <*> должен ap, где ap - тот, который определен в классе Monad, т.е. первый, который вы опубликовали.

Отрицательные моменты, насколько я вижу, должны придерживаться и другие применимые законы.

Более конкретно, позвольте сосредоточиться на указанном вами законе о композиции. Ваш "обратный" ap

(<**>) m1 m2 = do { x <- m2 ; f <- m1 ; return (f x) }

также можно определить как

(<**>) m1 m2 = pure (flip ($)) <*> m2 <*> m1

где <*> является "регулярным" ap.

Это означает, что, например,

u <**> (v <**> w) =
  { def. <**> }
pure (flip ($)) <*> (v <**> w) <*> u =
  { def. <**> }
pure (flip ($)) <*> (pure (flip ($)) <*> w <*> v) <*> u =
  { composition law }
pure (.) <*> pure (flip ($)) <*> (pure (flip ($)) <*> w) <*> v <*> u =
  { homomorphism law }
pure ((.) (flip ($))) <*> (pure (flip ($)) <*> w) <*> v <*> u =
  { composition law }
pure (.) <*> pure ((.) (flip ($))) <*> pure (flip ($)) <*> w <*> v <*> u =
  { homomorphism law (x2)}
pure ((.) ((.) (flip ($))) (flip ($))) <*> w <*> v <*> u =
  { beta reduction (several) }
pure (\x f g -> g (f x)) <*> w <*> v <*> u

(Я надеюсь, что все получилось нормально)

Попробуйте сделать что-то похожее на левую сторону.

pure (.) <**> u <**> v <**> w = ...