api - 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)

这绝对不是我想在我的问题特定代码中看到的东西。

我的问题是:如何最大限度地利用标准库来实现这个功能？

此外，似乎没有这样的标准函数暗示有经验的 Haskeller 可能很少需要它，因为他们可能知道更好的方法。真的吗？什么可以用来以更好的方式实现类似的功能？

此外，考虑到 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