什麼是羣體應該做的？

我用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

什麼是羣體應該做的？

回答

相關問題