26

Haskell wikibook断言

MonadPlus 的实例需要满足几个规则,就像 Monad 的实例需要满足三个 monad 定律一样。... 最重要的是 mzero 和 mplus 形成一个幺半群。

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

然而,Oleg 在他的众多回溯搜索实现之一中写道

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

定义 non-associative 是否符合规定mplus?前两个链接非常清楚地表明如果不是关联的,您就没有真实的MonadPlus实例。mplus但是如果Oleg这样做了……(另一方面,在该文件中,他只是定义了一个名为 的函数mplus,并没有声称那 mplusof mplusMonadPlus如果这是正确的解释,他选择了一个非常令人困惑的名称。)

4

3 回答 3

30

以下是奥列格本人的意见,以及我的评论和他的澄清。

好的首先,我想说明我与 Gabriel Gonzalez 的分歧。不是每个人都同意关于和MonadPlus应该是幺半群。报告对此只字未提。有许多令人信服的案例并非如此(见下文)。一般来说,代数结构应该适合任务。这就是为什么我们有群体,还有更弱的半群体或群体(岩浆)。它似乎 通常被视为搜索/非确定性单子。如果是这样,那么 的属性应该是那些有助于搜索和推理搜索的属性——而不是某些人出于任何原因喜欢的理想的临时属性。让我举个例子:设定法律很诱人mplusmzeroMonadPlusMonadPlus

m >> mzero === mzero

然而,支持搜索并能产生其他效果(想想 NonDeT m)的 monad 不能满足该定律。例如,

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

因为左侧打印了一些东西,但右侧没有。同理,mplus不能是对称的:在同一模型中,mplus m1 m2 通常不同于,。mplus m2 m1

让我们来mplusmplus 不需要关联的主要原因有两个。首先是搜索的完整性。考虑

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

因此,看起来,和 foo 是相同的。这意味着,我们永远不会从 foo 得到答案 2。

该结果适用于任何可以由 表示的搜索,MonadPlus只要mplus是关联的和不可交换的。因此,如果MonadPlus是搜索的单子,那么的关联性mplus是不合理的要求。

这是第二个原因:有时我们希望进行概率搜索——或者,一般来说,加权搜索,当一些备选方案被加权时。很明显,概率选择算子不是关联的。mplus出于这个原因,我们的 JFP 论文特别避免mzeroMonadPlus.

http://okmij.org/ftp/Computation/monads.html#lazy-sharing-nondet (参见论文图 1 的讨论)。

R.C. I think Gabriel and you agree on the fact that search monads do not exhibit the monoid structure. The argument boils down to whether MonadPlus should be used for search monads or should there be another class, let's call it MonadPlus', which is just like MonadPlus but with more lax laws. As you say, the report doesn't say anything on this topic, and there's no authority to decide.

For the purpose of reasoning, I don't see any problem with that — one just has to state clearly her assumptions about the MonadPlus instances.

As for the rewrite rule that re-associates mplus'es, the mere existence and widespread use of MonadPlus instances that are not associative, regardless of whether they are "broken", means that one should probably abstain from defining it.

O.K. I guess I disagree with Gabriel's statement

The monoid laws are the minimum requirement because without them the other laws are meaningless. For example, when you say mzero >>= f = mzero, you first need some sensible definition of mzero is, but without the identity laws you don't have that. The monoid laws are what keep the other proposed laws "honest". If you don't have the monoid laws then you have no sensible laws and what's the point of a theoretical type class that has no laws?

For example, LogicT paper and especially the JFP paper has lots of examples of equational reasoning about non-determinism, without associativity of mplus. The JFP paper omits all monoid laws for mplus and mzero (but uses mzero >>= f === mzero). It seems one can have "honest" and "sensible laws" for non-determinism and search without the monoid laws for mplus and mzero.

I'm also not sure I agree with the claim

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

I'm not sure a poll has been taken on this. The Report states no laws for mplus (perhaps the authors were still debating them). So, I would say the issue is open — and this is the main message to get across.

于 2013-04-06T17:15:00.113 回答
22

每个人都同意MonadPlus应该遵守的两条定律是恒等律和结合律(又名幺半群定律):

mplus mempty a = a

mplus a mempty = a

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

我总是假设它们在MonadPlus我使用的所有情况下都成立,并认为违反这些法律的情况是“破坏”的,无论它们是否由 Oleg 编写。

奥列格是对的,关联性不能很好地与广度优先搜索配合使用,但这只是意味着这MonadPlus不是他正在寻找的抽象。

为了回答您在评论中提出的观点,我始终认为您的重写规则是合理的。

于 2013-03-30T21:15:43.867 回答
4

实例违反关联性的情况很少见MonadPlus,但显然并非不可能。类型类只能在一定程度上满足“明显”的规律。例如,MonadPlus 这里讨论了另外四组可能的定律,而没有任何结论,并且图书馆遵循各种约定而没有具体说明哪一个。

显然,奥列格有理由不考虑关联性。它是“真正的MonadPlus实例”吗?谁知道呢,说的不够清楚。

于 2013-03-30T20:34:39.430 回答