什么是群体应该做的？

我用Data.List.groupBy写了一些东西。它没有按预期工作，所以我最终写了我自己的版本groupBy：毕竟我不确定Data.List应该这样做（没有真正的文档）。什么是群体应该做的？

无论如何，我的测试通过了我的版本groupBy，而它的失败与Data.List。我发现（感谢quickcheck）两个函数行为不同的情况，我仍然不明白为什么这两个版本之间存在差异。是Data.List版本的车或是我的？（当然，我的天真实施并不是最有效的方式）。

下面是代码：在GHC运行

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'

quickCheck prop_a回报["", "a", ""]

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

发生了什么事？我无法相信haskell平台有bug。

来源

2014-04-06 mb14

'groupBy'函数将一个列表分割成几部分，例如'concat。 groupBy f == id'（以及其他法律）。 – augustss

你的版本是Ø（ñ ） - 这可以在现实世界使用慢得不可接受。

标准版本通过仅将邻近的元素分组（如果它们是相等的）来避免这种情况。因此，

*主要> GROUPBY（（==）`on`头'） “”， “”， “一”]

将产生你之后的结果。

使用groupBy获得“通用分组”的一种简单方法是首先对列表进行排序，如果这对数据类型是可行的。

*主要> GROUPBY（（==）`on`头'）$ DL.sort [ “”， “一”， “”]

的这样的复杂性只是ö（n log n）。

这并不阻碍委员会指定nub为Ø（ñ ）...

来源

2014-04-06 18:22:28 leftaroundabout

阅读'groupBy'文件我发现它确实相邻，并且与我所需要的行为不同：正常的'group by'。我可以做一个确实的事情，但没有意识到这是必要的。我的版本并不假装在实词中可用，也没有为参数添加不必要的约束。除了明显的性能原因之外，“Ord”约束在功能上是不必要的。 – mb14

Data.List.groupBy在Haskell是一个可用性错误！一个用户友好的groupBy应该像这样：

groupByWellBehaved p = foldr (\x rest -> if null rest 
            then [[x]] 
            else if p x (head (head rest)) 
              then (x : head rest) : (tail rest) 
              else [x] : rest) []

也许有更好的实现，但至少这是O（n）。

来源

2015-07-31 00:50:55 mljrg

什么是群体应该做的？

回答

相关问题