Haskell 中 .NET 的 GroupBy 函数

Question

.NET框架中的LINQ库确实有一个非常有用的函数，称为GroupBy，我一直在使用它。 它在 Haskell 中的类型如下所示

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

它的目的是根据给定的分类函数 f 将项目分类到桶中，每个桶包含相似的项目，即 (b, l) 这样对于 l 中的任何项 x，fx == 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#generalized-list-compressives

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 (++) 将其转换为 Data.Map，当两个项目具有相同的键时连接，并且 M.toList 得到两人再次退出。

请注意，这会颠倒列表，因此如有必要，请进行调整。例如，如果您只需要每个组中元素的总和，也可以轻松地将 return 和 (++) 替换为其他类似幺半群的操作。