哈斯克尔:“群比”的惊人行为

看一看这本书 ghc 实施 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 假设给定函数(第一个参数)测试相等性,因此假设比较函数为 反射的 及物的 和 对称的 (见 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

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

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

现在有3组相等的元素。因此,它会检查它们中是否有任何一个实际上是相同的:

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

1>1.不所以最后一组是。

现在它比较了所有元素的相等性。

简言之 when it wants an equality test, give it an equality test .

问题是,参考实现 groupBy 在Haskell报告中,将元素与第一个元素进行比较,因此组并没有严格地增加(它们只需要都大于第一个元素)。你想要的是一个版本的 群比 测试 相邻 元素,比如实现 here

我只想指出,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