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 假定给定函数(第一个参数)测试相等性，因此假定比较函数是自反， 传递和对称(参见equivalence relation)。这里的问题是小于关系不是自反的，也不是对称的。

<小时/>

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

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