20

Scala 有一个groupBy关于列表的函数，它接受一个从列表项中提取键的函数，并返回另一个列表，其中项是由键和产生该键的项列表组成的元组。换句话说，是这样的：

List(1,2,3,4,5,6,7,8,9).groupBy(_ % 2)
// List((0, List(2,4,6,8)), (1, List(1,3,5,7,9)))

（实际上，它看起来在当前版本中提供了一个Map，但这并不重要）。C# 有一个更有用的版本，可让您同时映射值（例如，如果您的键函数只是提取元组的一部分，则非常有用）。

Haskell 有一个groupBy，但它有些不同 - 它根据一些比较函数对事物的运行进行分组。

在我去写之前，groupByHaskell 中是否有与 Scala 相当的东西？Hoogle 没有任何我期望签名看起来像的东西（如下），但我可能只是弄错了。

Eq b => (a -> b) -> [a] -> [(b,[a])]
4

7 回答 7

16

您可以很容易地自己编写函数，但如果您想要一个有效的解决方案，您需要对分类器函数的结果放置一个OrdorHashable约束。例子：

import Control.Arrow ((&&&))
import Data.List
import Data.Function

myGroupBy :: (Ord b) => (a -> b) -> [a] -> [(b, [a])]
myGroupBy f = map (f . head &&& id)
                   . groupBy ((==) `on` f)
                   . sortBy (compare `on` f)

> myGroupBy (`mod` 2) [1..9]
[(0,[2,4,6,8]),(1,[1,3,5,7,9])]

您还可以使用哈希映射，Data.HashMap.Strict而不是对预期的线性时间进行排序。

于 2013-03-14T14:36:33.043 回答
3

具体来说，以下应该有效：

scalaGroupBy f = groupBy ((==) `on` f) . sortBy (comparing f)

模这不会让你得到f每个组的结果，但如果你真的需要它，你可以随时使用

map (\xs -> (f (head xs), xs)) . scalaGroupBy f
于 2013-03-14T15:40:40.440 回答
2

这不是 List 库中的函数。

你可以把它写成 sortBy 和 groupBy 的组合。

于 2013-03-14T14:39:36.780 回答
0

trace输入af表明，使用@Niklas 解决方案，f对于长度为 2 或更长的任何列表中的每个元素，都会评估 3 次。我冒昧地对其进行了修改，以便f仅将其应用于每个元素一次。然而，目前尚不清楚创建和销毁元组的成本是否低于f多次评估的成本（因为f可以是任意的）。

import Control.Arrow ((&&&))
import Data.List
import Data.Function

myGroupBy' :: (Ord b) => (a -> b) -> [a] -> [(b, [a])]
myGroupBy' f = map (fst . head &&& map snd)
                   . groupBy ((==) `on` fst)
                   . sortBy (compare `on` fst)
                   . map (f &&& id)
于 2013-03-15T15:29:58.407 回答
0

此解决方案将按 (fx) 中断和分组，无论它是否已排序

f = (`mod` (2::Int))

list = [1,3,4,6,8,9] :: [Int]


myGroupBy :: Eq t => (b -> t) -> [b] -> [(t, [b])]

myGroupBy f (z:zs) = reverse $ foldl (g f) [(f z,[z])] zs
  where
    -- folding function                        
    g f ((tx, xs):previous) y = if (tx == ty)
                           then (tx, y:xs):previous
                           else (ty, [y]):(tx, reverse xs):previous
        where ty = f y                        

main = print $ myGroupBy f list

结果：[(1,[1,3]),(0,[4,6,8]),(1,[9])]

于 2013-03-27T10:03:40.653 回答
0

由于 ScalagroupBy返回一个不可变的HashMap，它不需要排序，相应的 Haskell 实现也应该返回 a HashMap。

import qualified Data.HashMap.Strict as M

scalaGroupBy :: (Eq k, Hashable k) => (v -> k) -> [v] -> M.HashMap k [v]
scalaGroupBy f l = M.fromListWith (++) [ (f a, [a]) | a <- l]
于 2020-10-05T08:13:31.430 回答
0

我们还可以then group by在列表理解中使用类似 SQL 的语法，这需要TransformListComp语言扩展。

由于 ScalagroupBy返回 a Map，我们可以调用fromDistinctAscList将列表推导转换为 a Map。

$ stack repl --package containers

Prelude> :set -XTransformListComp
Prelude> import Data.Map.Strict ( fromDistinctAscList, Map )
Prelude Data.Map.Strict> import GHC.Exts ( groupWith, the )
Prelude Data.Map.Strict GHC.Exts> :{
Prelude Data.Map.Strict GHC.Exts| scalaGroupBy f l =
Prelude Data.Map.Strict GHC.Exts|   fromDistinctAscList
Prelude Data.Map.Strict GHC.Exts|     [ (the key, value)
Prelude Data.Map.Strict GHC.Exts|     | value <- l
Prelude Data.Map.Strict GHC.Exts|     , let key = f value
Prelude Data.Map.Strict GHC.Exts|     , then group by key using groupWith
Prelude Data.Map.Strict GHC.Exts|     ]
Prelude Data.Map.Strict GHC.Exts| :}
Prelude Data.Map.Strict GHC.Exts> :type scalaGroupBy
scalaGroupBy :: Ord b => (t -> b) -> [t] -> Map b [t]
Prelude Data.Map.Strict GHC.Exts> scalaGroupBy (`mod` 2) [1, 2, 3, 4, 5, 6, 7, 8, 9]
fromList [(0,[2,4,6,8]),(1,[1,3,5,7,9])]

与 Scala 的唯一区别groupBy是上面的实现返回一个排序映射而不是哈希映射。有关返回哈希映射的实现，请参阅我在https://stackoverflow.com/a/64204797/955091上的其他答案。

于 2021-01-18T22:14:24.247 回答