GroupBy函數來自Haskell中的.NET

Question

.NET框架中的LINQ庫確實有一個非常有用的函數GroupBy，我一直在使用它。 其在Haskell類型會是什麼樣子

Ord b => (a-> b) -> [a] -> [(b, [a])] 

其目的是基於給定的分類功能f項目分爲桶，與含有類似的項目每個桶，這是(b, l)使得對於l任何項目x， f x == b。它在.NET中的性能是O（N），因爲它使用散列表，但在Haskell中，我確定O（N * log（N））。

我在標準的Haskell庫中找不到類似的東西。另外，我的標準功能方面實現多少有些笨重：

myGroupBy :: Ord k => (a -> k) -> [a] -> [(k, [a])] 
myGroupBy f = map toFst 
     . groupBy ((==) `on` fst) 
     . sortBy (comparing fst) 
     . map (\a -> (f a, a)) 
    where 
     toFst l@((k,_):_) = (k, map snd l) 

這絕對不是我想看到我之間特定問題的代碼。

我的問題是：我怎樣才能實現這個功能很好地利用標準庫到他們最大？

此外，似乎沒有這樣的標準功能暗示它可能很少有經驗的Haskellers需要，因爲他們可能知道一些更好的方法。真的嗎？什麼可以用來以更好的方式實現類似的功能？

另外，考慮到groupBy已經採取了什麼名稱呢？ :)

Answer 1

使用Data.Map作爲中間結構：

import Control.Arrow ((&&&)) 
import qualified Data.Map as M 

myGroupBy f = M.toList . M.fromListWith (++) . map (f &&& return) 

的map操作接通輸入列表與含有元素單列表成對密鑰的列表。 M.fromListWith (++)將其變爲Data.Map，當兩個項目具有相同的密鑰時連接，並且M.toList將對再次取出。

請注意，這將反轉列表，因此必要時進行調整。如果例如只想要每個組中的元素的總和，則將return和(++)替換爲其他類似monoid的操作也是容易的。

Answer 2

GHC.Exts.groupWith

groupWith :: Ord b => (a -> b) -> [a] -> [[a]] 

引入廣義列表解析的一部分：http://www.haskell.org/ghc/docs/7.0.2/html/users_guide/syntax-extns.html#generalised-list-comprehensions