Блог

Я довольно новичок в функциональном программировании, и у меня возникли некоторые проблемы с задачей обработки списков. У меня есть коллекция записей, подобных следующей:

 type TestRec = {
    Id : string
    Amount : int }
  

Теперь я хочу удалить все элементы в списке, которые создают пару друг с другом. Например, если есть два элемента с Amount of 7 и -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: Чтобы прояснить еще кое-что, я хочу дать более реалистичное описание возможной связанной проблемы. Вы можете представить вычисление счета, где список состоит из всех позиций счета. Теперь вы хотите удалить все пары позиций накладных, которые имеют, например, одинаковый «артикул», «валюту», а цены равны нулю.

Возможно, этот пример помогает объяснить мою проблему. Я просто подумал, что может быть более «функциональный способ» решения этой проблемы, чем выполнение двух циклов над списком и удаление элементов, как я бы сделал на императивном языке.

Чтобы абстрагироваться от идеи противостоящих пар, я определяю две функции. Один для реляционного равенства (связанный) и один для определения отмен (противоположный).

Функция работает, сначала группируя связанные объекты вместе, а затем разбивая их на противоположные массивы. Затем эти результирующие массивы нарезаются в соответствии с количеством требуемых отмен. Наконец, все объединено вместе.

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

Другой вариант, вероятно, не столь функциональный, как другие предложения, но должен быть эффективным:

 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]
  

(Обновлено на основе вашего комментария)

Если вы хотите удалить последовательные отрицательные пары, вы можете просто сделать:

 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)