nubBy的表现不如预期

Question

下面的函数应该生成质数，但在 GHC 7.10.2 中并没有。还有人遇到这个问题吗？

GHCi, version 7.10.2: http://www.haskell.org/ghc/  :? for help
Prelude> import Data.List
Prelude Data.List> print . take 100 . nubBy (\x y -> x `rem` y == 0) $ [2..]
[2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101]

奇怪的是，在这个网站上它似乎可以正常工作：

rextester.com/LWZCQ71376

。

- Vanson Samuel

---

我认为nubBy需要一个等价关系。 - chi

这就是文档所说的，而传递到此处的函数并非如此，这将导致未定义的行为。在实践中，它可以被重写为参数以相反的顺序应用（对于等价函数是安全的，但对于任意函数则不是）。 - that other guy

它在这里完美地工作：http://rextester.com/LWZCQ71376 - Vanson Samuel

它在ghc 7.6.3中运行。也许nubBy已被修改和“优化”，以依赖于等价关系的属性？ - Bakuriu

Answer 1

在 base-4.7.x 和 base-4.8.0.0 之间发生了什么变化，是关于 elem_by 的定义，而 nubBy 就是基于这个定义进行定义的。

在 base-4.7 中，elem_by 有以下条款：

elem_by eq y (x:xs)     =  y `eq` x || elem_by eq y xs

并且在基础版本4.8中它已经被改变为:

elem_by eq y (x:xs)     =  x `eq` y || elem_by eq y xs

这个变更的历史记录在以下 TRAC 问题中有所记载:

• 2528
• 3280
• 7913

请注意，Haskell 报告 Prelude 版本的 nubBy 是:

nubBy eq (x:xs)         =  x : nubBy eq (filter (\ y -> not (eq x y)) xs)

这与4.7版本的实现不一致，这也说明了这个改变。

- ErikR

---

eq函数应该是可交换的，这个改变似乎可能是我问题的原因。 - Vanson Samuel

不要！你的eq函数不是可交换的！“rem 4 2 /= rem 2 4”。其中一个将等于零，而另一个将为二。 - Thomas M. DuBuisson

我认为更好的术语是“对称的”。 - ErikR

@ThomasM.DuBuisson 我在谈论elem_by的变化。这个变化对我来说不应该是一个问题，因为如果 x \eq` y，那么所有Int类型都满足 y `eq` x`。所以elem_by的这个变化不会导致我的问题。 - Vanson Samuel

@ErikR 更好的术语是指什么？ - Vanson Samuel

我们是否在互相误解？在你的用法中，eq = (\x y -> x \rem` y == 0)。elem_by 的变化意味着为了使你的用法没有问题，属性(x `rem` y == 0) == (y `rem` x == 0)`必须成立。我等待你证明这样的属性成立;-)。 - Thomas M. DuBuisson

Answer 2

似乎在新的基础中，参数的顺序已经改变。编辑：我称其为错误，但是另一个答案指出旧行为是错误的顺序。

您可以通过观察来看到顺序已经翻转：

> print . take 5 . nubBy (\x y -> trace (show (x,y)) $ x `rem` y == 0) $ [2..]
[2(2,3)
,3(3,4)
(2,4)
,4(4,5)
(3,5)
(2,5)

当然，rem 2 4 不等于零（它等于2），所以它输出 4。

注意，当您在lambda中翻转参数顺序时，可以获得所需的结果：

> print . take 5 . nubBy (\x y -> trace (show (x,y)) $ y `rem` x == 0) $ [2..]
[2(2,3)
,3(3,4)
(2,4)
(3,5)
(2,5)
....

编辑：由于讨论表明关系应该是相等的，并且不考虑顺序（而我现在太懒得看报告），请注意您可以先比较参数，然后以任何方式获得稳定的行为：

print . take 100 . nubBy (\x y -> rem (max x y) (min x y) == 0) $ [2..]

- Thomas M. DuBuisson

---

你会称这为 GHC base 中的一个 bug 吗？ - Vanson Samuel

当然。首先，将“bug”定义为与Haskell语言规范相反的行为。其次，注意到这种行为是相反的。第三，大喊“bug”。 - Thomas M. DuBuisson

(\x y -> rem (max x y) (min x y) == 0) 可能具有对称性，但它仍然不是一个等价关系。 - Joachim Breitner

是的，我小心地只称之为“稳定”的行为。 - Thomas M. DuBuisson