monads的「ap」實現有多隨意？

Question

我目前正在研究monad和applicative仿函數之間的關係。

我看到兩個實施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)

我想方設法把「什麼單子的部分是適用函子」的直覺證明...

Answer 1

這個問題至少有三個相關方面。

1. 給定一個Monad m例如，什麼是它的必要Applicative m父實例的規範？ 答：pure是return，<*>是ap，所以

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

注意，該規範是不是Applicative類的法律。這是Monad的要求，以確保一致的使用模式。

1. 鑑於該規範（通過候選實現），是ap唯一可接受的實現。答案：令人震驚的是，沒有。 >>=類型所允許的值相關性有時會導致執行效率低下：有些情況下<*>可以比ap更有效，因爲您無需等待第一次計算完成，然後才能知道第二次計算的結果是。 「應用做」符號的存在正是爲了利用這種可能性。

2. 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不同實例。

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 

（我希望我得到的一切OK）

試着做類似左側的東西。

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