monad的"ap"实现有多武断？

Question

我目前正在研究monad和applicative functors之间的联系.

我看到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)

我试图直观地说"monad的哪一部分是应用函子"......

Answer 1

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

1. 给定一个Monad m实例,其必要的Applicative m超类实例的规范是什么？答案:pure是return,<*>是ap,所以

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

请注意,此规范不是Applicative该类的法律.这是Monads 的要求,以确保一致的使用模式.

2. 鉴于该规范(通过候选实现),是ap唯一可接受的实现.答案:响亮,没有.类型允许的值依赖性>>=有时会导致执行效率低下:有些情况下<*>可以提高效率,ap因为您无需等待第一次计算完成,然后才能知道第二次计算是什么."applicative do"符号恰好存在于利用这种可能性.

3. 是否有任何其他候选实例Applicative满足Applicative法律,即使他们不同意所需的ap实例？答:是的.问题提出的"倒退"实例就是这样的事情.事实上,正如另一个答案所指出的那样,任何一个应用都可以倒退,结果往往是一个不同的野兽.

对于读者的进一步示例和练习,请注意非空列表以普通列表中熟悉的方式是monadic.

  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符合适用法律的行为上不同的实例.

Answer 2

让我们先从一个明显的事实:这样的定义为<*>违反了ap在这个意义上,婆媳<*>应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 = ...