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]