必須mplus總是聯想？哈斯克爾維基與奧列格Kiselyov

Question

的Haskell wikibook斷言MonadPlus的

實例都必須滿足幾個規則，就像單子的情況下，須符合三個單子法律。 ......最重要的是mzero和mplus構成一個monoid。

其結果是mplus必須是關聯的。 Haskell wiki同意。

然而，奧列格在one of his many backtracking search implementations寫道，

-- Generally speaking, mplus is not associative. It better not be, 
-- since associative and non-commutative mplus makes the search 
-- strategy incomplete. 

它是猶太定義爲非關聯mplus？前兩個鏈接非常清楚地表明，如果mplus不是關聯的，則您沒有真實的MonadPlus實例。但是，如果奧列格做它...（在另一方面，在該文件中，他只是定義一個名爲mplus功能，並沒有聲稱即mplus是MonadPlus的mplus，他選擇了一個非常令人迷惑的名字，如果這是正確的解釋。）

Answer 1

的兩部法律，每個人都同意，MonadPlus應遵守的身份和結合法（又名獨異規律）：

mplus mempty a = a 

mplus a mempty = a 

mplus (mplus a b) c = mplus a (mplus b c) 

我一直以爲他們在所有MonadPlus情況下，我使用的把握和考慮的實例是違反這些法律是「破碎」的，不管它們是不是奧列格寫的。

奧列格是正確的，associativity不與廣度優先搜索很好地玩，但這只是意味着MonadPlus不是他正在尋找的抽象。

爲了迴應您在評論中所提出的觀點，我總是會認爲你的重寫規則聽起來很重要。

Answer 2

MonadPlus實例違反關聯性很少見，但顯然不是不可能的。只能計數類特定符合一定數量的「明顯」規律。例如，MonadPlusare discussed here的另外四組可能的法律沒有任何結論，而且圖書館遵循各種約定，但沒有指定哪一個。顯然，奧列格有一個理由來解散聯想性。它是否「真的是MonadPlus實例」？誰知道，這是不夠明確的說。

Answer 3

下面是奧列格自己的意見，我的評論和他的澄清。

O.K.首先我想註冊我與Gabriel Gonzalez的分歧。並非所有人都同意MonadPlus應與 相關mplus和mzero應該是monoid。報告沒有提到這一點。如果不是這樣，那麼 就是很多引人注目的案例（見下文）。一般來說，代數結構應該適合任務。這就是爲什麼我們有 組，還有更弱的半羣或類羣（岩漿）。看來 MonadPlus通常被認爲是一個搜索/非確定性單子。如果是這樣， 然後MonadPlus的屬性應該是促進 搜索和推理有關搜索 - 而不是一些理想的ad hoc特性 性能某人喜歡出於任何原因。讓我舉一個例子： 很容易讓人斷定法律

m >> mzero === mzero 

然而，支持搜索和可以做其他的效果單子（想 NonDeT m）不能滿足該法律。例如，

print "OK" >> mzero =/== mzero 

因爲左側打印的東西，但右手 沒有。同樣的道理，mplus不能是對稱的：mplus m1 m2 一般不同於mplus m2 m1，在同一模型中。

讓我們來mplus。有兩個主要原因不要求mplus 是關聯的。首先是搜索的完整性。考慮

ones = return 1 `mplus` ones 

foo = ones `mplus` return 2 
    === {- inlining ones -} 
    (return 1 `mplus` ones) `mplus` return 2 
    === {- associativity -} 
    return 1 `mplus` (ones `mplus` return 2) 
    === 
    return 1 `mplus` foo 

因此，似乎coinductively one和foo是相同的。那 的意思是，我們永遠不會從foo得到答案2。

該結果適用於可由MonadPlus表示的任何搜索，因此 只要mplus是關聯性和非交換性的。因此，如果MonadPlus是一個 monad用於搜索，則mplus的關聯性是不合理的要求。

這裏是第二個原因：有時，我們希望有一個概率 搜索 - 或者，在一般情況下，加權搜索，當一些替代品 加權。很顯然，概率選擇算子不是聯想性的。出於這個原因，我們的JFP文件特別避免 在MonadPlus上施加monoid（mplus,mzero）結構。

http://okmij.org/ftp/Computation/monads.html#lazy-sharing-nondet （參見論文的圖1的討論）。

R.C. 我認爲加布裏埃爾和你同意這個事實，搜索monad不 展覽monoid結構。這個論點歸結爲 MonadPlus應該用於搜索monads還是應該有另一個 類，我們稱之爲MonadPlus'，這就像MonadPlus，但 更寬鬆的法律。正如你所說，這份報告在這個主題上沒有說什麼，也沒有權力決定。

出於推理的目的，我沒有看到任何問題 - 一個 只是要清楚地陳述她對MonadPlus實例的假設。

至於是重新聯營mplus「ES重寫規則，僅僅存在 和廣泛使用MonadPlus情況下是不相關聯， 無論它們是否是‘破’，就是應該大概 忌諱定義它。

O.K. 我想我與加布裏埃爾的聲明

不同意幺法律是最低限度的要求，因爲 沒有他們的其他法律是沒有意義的。例如，當你說 mzero >>= f = mzero，你首先需要一些明智的定義 mzero是，但沒有身份法律你沒有。幺半律是其他提出的法律是「誠實」的。如果你沒有 有幺半律，那麼你沒有明智的法則，什麼是沒有規律的理論類型的點 ？

例如，LogicT紙特別是JFP紙具有許多有關的非確定性等式推理 例子，而不 關聯的mplus。 JFP文件省略了所有幺半律：mplus 和mzero（但使用mzero >>= f === mzero）。看起來可以有 「誠實」和「明智的法律」爲非決定論和搜索沒有 幺半律mplus和mzero。

我也不能肯定我同意要求

的兩部法律，每個人都同意，MonadPlus應該服從是 身份和關聯的法律（又名獨異規律）：

我不確定有人對此進行過民意調查。該報告沒有提供 的mplus法律（也許作者仍在辯論它們）。所以，我 會說這個問題是開放的 - 這是獲得 的主要信息。