Haskell:令人惊讶的行为"groupBy"

Question

我试图找出行为的图书馆功能groupBy(从数据。列表的)，它声称族元素的清单由一个"平等试验"功能，通过作为第一个参数。类型签名表明，平等测试只是需要有类型

(a -> a -> Bool)

然而，当我使用(<)作为"平等试验"在GHCi6.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

看看 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 假定所赋予的功能(第一个参数)的试验对于平等，并因此假定的比较功能是 反思的, 传递的 和 对称 (见 等价关系).这里的问题是， 比 关系不是自反，也不对称。

---

编辑:下面的执行只能假定传递:

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

的问题是，在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是在其定义中使用跨度。为了得到它不依赖于我们是否有任何特定的顺序，我们可以定义一个函数基础列表合理的行为：

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