这是内置的吗？

Question

我正在寻找类型的功能

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

并且Hoogle告诉我没有一个,所以我写了这个:

transpose :: (Eq a) => [[(a, b)]] -> [(a, [b])]
transpose alists = uncurry zip $ foldl combine ([], []) alists
    where combine memo new = foldl tally memo new
          tally ([], []) (k, v) = ([k], [[v]])
          tally ((ksHead:ksRest), (vsHead:vsRest)) (k, v) = 
              if k == ksHead
              then (ksHead:ksRest, (v:vsHead):vsRest)
              else (ksHead:ks, vsHead:vs)
                  where (ks, vs) = tally (ksRest, vsRest) (k, v)

按重要性排序:

1. 实际上有一个内置的Hoogle不知道吗？
2. transpose这个东西是正确的名字吗？
3. 是否有更好的(更具可读性和/或更高性能)的写作方式？

编辑

因为有人对这种味道感兴趣:

我正在写一个堆栈排名应用程序,来自用户的选票以形式出现[(Candidate, Rank)].为了通过例如Borda计数来计算获胜者,我需要Candidate通过组合这些选票来计算每个人的排名.关于更普遍的问题的评论也是受欢迎的.

Answer 1

您应该考虑使用地图数据结构,这样可以更容易:

import Data.Map (Map)
import qualified Data.Map as Map

transpose: Ord a => [(k, v)] -> Map k [v]
transpose = Map.fromListWith (++) [] . map (\(k, v) -> (k, [v])

实际上,这基本上就是文档给出的示例fromListWith.

Answer 2

transpose通常用于表示沿矩阵转置线的列表操作.事实上,Data.List.transpose正是如此.

我不能完全肯定什么你的代码做什么.说实话,这真是令人费解.你的意思是这样的吗？

import Data.List
import Data.Function
import Control.Arrow

groupByKey :: Ord a => [[(a, b)]] -> [(a, [b])]
groupByKey = map (fst . head &&& map snd) . groupBy kEq . sortBy kCmp . concat
  where
    kEq = (==) `on` fst
    kCmp = compare `on` fst

如果您正在执行此操作,请升级约束以Ord a将算法改进为O(n log n)而不是O(n ^ 2).