如何递归实现按键分组键值对列表元素（不使用库函数）

问题场景 #

给定两个列表：

l1 = [k1, k2, k3] 
l2 = [(k1, x1), (k2, x2), (k1, x3), (k2, x4), (k5, x5), ...]

要把每个键对应的x值归组到列表里，最终得到：

l = [(k1, [x1, x3]), (k2, [x2, x4]), (k5, [x5]), ...]

要求不用库函数，纯递归实现。

原代码的问题 #

你写的递归函数有几个明显问题：

• 参数类型不对：l1是单个键的列表，但你把第一个参数写成了键值对列表(k, value):tail1，类型不匹配。
• 递归逻辑混乱：没理清“收集单个键的所有值”和“切换下一个键”的流程，也没处理l2里出现l1以外键的情况。
• 终止条件不全：既没考虑l2遍历完但l1还有键的情况，也没处理l1遍历完后l2剩余键的分组。

递归实现的正确思路 #

可以拆成三个递归函数配合完成：

1. 收集单个键的所有值：递归扫l2，把目标键的所有值挑出来，同时返回没处理的剩余l2（避免重复遍历）。
2. 处理剩余键的分组：当l1的键都处理完后，递归把l2里剩下的键自动分组。
3. 主函数遍历l1：逐个处理l1的键，调用收集函数拿对应值，再递归处理剩下的键和剩余l2。

完整递归代码 #

-- 辅助函数：收集单个键k在l2中的所有值，返回（值列表，剩余未处理的l2）
collectValues :: Eq a => a -> [(a, b)] -> ([b], [(a, b)])
collectValues _ [] = ([], [])
collectValues k ((k1, x):rest)
    | k == k1   = let (vals, remaining) = collectValues k rest in (x:vals, remaining)
    | otherwise = let (vals, remaining) = collectValues k rest in (vals, (k1, x):remaining)

-- 辅助函数：处理l1遍历完后，剩余l2的键值对分组
groupRemaining :: Eq a => [(a, b)] -> [(a, [b])]
groupRemaining [] = []
groupRemaining ((k, x):rest) =
    let (vals, remaining) = collectValues k rest
    in (k, x:vals) : groupRemaining remaining

-- 主递归函数：按l1的键分组l2的值
groupByKeys :: Eq a => [a] -> [(a, b)] -> [(a, [b])]
groupByKeys [] l2 = groupRemaining l2
groupByKeys (k:ks) l2 =
    let (vals, remaining) = collectValues k l2
    in (k, vals) : groupByKeys ks remaining

代码运行逻辑 #

1. collectValues：递归遍历l2，碰到和目标键匹配的项就把值加入结果列表，不匹配的项保留到剩余列表中，最后返回收集到的值列表和未处理的剩余l2。
2. groupRemaining：当l1的键全部处理完成后，每次取l2的第一个键，用collectValues收集它的所有对应值，再递归处理剩余的键值对，自动完成剩余键的分组。
3. groupByKeys：主函数逐个遍历l1的键，收集完当前键的所有值后，递归处理剩余的键和剩余l2；如果l1已空，就交给groupRemaining处理l2中剩下的键值对。

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