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