F#中如何将相同键值的多元素分组映射为指定格式嵌套列表

需求说明 #

现有两个长度一致的已排序列表：

• 键值列表：let k = [1;1;2;2;3;3]
• 数值列表：let n = [1;2;3;4;5;6]

两个列表相同索引位置的元素一一对应，要求按相同键值分组，最终生成格式为[[n1;n2;key];[n1;n2;key]...]的列表，示例输出为[[1;2;1];[3;4;2];[5;6;3]]。

实现思路 #

利用F#原生列表操作函数即可快速实现，逻辑如下：

1. 用List.zip将两个列表按索引配对，生成(键, 数值)格式的元组列表
2. 用List.groupBy按元组的键字段分组，因为原列表已排序，分组结果的顺序和原键的出现顺序完全一致
3. 遍历每个分组，提取分组内所有数值，再将当前键追加到数值列表末尾，拼接为要求的子列表格式

具体代码 #

// 输入定义
let k = [1;1;2;2;3;3]
let n = [1;2;3;4;5;6]

// 核心实现
let groupResult =
    List.zip k n
    |> List.groupBy fst
    |> List.map (fun (key, itemGroup) ->
        // 提取同组所有数值，末尾追加当前键
        (itemGroup |> List.map snd) @ [key]
    )

执行后groupResult的值就是目标结果[[1; 2; 1]; [3; 4; 2]; [5; 6; 3]]。

优化方案（可选） #

如果输入列表规模极大，因为输入本身已经是有序的，可以用List.fold单次遍历完成分组，避免List.groupBy的额外哈希计算开销，性能更高：

let groupResultOptimized =
    List.zip k n
    |> List.fold (fun acc (key, value) ->
        match acc with
        // 首次遍历初始化第一个分组
        | [] -> (key, [value]) :: acc
        // 和上一个分组键相同，把数值加入当前分组
        | (lastKey, values) :: rest when lastKey = key -> 
            (lastKey, value :: values) :: rest
        // 遇到新键，新建分组
        | _ -> (key, [value]) :: acc
    ) []
    // 翻转分组顺序对齐原列表的键顺序
    |> List.rev
    // 转换为要求的输出格式：数值列表后追加键
    |> List.map (fun (currentKey, values) -> (List.rev values) @ [currentKey])

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