Haskell：“groupBy”的令人惊讶的行为

Question

我试图找出库函数 groupBy （来自 Data.List）的行为，它旨在通过作为第一个参数传入的“相等测试”函数对列表的元素进行分组。类型签名表明相等测试只需要具有类型

(a -> a -> Bool)

但是，当我在 GHCi 6.6 中使用 (<) 作为“相等测试”时，结果不是我所期望的：

ghci> groupBy (<) [1, 2, 3, 2, 4, 1, 5, 9]
[[1,2,3,2,4],[1,5,9]]

相反，我期望运行严格递增的数字，就像这样：

[[1,2,3],[2,4],[1,5,9]]

我错过了什么？

Answer 1

查看 groupBy：

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

现在比较这两个输出：

Prelude List> groupBy (<) [1, 2, 3, 2, 4, 1, 5, 9]
[[1,2,3,2,4],[1,5,9]]
Prelude List> groupBy (<) [8, 2, 3, 2, 4, 1, 5, 9]
[[8],[2,3],[2,4],[1,5,9]]

简而言之，发生的情况是这样的：groupBy 假设给定函数（第一个参数）测试相等性，因此假设比较函数是自反、传递和对称（参见等价关系）。这里的问题是小于关系不是自反的，也不是对称的。

---

编辑：以下实现仅假设传递性：

groupBy' :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy' _   []                        = []
groupBy' _   [x]                       = [[x]]
groupBy' cmp (x:xs@(x':_)) | cmp x x'  = (x:y):ys
                           | otherwise = [x]:r
  where r@(y:ys) = groupBy' cmp xs

Answer 2

事实是“<”不是平等测试。

您可能会期望某些行为，因为您会以不同的方式实现它，但这并不是它所承诺的。

为什么它输出的是合理答案的一个例子是，如果它扫描它，那么

[1, 2, 3, 2, 4, 1, 5, 9] ->
[[1,2,3], [2,4], [1,5,9]]

Now 有 3 组相等的元素。因此，它检查它们中的任何一个实际上是否相同：

因为它知道每个组中的所有元素都相等，所以它可以只查看每个组中的第一个元素，1、2 和 1。

1 > > 2？是的！所以它合并了前两组。

1> 1？不！所以剩下最后一组。

现在它比较所有元素是否相等。

...只是，您没有传递给它它所期望的那种功能。

简而言之，当它需要相等性测试时，给它一个相等性测试。

Answer 3

问题在于 Haskell 报告中 groupBy 的参考实现将元素与第一个元素进行比较，因此组并不是严格递增的（它们只需全部大于第一个元素）。相反，您想要的是在相邻元素上进行测试的groupBy版本，例如实现此处。

Answer 4

我想指出的是，groupBy 函数还要求在应用之前对列表进行排序。

例如：

equalityOp :: (a, b1) -> (a, b2) -> Bool
equalityOp x y = fst x == fst y

testData = [(1, 2), (1, 4), (2, 3)]

correctAnswer = groupBy equalityOp testData == [[(1, 2), (1, 4)], [(2, 3)]]

otherTestData = [(1, 2), (2, 3), (1, 4)]

incorrectAnswer = groupBy equalityOp otherTestData == [[(1, 2)], [(2, 3)], [(1, 4)]]

出现此行为是因为 groupBy 在其定义中使用了 span。为了获得不依赖于我们以任何特定顺序拥有底层列表的合理行为，我们可以定义一个函数：

groupBy' :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy' eq []     = []
groupBy' eq (x:xs) = (x:similarResults) : (groupBy' eq differentResults)
    where similarResults   = filter (eq x) xs
          differentResults = filter (not . eq x) xs