Haskell：“groupBy”的令人惊讶的行为 [英] Haskell: surprising behavior of "groupBy"

问题描述

我试图找出库函数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]] 
  

我错过了什么？

解决方案

ghc 实现rel = noreferrer> groupBy ：

  groupBy ::（a  - > a  - > Bool） - > ; [a]  - > [（a）] 
 groupBy _ [] = [] 
 groupBy eq（x：xs）=（x：ys）：groupBy eq zs 
其中（ys，zs）= span eq x）xs 
  

现在比较这两个输出：

 前奏列表> groupBy（<）[1,2,3，2,4,1,5,9] 
 [[1,2,3,2,4]，[1,5,9]] 
前奏列表> 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 
 |否则= [x]：r 
其中r @（y：ys）= groupBy'cmp xs 
  

I'm trying to figure out the behavior of the library function groupBy (from Data.List), which purports to group elements of a list by an "equality test" function passed in as the first argument. The type signature suggests that the equality test just needs to have type

(a -> a -> Bool)

However, when I use (<) as the "equality test" in GHCi 6.6, the results are not what I expect:

ghci> groupBy (<) [1, 2, 3, 2, 4, 1, 5, 9]
[[1,2,3,2,4],[1,5,9]]

Instead I'd expect runs of strictly increasing numbers, like this:

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

What am I missing?

解决方案

Have a look at the ghc implementation of groupBy:

groupBy                 :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy _  []           =  []
groupBy eq (x:xs)       =  (x:ys) : groupBy eq zs
                           where (ys,zs) = span (eq x) xs

Now compare these two outputs:

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

In short, what happens is this: groupBy assumes that the given function (the first argument) tests for equality, and thus assumes that the comparison function is reflexive, transitive and symmetric (see equivalence relation). The problem here is that the less-than relation is not reflexive, nor symmetric.

---

Edit: The following implementation only assumes transitivity:

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

这篇关于Haskell：“groupBy”的令人惊讶的行为的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！