F #: уменьшить / агрегировать последовательность или список в парах - PullRequest
Новая
       4

F #: уменьшить / агрегировать последовательность или список в парах

4 голосов
/ 19 октября 2011

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

type TestRec = {
    Id : string
    Amount : int }

Теперь я хочу удалить все элементы в списке, которые строят пару друг с другом. Например, если есть два элемента с Amount из 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)

Edit: Функция, которая определяет, соответствуют ли два элемента друг другу, может быть более сложной, чем описано выше (Math.Abs). Я подумал, что это будет хороший пример со значениями Amount, но это может быть любая функция предиката.

Редактировать 2: Чтобы прояснить еще немного, я хочу дать более реалистичное описание возможной связанной проблемы. Вы можете представить расчет счета, в котором список состоит из всех позиций счета. Теперь вы хотите удалить все пары позиций счетов-фактур, которые имеют, например, один и тот же «номер товара», «валюта» и цены равны нулю.

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

Ответы [ 3 ]

1 голос
/ 19 октября 2011

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

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

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;}]
0 голосов
/ 19 октября 2011

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

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]
0 голосов
/ 19 октября 2011

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

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

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)
...