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

Еще одно решение, использующее Seq.mapFold и Seq.groupBy:

let group values =
    values
    |> Seq.mapFold (fun (group, total) (name, count) -> 
        let newTotal = count + total
        let newGroup = group + if newTotal > 50 then 1 else 0
        (newGroup, name), (newGroup, if newGroup = group then newTotal else count) 
        ) (0, 0)
    |> fst
    |> Seq.groupBy fst
    |> Seq.map    (snd >> Seq.map snd >> Seq.toList)

Вызовите его следующим образом:

[   "ACE", 78
    "AMR", 3
    "Aam", 6
    "Acc", 1
    "Adj", 23
    "Aga", 12
    "All", 2
    "Ame", 4
    "Amo", 60
] 
|> group        
|> Seq.iter    (printfn "%A")

// ["ACE"]
// ["AMR"; "Aam"; "Acc"; "Adj"; "Aga"; "All"]
// ["Ame"]
// ["Amo"]

Answer 2

Операции добавления дороги.Прямой фолд с предварительно сложенными промежуточными результатами дешевле, даже если списки необходимо перевернуть после обработки.

["ACE", 78; "AMR", 3; "Aam", 6; "Acc", 1; "Adj", 23; "Aga", 12; "All", 2; "Ame", 4; "Amd", 6; "Amo", 60]
|> List.fold (fun (r, s1, s2) (t1, t2) ->
    if t2 > 50 then [t1]::s1::r, [], 0
    elif s2 + t2 > 50 then s1::r, [t1], t2
    else r, t1::s1, s2 + t2 ) ([], [], 0)
|> fun (r, s1, _) -> s1::r
|> List.filter (not << List.isEmpty)
|> List.map List.rev
|> List.rev
// val it : string list list =
//   [["ACE"]; ["AMR"; "Aam"; "Acc"; "Adj"; "Aga"; "All"]; ["Ame"; "Amd"];
//    ["Amo"]]

Answer 3

Вот рекурсивная версия, работающая почти так же, как и фолд-версии:

let groupBySums data =
    let rec group cur sum acc lst =
        match lst with
        | [] -> acc |> List.where (not << List.isEmpty) |> List.rev
        | (name, value)::tail when value > 50 -> group [] 0 ([(name, value)]::(cur |> List.rev)::acc) tail
        | (name, value)::tail -> 
            match sum + value with
            | x when x > 50 -> group [(name, value)] 0 ((cur |> List.rev)::acc) tail
            | _ -> group ((name, value)::cur) (sum + value) acc tail
    (data |> List.sortBy (fun (name, _) -> name)) |> group [] 0 []

values |> groupBySums |> List.iter (printfn "%A")

Answer 4

Я думаю, что понял.Не самый лучший код, но он работает и является неизменным.

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 в последней строке, вы получите значение суммы для каждого кластера в списке.