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的ghc实现:

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]]

现在有3组相等的元素.所以它检查它们中的任何一个是否实际上是相同的:

因为它知道每个组中的所有元素是相等的,所以它只能查看每个元素中的第一个元素,即1,2和1.

1> 2？是! 所以它合并了前两组.

1> 1？没有!所以它留下了最后一组.

现在,它将所有要素进行了比较.

...只是,你没有传递它预期的那种功能.

简而言之,当它想要一个相等的测试时,给它一个相等的测试.

Answer 3

问题是groupByHaskell报告中的参考实现将元素与第一个元素进行比较,因此这些组并没有严格增加(它们只需要比第一个元素都大).您想要的是相邻元素的groupBy测试版本,例如此处的实现.