F # : 시퀀스 또는 목록을 쌍으로 줄이거 나 집계하십시오.

Question

저는 기능 프로그래밍을 처음 접했고 목록 처리 작업에 몇 가지 문제가 있습니다. 다음과 같은 레코드 모음이 있습니다 :

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) 

편집 : 두 가지 요소는 위에서 설명한 것보다 더 복잡 할 수 있습니다 서로 일치하는 경우를 결정하는 기능 (Math.Abs). Amount 값을 가진 좋은 예라고 생각했지만 어떤 술어 함수라도 될 수 있습니다.

편집 2 : 좀 더 명확히하기 위해 가능한 관련 문제에 대해보다 현실적인 설명을하고 싶습니다. 목록이 모든 송장 위치로 구성되어있는 송장 계산을 상상할 수 있습니다. 이제 동일한 '상품 번호', '통화'및 가격이 0 인 송장 위치 쌍을 모두 제거하려고합니다.

아마도이 예가 내 문제를 설명하는 데 도움이됩니다. 나는 목록 위에 두 개의 루프를 실행하고 명령형 언어에서하는 것처럼 요소를 제거하는 것보다이 문제를 해결하는 '기능적 방법'이 더있을 것이라고 생각했습니다.

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]