Haskell中.NET的GroupBy函数

Question

.NET框架中的LINQ库确实有一个非常有用的函数叫GroupBy,我一直在使用它.它在Haskell中的类型看起来像

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

其目的是为了进行分类基于给定的分类功能项f到存储桶,与含有类似的产品每个桶,即(b, l),使得对于任何项目x中l,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

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

Answer 2

用作Data.Map中间结构：

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

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

该map操作将输入列表转换为与包含元素的单例列表配对的键列表。M.fromListWith (++)将其转换为 a Data.Map，当两个项目具有相同的键时连接，并M.toList再次取出对。

请注意，这会颠倒列表，因此如有必要，请进行调整。例如，如果您只想要每个组中元素的总和，那么它也很容易替换return为其他类似幺半群的操作。(++)