Haskell合并带索引嵌套列表 统计需执行多次访谈的采访者

方案1：无Data.Map依赖的最优实现（推荐） #

适用场景 #

输入的interviewers列表中每个采访者仅出现一次（绝大多数业务分配场景都符合这个约束）

实现思路 #

直接遍历每个采访者的分配任务，汇总其需要访谈的所有人员，直接判断总人数是否大于1即可，完全不需要中间分组的Map开销，代码更简洁性能也更高。

代码实现 #

import Data.Maybe (mapMaybe)

data Person = Person {
    name :: String
    } deriving (Show, Eq)

multiInterviews :: [[Person]] -> [(String, [Int])] -> [(String, [String])]
multiInterviews households = mapMaybe processAgent
  where
    processAgent (agent, houseIds) =
      let allInterviewees = concatMap (households !!) houseIds
          names = map name allInterviewees
      -- 符合多访谈条件就返回，否则过滤掉
      in if length names > 1 then Just (agent, names) else Nothing

验证结果 #

代入测试用例输出完全符合预期：
[("Agent1",["Alice","Bob"]),("Agent2",["Carlos","Dabir","Eashan"])]

方案2：兼容重复采访者条目的优化Map版本 #

适用场景 #

输入的interviewers可能存在同一个采访者的多条分配记录，需要合并计算总访谈人数

优化点 #

原有fromListWithDuplicates用(++)拼接列表效率很低，改成用(:)头插的方式拼接，列表拼接性能提升数倍，因结果顺序不影响正确性，不需要额外做反转。

代码实现 #

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

fromListWithDuplicates :: Ord k => [(k, v)] -> Map k [v]
fromListWithDuplicates = Map.fromListWith (flip (:)) . fmap (fmap (:[]))

multiInterviews :: [[Person]] -> [(String, [Int])] -> [(String, [String])]
multiInterviews households interviewers =
  let assignments = [ (agent, name person)
                    | (agent, houseIds) <- interviewers
                    , idx <- houseIds
                    , person <- households !! idx
                    ]
  in filter ((> 1) . length . snd) . Map.assocs $ fromListWithDuplicates assignments

额外性能优化建议 #

如果households的规模很大，列表的!!索引是O(n)的，可以提前将households转换为Data.Vector，索引访问性能提升到O(1)：

import qualified Data.Vector as V

householdsVec :: V.Vector [Person]
householdsVec = V.fromList [[Person "Alice", Person "Bob"],[Person "Carlos"],[Person "Dabir", Person "Eashan"],[Person "Fatima"]]

-- 访问时替换为 V.!
person <- householdsVec V.! idx

内容的提问来源于stack exchange，提问作者David Mertz