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因此，Since不是列表中的前一个值。如果我们这样运行groupBylist [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是列表的第一项，情况并非如此。

通常你应该只使用等价关系 ~ [wiki]，这种关系是：

1. 反身：x ~ x确实如此；
2. 对称：所以x ~ y当且仅当y ~ x；和
3. 及物：所以x ~ y并y ~ z暗示那个x ~ z。

你的等价关系不是自反的，也不是对称的。因此，这不是一个可以使用的有效函数groupBy。