Haskell：按fst过滤并按snd对计算

问题描述：

我想要定义函数pointCounts，其中第一个成员是名称对的列表，第二个是每个名称的点数值和计数点对的返回列表。Haskell：按fst过滤并按snd对计算

我为此奋斗了几天，但我不知道如何做到这一点。

的开关输入〔实施例应该看起来像：

pointCount [("Ferp",25),("Herp",18),("Derp",15),("Ferp",25),("Herp",15),("Derp",18),("Jon",10)]

和期望的输出例如：

[("Ferp",50),("Herp",33),("Derp",33),("Jon",10)]

[我帮助某人有类似的问题，前一天]（http://stackoverflow.com/questions/22580319/f1-results-with-haskell/22580945#22580945）。我不认为这是一个重复的问题，但同样的问题正在得到解决。 – bheklilr

答

这里是另一种解决方案，只使用了比列表更奇特的东西。但是cdk的解决方案更简单，运行时间更长。

import Data.List 

pointCount :: Num a => [(String, a)] -> [(String, a)] 
pointCount [] = [] 
pointCount ((x, n):xs) = 
    let (eqx, neqx) = partition ((==x).fst) xs in 
     (x, n + (sum$ map snd eqx)) : pointCount neqx

答

我用Data.Map作为中间数据结构：

import qualified Data.Map as M 

pointCount :: Num a => [(String, a)] -> [(String, a)] 
pointCount = M.toList . foldr f M.empty 
    where f (name, val) = M.insertWith (+) name val 
      -- or pointfree 
      -- f = uncurry (M.insertWith (+))

或甚至更好（正如Daniel Wagner指出的那样）

pointCount = M.toList . M.fromListWith (+)

如果这些名字可能很长，可能会付出代价来散列它们或使用trie或其他东西。 – dfeuer

@ dfeuer（或者更确切地说，不知道什么“或什么”的人可能是）。 'Data.HashMap'存在，对于这种情况很有用。存在两个实现，请参阅'hashmap'和'unordered-containers'软件包。 –

我将'critbit'包添加到列表中，它旨在有效地索引'ByteString' /'Text'键。性能与哈希映射大致相同，但它提供了一些散列映射不能的便利函数（当然，这些函数都不需要这些函数）。 – cdk

答

这是我会怎么做，假设结果的顺序并不重要，它只是在小名单（即效率其实并不重要）用于：

import   Data.Ord  (comparing) 
import   Data.Function (on) 
import   Data.List  (groupBy, sortBy, foldl1') 

pointCount :: Num a => [(String, a)] -> [(String, a)] 
pointCount = map  (foldl1' sumSecond) 
      . groupBy ((==) `on` fst) 
      . sortBy (comparing fst) 
    where 
    sumSecond :: Num a => (String, a) -> (String, a) -> (String, a) 
    sumSecond (_, accum) (name, v) = (name, accum + v)

这是另一种可能的（类似的）解决方案，它利用求和的半群性质，找到非空列表的第一项和半群对，以及在组成两个半群时使用半群的事实semigroups和semigroupoids包）：

import   Data.Ord     (comparing) 
import   Data.Function    (on) 
import   Data.List     (groupBy, sortBy) 
import   Data.Semigroup   (First (..), Sum (..)) 
import   Data.Semigroup.Foldable (foldMap1) 
import qualified Data.List.NonEmpty as NE 
import   Control.Arrow    ((***)) 

pointCount :: Num a => [(String, a)] -> [(String, a)] 
pointCount = map  (unpackResult 
         . foldMap1 packSemigroup 
         . NE.fromList 
         ) 
      . groupBy ((==) `on` fst) 
      . sortBy (comparing fst) 
    where 
    packSemigroup :: Num a => (String, a) -> (First String, Sum a) 
    packSemigroup = First *** Sum 

    unpackResult :: Num a => (First String, Sum a) -> (String, a) 
    unpackResult = getFirst *** getSum

我可能会采用第一种解决方案，但第二种解释说明问题的本质如何被视为对半群组合的操作。该操作具体为半群同态，由unpackResult . foldMap1 packSemigroup部分表示。

Haskell：按fst过滤并按snd对计算

相关推荐