Haskell:令人惊讶的行为"groupBy"
-
19-09-2019 - |
题
我试图找出行为的图书馆功能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]]
我是什么丢失?
解决方案
看看 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
其他提示
这“<”的事实并不是等同测试
您可能会想到一些行为,因为你不同的方式实现它,但是这不是什么承诺。
的原因是什么,输出是一个合理的答案的一个例子是,如果它扫过它,做
[1, 2, 3, 2, 4, 1, 5, 9] ->
[[1,2,3], [2,4], [1,5,9]]
现在有3组等于元件。所以它检查其中是否实际上是相同的:
,因为它知道的所有元素中的每个基团是相等的,它可以只是看在每个第一元件,1,2和1。
1> 2?是!因此,它合并前两组。
1> 1?没有!因此,离开最后一组是。
和现在它的比较是否相等的所有元素。
...只有你没有通过它的各种功能,预计。
在短,当它要相等试验,得到它等同测试。
的问题是,在Haskell的报告groupBy
的参考实现比较靠第一元件的元件,所以该基团不严格递增(它们只是要所有比第一元件更大)。你想要什么,而不是一个版本groupBy
的上的相邻的元素,如实施的此处。
我只是想指出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