monad 的 "ap" 实现有多随意？

Question

我目前正在研究 monad 和 applicative functor 之间的联系。

我看到 ap 的两个实现：

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

和

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

第二个不同，但是，它是 <*> 的良好实施吗？

我迷失在 pure (.) <*> u <*> v <*> w = u <*> (v <*> w)

的证明中

我试图获得 "what part of the monad is the applicative functor"...

的直觉

Answer 1

让我们从一个显而易见的事实开始：<*> 的这种定义违反了 ap 定律，因为 <*> 应该 ap，其中 ap 是 Monad class 中定义的，即您发布的第一个。

撇开琐事不谈，据我所知，其他适用法则应该成立。

更具体一点，我们重点关注你说的构图法则。你的"reversed"ap

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

也可以定义为

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

其中 <*> 是 "regular" 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 = ...

Answer 2

这个问题至少有三个相关方面。

给定一个Monad m实例，其必要的Applicative m超级class实例的规范是什么？回答：pure是return，<*>是ap，所以
```
mf <*> ms == do f <- mf; s <- ms; return (f s)
```

注意这个规范不是Applicativeclass的规律。这是对 Monad 的要求，以确保一致的使用模式。

鉴于该规范（通过候选实现），ap 是唯一可接受的实现。回答：响亮地说，没有。 >>= 类型允许的值依赖有时会导致执行效率低下：在某些情况下 <*> 可以比 ap 更高效，因为您不需要等待在你知道第二个计算是什么之前完成第一个计算。 "applicative do" 符号的存在正是为了利用这种可能性。
Applicative 的任何其他候选实例是否满足 Applicative 法则，即使它们不同意所需的 ap 实例？回答：是的。问题提出的 "backwards" 实例就是这样的东西。事实上，正如另一个答案所观察到的，任何应用程序都可以倒转，结果往往是不同的野兽。

有关 reader 的进一步示例和练习，请注意非空列表以普通列表所熟悉的方式是一元的。

  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 实例，它们遵守适用法则。

monad 的 "ap" 实现有多随意？

How arbitrary is the "ap" implementation for monads?

monads

haskell

applicative