haskell - groupBy 的奇怪行为

Question

我想知道为什么以下调用 groupBy不起作用:我的谓词是 x < y ，所以我希望 [1, 6]成为一个组，但 Haskell 将 [1, 6, 4, 2]成一个组。

Prelude Data.List> groupBy (\x y -> x < y) [8,5,3,2,1,6,4,2]
[[8],[5],[3],[2],[1,6,4,2]]

更奇怪的是，当我将最后一个数字更改为 -2 时，我期望与上面示例中的行为相同。也就是说，由于 2 和 -2 都小于 4，我希望在结果中 [1, 6, 4, -2]会组成一个小组。但是，这一次，Haskell 将 -2 设置为一个组。

Prelude Data.List> groupBy (\x y -> x < y) [8,5,3,2,1,6,4,-2]
[[8],[5],[3],[2],[1,6,4],[-2]]

我对 groupBy有什么误解吗？ ?

Answer 1

在执行groupBy , x始终是子列表的第一项。确实，groupBy实现为:

groupBy                 :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy _  []           =  []
groupBy eq (x:xs)       =  (x:ys) : groupBy eq zs
                           where (ys,zs) = span (eq x) xs

尤其是 span (eq x)在这里很重要，因为 x将是新组的第一项。
由于 x因此不是列表中的前一个值。如果我们因此运行 groupBy与列表 [5, 3, 2, 1, 6, 4, -2] ，我们得到:


列表
当前列表
x=?
检查
结果

[5,3,2,1,6,4,-2] [8] 8 / / [5,3,2,1,6,4,-2] [8] 8 5 False [3,2,1,6,4,-2] [5] 5 / / [3,2,1,6,4,-2] [5] 5 3 False [3,2,1,6,4,-2] [3] 3 / / [2,1,6,4,-2] [3] 3 2 False [2,1,6,4,-2] [2] 2 1 False [1,6,4,-2] [2] 2 / / [1,6,4,-2] [2] 2 1 False [6,4,-2] [1] 1 / / [4,-2] [1,6] 1 6 True [-2] [1,6,4] 1 4 True [] [-2] -2 / /

尤其是我们比较 x=1 的情况和 y=4很重要。如果 x只是以前的值，我们应该开始生成一个新列表，但是因为 x是列表的第一项，但事实并非如此。
通常你应该只使用 equivalence relation ~ [wiki] ，这样的关系是:

反身:所以 x ~ x是真的;

对称:所以 x ~ y当且仅当 y ~ x ;和

传递:所以 x ~ y和 y ~ z表示 x ~ z .

您的等价关系不是自反的，也不是对称的。因此，这不是与 groupBy 一起使用的有效函数。 .