F #: Reduce / group a sequence or list in pairs

Question

I am new to functional programming and have some problems with the task of list processing. I have a set of records, such as:

type TestRec = { Id : string Amount : int } 

Now I want to delete all the items in the list that pair with each other. For example, if there are two items with Amount of 7 and -7 , both items should be removed from the list. If there is a third element with Amount = 7 , it should remain in the list.

I hope you guys understand what I'm trying to do. This is what I came up with so far (but it does not work correctly):

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

Edit: A function that determines the coincidence of two elements with each other can be more complex than described above ( Math.Abs ). I thought this would be a good example with Amount values, but it could be any predicate function.

Edit 2: To clarify something else, I want to give a more realistic description of a possible related problem. You can submit an invoice calculation in which the list consists of all invoice items. Now you want to delete all pairs of account positions that have, for example, the same “article number”, “currency” and prices are valued to zero.

Perhaps this example helps explain my problem. I just thought that there might be a more “functional way” to solve this problem than having two loops over the list and removing elements like I would do in an imperative language.

Answer 1

To distract the idea of ​​opposing pairs, I define two functions. One for the relation of equality (related) and one for the definition of cancellation (opposite).

The function works by first grouping related objects together and then breaking them into opposite arrays. These resulting arrays are then sliced ​​according to the number of cuts required. Finally, everything is agreed.

 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 

Outputs

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

Answer 2

(Updated based on your comment)

If you want to remove consecutive negation pairs, you can simply do:

 let removePairs f items = let rec loop acc = function | a :: b :: t when fab -> 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

Another option may not be as functional as other suggestions, but should be effective:

 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 ix -> {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]