F# 按总计列出组？

Question

我有以下按第一项排序的元组列表。我想按以下方式对时间进行聚类

1. 如果元组的第二项大于 50，它将在自己的簇中。
2. 否则，对总和小于 50 的项目进行聚类。
3. 顺序不能更改。

代码:

let values =
  [("ACE", 78);
   ("AMR", 3);
   ("Aam", 6);
   ("Acc", 1);
   ("Adj", 23);
   ("Aga", 12);
   ("All", 2);
   ("Ame", 4); 
   ("Amo", 60);
   //.... 
  ]
values |> Seq.groupBy(fun (k,v) -> ???)

期望值为

[["ACE"] // 78
 ["AMR"; "Aam"; "Acc"; "Adj"; "Aga"; "All"] // 47
 ["Ame"] // 4
 ["Amo"] // 60
....]

理想情况下，我想平均分配第二组(["AMR"; "Aam"; "Acc"; "Adj"; "Aga"; "All"] 得到总和47 个)和第三个(["Ame"] 只有 4 个)。

如何在F#中实现？

---

我有以下解决方案。它使用可变变量。这不是 F# 惯用语吗？ for ... do 在 F# 中是命令式的还是某些函数构造的语法糖？

seq {
    let mutable c = []
    for v in values |> Seq.sortBy(fun (k, _) -> k) do
        let sum = c |> Seq.map(fun (_, v) -> v) |> Seq.sum
        if not(c = []) && sum + (snd v) > 50 
        then 
            yield c
            c <- [v]
        else
            c <- List.append c [v]
 }

Answer 1

我想我明白了。不是有史以来最好的代码，但可以工作并且是不可变的。

let foldFn (acc:(string list * int) list) (name, value) =
    let addToLast last = 
        let withoutLast = acc |> List.filter ((<>) last)
        let newLast = [((fst last) @ [name]), (snd last) + value]
        newLast |> List.append withoutLast

    match acc |> List.tryLast with
    | None -> [[name],value]
    | Some l ->
        if (snd l) + value <= 50 then addToLast l
        else [[name], value] |> List.append acc

values |> List.fold foldFn [] |> List.map fst

更新:由于追加可能是非常昂贵的操作，我添加了仅前置版本(仍然满足保持顺序的原始要求)。

let foldFn (acc:(string list * int) list) (name, value) =
    let addToLast last = 
        let withoutLast = acc |> List.filter ((<>) last) |> List.rev
        let newLast = ((fst last) @ [name]), (snd last) + value
        (newLast :: withoutLast) |> List.rev

    match acc |> List.tryLast with
    | None -> [[name],value]
    | Some l ->
        if (snd l) + value <= 50 then addToLast l
        else ([name], value) :: (List.rev acc) |> List.rev

注意:第 4 行仍然有 @ 运算符(在集群中创建新的名称列表时)，但是由于集群中理论上的最大名称数量为 50(如果所有它们将等于 1)，这里的性能可以忽略不计。

如果您删除最后一行的 List.map fst，您将获得列表中每个集群的总和值。