必须mplus总是联想？ Haskell wiki与Oleg Kiselyov [英] Must mplus always be associative? Haskell wiki vs. Oleg Kiselyov

问题描述

Haskell wikibook 断言：

MonadPlus的实例需要满足几个规则，就像Monad实例需要满足三条monad法则一样。 ...最重要的是mzero和mplus构成一个monoid。

其结果是 mplus 必须是关联的。 Haskell wiki 同意。

但是，Oleg在<他的许多回溯搜索实现中的一个写道：

   - 一般来说，mplus不是关联的。最好不要是
  - 因为联想和非交换mplus使搜索
  - 策略不完整。 
  

是否可以定义一个非关联的 mplus ？前两个链接非常清楚地表明，如果 mplus 不是关联的，那么您没有真正的 MonadPlus 实例。但是如果 Oleg 这样做......（另一方面，在那个文件中，他只是定义了一个名为 mplus 的函数，并没有声称 mplus 是 MonadPlus mplus 如果这是正确的解释，他选择了一个相当混乱的名字。）

那么 MonadPlus 应该服从的是身份和关联性法则（aka monoid laws）： $ b $

  mplus mempty a = a 
 
 mplus a mempty = a 
 
 mplus（mplus ab）c = mplus a（mplus bc）
  

我总是假设它们持有我使用并考虑实例的所有 MonadPlus 实例违反这些法律将被破坏，无论它们是否由Oleg编写。

Oleg是正确的，associativity不能很好地处理广度优先搜索，但这仅仅意味着 MonadPlus 不是为了回答你在评论中提出的观点，我总是会认为你的重写规则听起来很美妙。

b

The Haskell wikibook asserts that

Instances of MonadPlus are required to fulfill several rules, just as instances of Monad are required to fulfill the three monad laws. ... The most essential are that mzero and mplus form a monoid.

A consequence of which is that mplus must be associative. The Haskell wiki agrees.

However, Oleg, in one of his many backtracking search implementations, writes that

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

Is it kosher to define a non-associative mplus? The first two links pretty clearly suggest you don't have a real MonadPlus instance if mplus isn't associative. But if Oleg does it ... (On the other hand, in that file he's just defining a function called mplus, and doesn't claim that that mplus is the mplus of MonadPlus. He chose a pretty confusing name, if that's the right interpretation.)

解决方案

The two laws that everybody agrees that MonadPlus should obey are the identity and associativity laws (a.k.a. the monoid laws):

mplus mempty a = a

mplus a mempty = a

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

I always assume they hold in all MonadPlus instances that I use and consider instances that violate those laws to be "broken", whether or not they were written by Oleg.

Oleg is right that associativity does not play nicely with breadth-first search, but that just means that MonadPlus is not the abstraction he is looking for.

To answer the point you made in a comment, I would always consider that rewrite rule of yours sound.

这篇关于必须mplus总是联想？ Haskell wiki与Oleg Kiselyov的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！