groupBy应该做什么？

Question

我写了一些东西Data.List.groupBy.它没有按预期工作,所以我最终写了我自己的版本groupBy:毕竟我不确定那个Data.List应该做什么(没有真正的文档).

无论如何,我的测试通过我的版本,groupBy而它失败了Data.List.我发现(感谢quickcheck)两个函数表现不同的情况,我仍然不明白为什么两个版本之间存在差异.是Data.List版本马车或者是我的？(当然我的是一个天真的实现,可能不是最有效的方法).

这是代码:

import qualified Data.List as DL
import Data.Function (on)
import Test.QuickCheck

groupBy' :: (a -> a ->  Bool) -> [a] -> [[a]]
groupBy' _ [] = []
groupBy' eq (x:xs) = xLike:(groupBy' eq xNotLike) where
    xLike = x:[ e | e <- xs, x `eq` e  ]
    xNotLike = [ e | e <- xs, not $ x `eq` e  ]

head' [] = Nothing
head'  (x:xs) = Just x

prop_a s = (groupBy' by s) == (DL.groupBy by s) where
    types = s :: [String]
    by = (==) `on` head'

在ghc中 运行quickCheck prop_a返回["", "a", ""]

*Main> groupBy' ((==) `on` head') ["","a",""]
[["",""],["a"]] # correct in my opinion
*Main> DL.groupBy ((==) `on` head') ["","a",""]
[[""],["a"],[""]] # incorrect.

发生了什么 ？我不敢相信haskell平台上有一个bug.

Answer 1

你的版本是O(n ²) - 在现实世界中使用速度慢得令人无法接受¹.

标准版本通过仅对相邻元素进行分组来避免这种情况.因此,

*Main> groupBy((==)`on`head')["","","a"]

将产生你所追求的结果.

获得"通用分组"的一种简单方法groupBy是首先对列表进行排序,如果这对于数据类型是可行的.

*Main> groupBy((==)`on`head')$ DL.sort ["","a",""]

其复杂性仅为O(n log n).

¹这并不妨碍委员会指定nub为O(n ²)......