如何实现Elm语言中指定签名的groupBy分组函数？

需求说明 #

需要实现一个名为groupBy的方法，签名如下：

groupBy : (a -> b) -> List a -> List ( b, List a )

该方法接收一个分组依据函数和一个元素列表，返回(b, List a)形式的元组列表。其中：

• b是列表元素a经过分组函数处理后得到的值，作为分组的key
• List a是所有经分组函数处理后得到相同b值的原元素集合，作为对应key的value

测试用例 #

• groupBy .x [ { x = 1 } ] --> [(1, [{x = 1}])]
• groupBy (modBy 10) [ 11, 12, 21, 22 ] --> [(1, [11, 21]), (2, [12, 22])]
• groupBy identity [] --> []

注：identity是Elm内置函数，作用是返回输入值本身。当传入它作为分组函数时，空列表返回空列表；若列表非空，会把每个元素作为单独的key，对应value是仅包含该元素的列表（比如groupBy identity [1,2,1]会返回[(1, [1,1]), (2, [2])]）

当前尝试的代码 #

我已经写出了部分代码，但卡在最后一步无法继续：

groupBy : (a -> b) -> List a -> List ( b, List a )
groupBy criteria list =
    let
        unique lst = 
            List.foldl
                (\a uniques ->
                    if List.member a uniques then
                        uniques
                    else
                        uniques ++ [a]
                )
                [] 
                lst
        keys = 
            list
                |> List.map criteria
                |> unique
        pairs =
            List.map2 Tuple.pair (List.map criteria list) list

        filtered_list =
            List.filterMap (\x -> criteria x == keys) 
        group kl lst =
            case kl of
                [] -> []
                k::ks ->
                    (k, []):: (result els)
    in
        []
    -- Debug.todo "Implement groupBy in Util.elm"

在Elm REPL中运行以下代码可以得到(b, a)形式的元组列表：

List.map2 Tuple.pair (List.map (modBy 10) [ 11, 12, 21, 22 ]) [ 11, 12, 21, 22 ]

结果为：[(1,11),(2,12),(1,21),(2,22)]

其中unique函数可以正确提取列表中的唯一元素，pairs能生成键值对，但我不知道如何把相同key的元素合并成列表，得到最终需要的(b, List a)结构。

解决方案 #

可以基于已有的keys和原列表来构建结果：对于每个唯一key，过滤出原列表中所有经分组函数处理后等于该key的元素，然后组成元组即可。

修改后的完整代码如下：

groupBy : (a -> b) -> List a -> List ( b, List a )
groupBy criteria list =
    let
        unique lst = 
            List.foldl
                (\a uniques ->
                    if List.member a uniques then
                        uniques
                    else
                        uniques ++ [a]
                )
                [] 
                lst
        keys = 
            list
                |> List.map criteria
                |> unique
        -- 对每个key，过滤出原列表中符合条件的元素
        buildGroup key =
            (key, List.filter (\item -> criteria item == key) list)
    in
        List.map buildGroup keys

代码解释 #

1. unique函数保持不变，用于提取所有唯一的分组key；
2. buildGroup函数接收一个key，返回(key, 符合条件的元素列表)的元组，通过List.filter筛选出原列表中所有经criteria处理后等于当前key的元素；
3. 最后用List.map遍历所有唯一key，生成最终的分组列表。

优化点（可选） #

原unique函数使用++拼接列表，效率较低（每次拼接都是O(n)操作），可以改用::并最后反转列表来提升性能：

unique lst = 
    List.foldl
        (\a uniques ->
            if List.member a uniques then
                uniques
            else
                a :: uniques
        )
        [] 
        lst
    |> List.reverse

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