时间戳

首页 > 解决方案 > groupBy 的奇怪行为

haskell - groupBy 的奇怪行为

问题描述

我想知道为什么下面的调用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吗？

标签： haskell

解决方案

在实现中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使用 list运行[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。

推荐阅读