F＃：成對減少/聚合一個序列或列表

Question

我對函數式編程相當新穎，並且在列表處理任務時遇到了一些問題。我有類似下面記錄的集合：

type TestRec = { 
    Id : string 
    Amount : int } 

現在我想刪除列表中的該相互建立一個對所有項目。例如，如果有Amount7和-7兩個項目項目應從列表中刪除。如果有第三個元素Amount = 7它應該留在列表中。

我希望你們能理解我想要做的事情。這是我想出了這麼遠（但它不正常工作尚未）：

let removeDoubles items = 
    items 
    |> Seq.groupBy (fun i -> Math.Abs(i.Amount)) 
    |> Seq.map snd 
    |> Seq.filter (fun i -> Seq.length i = 1) 

編輯： ，決定是否兩個元素互相一致，可能會比上述更復雜的功能（ Math.Abs）。我認爲這將是Amount值的一個很好的例子，但它可以是任何謂詞函數。

編輯2： 爲了澄清更多我想給一個可能相關的問題更現實的描述。您可以想象發票的計算，其中列表包含所有發票頭寸。現在，您要刪除所有具有相同「商品編號」，「貨幣」和價格評估爲零的發票頭寸對。

也許這個例子有助於解釋我的問題。我只是認爲，解決這個問題可能有一種更「功能性的方式」，而不是像在命令式語言中那樣使用兩個循環遍歷列表並刪除元素。

Answer 1

爲了提取反對對象的想法，我定義了兩個函數。一個用於關係平等（相關），另一個用於定義取消（相反）。

該功能的工作原理是首先將相關對象分組在一起，然後將它們分區到相反的數組中。這些結果數組然後根據所需取消的數量進行分割。最後，所有內容一起拼接起來。

type TestRec = { 
    Id : string; 
    Amount : int; 
} 

let removeDoubles items related opposite = 
    items 
    |> Seq.groupBy related 
    |> Seq.map (fun (key, values) -> 
     let t, f = values |> Seq.toArray |> Array.partition opposite 
     if t.Length > f.Length then 
      t.[.. t.Length - f.Length - 1] 
     else 
      f.[.. f.Length - t.Length - 1] 
     ) 
    |> Seq.concat 

let items = [ 
    {Id="first";Amount=7}; 
    {Id="seconds";Amount=7}; 
    {Id="we";Amount=4}; 
    {Id="negative";Amount= -7} 
    ] 

let test = removeDoubles 
       items 
       (fun x -> abs x.Amount) 
       (fun x -> x.Amount > 0) 

printf "%A" test 

System.Console.ReadLine() |> ignore 

輸出

seq [{Id = "first"; 
     Amount = 7;}; {Id = "we"; 
        Amount = 4;}] 

Answer 2

（更新，根據您的評論）

如果要刪除連續否定對，你可以簡單地做：

let removePairs f items = 
    let rec loop acc = function 
    | a :: b :: t when f a b -> loop acc t 
    | h :: t -> loop (h::acc) t 
    | [] -> List.rev acc 
    loop [] (List.ofSeq items) 

items |> removePairs (fun {Amount=amtA} {Amount=amtB} -> amtA + amtB = 0) 

Answer 3

另一種選擇，恐怕不是那麼功能爲其他提案，但應高效率：

type R = { 
    Id : int 
    Amount : int 
    } 
let mkR id amount = {Id = id; Amount = amount}  

open System.Collections.Generic 
let removePairs s : seq<R> = 
    // stores mapping: key -> corresponding nodes in result list 
    let seen = Dictionary<_, LinkedList<LinkedListNode<R>>>() 
    // accumulates result 
    let list = LinkedList<R>() 

    // check if paired element was already met 
    // if yes - remove its first appearance from the result list 
    let tryEliminate ({Amount = a} as el) = 
     // paired element will have different sign 
     let key = -a 
     match seen.TryGetValue key with 
     | true, existing -> 
      list.Remove(existing.First.Value) // Remove(LinkedListNode) works in O(1) 
      existing.RemoveFirst() 
      if existing.Count = 0 then seen.Remove key |> ignore 
      true 
     | _ -> 
      false 

    let append ({Amount = a} as el) = 
     let newNode = list.AddLast(el) 
     let l = 
      match seen.TryGetValue a with 
      | true, existing -> existing 
      | false, _ -> 
       let nodes = LinkedList() 
       seen.Add(a, nodes) 
       nodes 
     l.AddLast(newNode) |> ignore 

    for el in s do 
     if not (tryEliminate el) then append el 

    list :> _ 

let check source expected = 
    let result = 
     source 
     |> List.mapi (fun i x -> {Id = i; Amount = x}) 
     |> removePairs 
     |> List.ofSeq 
    if (result <> expected) then failwithf "Expected: %A, actual %A" expected result 

check [1;1;-1;2] [mkR 1 1; mkR 3 2] 
check [1;1;-1;-1] [] 
check [7;7;4] [mkR 0 7; mkR 1 7; mkR 2 4]