CODEWITHSUNDEEP
.netf#functional-programming
kongo2002
kongo2002

Reputation: 1024

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

I am fairly new to functional programming and have some problems with a list processing task. I have a collection of records like the following:

type TestRec = {
    Id : string
    Amount : int }

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

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

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

Edit: The function that determines if two elements match with each other might be more complex than described above (Math.Abs). I thought it would be a good example with the Amount values but it could be any predicate function.

Edit 2: In order to clarify some more I want to give a more realistic description of a possible related problem. You can imagine the calculation of an invoice where the list consists of all invoice positions. Now you want to remove all pairs of invoice positions that have for example the same 'article number', 'currency' and the prices evaluate to zero.

Maybe this example helps to explain my problem. I just thought there might be a more 'functional way' of solving this problem than having two loops running over the list and removing the elements like I would do in an imperative language.

Upvotes: 4

Views: 1213

Answers (3)

Daniel
Daniel

Reputation: 47904

(Updated, based on your comment)

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

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)

Upvotes: 0

gradbot
gradbot

Reputation: 13862

To abstract the idea of opposing pairs away, I define two functions. One for relational equality (related) and one to define cancellations (opposite).

The function works by first grouping the related objects together and then partitioning them into opposing arrays. These resulting arrays are then sliced according to the number of required cancellations. Finally everything is concated together.

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;}]

Upvotes: 1

desco
desco

Reputation: 16782

Another option, probably not so functional as other proposals, but should be efficient:

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]

Upvotes: 0

Related Questions