是否有用于分隔一系列选择的标准 F# 函数？

Question

我正在寻找一个标准的 F# 函数，该函数采用 2 项选择的序列和 returns 一对序列：

let separate (choices : seq<Choice<'T1, 'T2>>) : seq<'T1> * seq<'T2> = ...

天真的实现非常简单：

let separate choices =
    let ones =
        choices
            |> Seq.choose (function
                | Choice1Of2 one -> Some one
                | _ -> None)
    let twos =
        choices
            |> Seq.choose (function
                | Choice2Of2 two -> Some two
                | _ -> None)
    ones, twos

这工作正常，但迭代序列两次，不太理想。这个函数是在一个半标准库中定义的吗？我环顾四周，却找不到。（如果它存在，我确定它有其他名称。）

对于奖励积分，支持 3 项选择、4 项选择等的版本也不错，List、Array 等版本也不错。谢谢。

Answer 1

我找不到内置实现，但可以自己编写。它使用基于 IEnumerator<> 的方法，因此它适用于任何集合类型，但它不是最佳的（例如，数组的工作速度会比可能的慢）。顺序颠倒了（使用 ResizeArray 很容易修复，但需要更多代码）。此外，此版本并不懒惰，但可以轻松适应 Choice<'a, 'b, 'c> 和其他

let splitChoices2 (choices: Choice<'a, 'b> seq) =
    let rec inner (it: IEnumerator<_>) acc1 acc2 =
        if it.MoveNext() then
            match it.Current with
            | Choice1Of2 c1 -> inner it (c1 :: acc1) acc2
            | Choice2Of2 c2 -> inner it acc1 (c2 :: acc2)
        else
            acc1, acc2

    inner (choices.GetEnumerator()) [] []

let choices = [
        Choice1Of2 11
        Choice2Of2 "12"
        Choice1Of2 21
        Choice2Of2 "22"
    ]
choices |> splitChoices2 |> printfn "%A"

更新：基于 ResizeArray 的方法，没有颠倒的顺序和可能更便宜的枚举

let splitChoices2 (choices: Choice<'a, 'b> seq) =
    let acc1 = ResizeArray()
    let acc2 = ResizeArray()
    
    for el in choices do
        match el with
        | Choice1Of2 c1 -> acc1.Add c1
        | Choice2Of2 c2 -> acc2.Add c2

    acc1, acc2

Answer 2

这有点受到 TraverseA 的启发，但结果却大不相同。这是一个单遍解决方案（更新：然而，虽然核心算法可能是从 List 到 List 的单遍，但是让它匹配您的类型签名，并以相同的方式对结果进行排序使其成为 3*O(n)，这取决于排序和类型签名对你有多重要）

let choices = seq {Choice1Of2(1) ; Choice2Of2(2) ; Choice2Of2(3) ; Choice1Of2(4)}
let seperate' choices  = 
    let rec traverse2ChoicesA tupleSeq choices = 
        match choices with
        | [] -> fst tupleSeq |> List.rev |>Seq.ofList , snd tupleSeq |> List.rev |> Seq.ofList  
        | (Choice1Of2 f)::tl -> traverse2ChoicesA (f::fst tupleSeq, snd tupleSeq) tl
        | (Choice2Of2 s)::tl -> traverse2ChoicesA (fst tupleSeq, s::snd tupleSeq) tl
    traverse2ChoicesA ([],[]) <| List.ofSeq choices
 
seperate' choices;;

val seperate' : choices:seq<Choice<'a,'b>> -> seq<'a> * seq<'b>
val it : seq<int> * seq<int> = ([1; 4], [2; 3])

更新：需要说明的是，如果排序和 List 而不是 Seq 没问题，那么这是单次传递：

let choices = [Choice1Of2(1) ; Choice2Of2(2) ; Choice2Of2(3) ; Choice1Of2(4)]

let seperate' choices  = 
    let rec traverse2ChoicesA (tupleSeq) choices = 
        match choices with
        | [] -> tupleSeq
        | (Choice1Of2 f)::tl -> traverse2ChoicesA (f :: fst tupleSeq, snd tupleSeq) tl
        | (Choice2Of2 s)::tl -> traverse2ChoicesA (fst tupleSeq, s:: snd tupleSeq) tl
    traverse2ChoicesA ([],[]) choices

seperate' choices;;

val choices : Choice<int,int> list =
  [Choice1Of2 1; Choice2Of2 2; Choice2Of2 3; Choice1Of2 4]
val seperate' : choices:Choice<'a,'b> list -> 'a list * 'b list
val it : int list * int list = ([4; 1], [3; 2])

您可能会在使用 TraverseA 的 FSharpPlus“半标准”库中找到更通用、更高效且具有适当类型签名的内容？

是否有用于分隔一系列选择的标准 F# 函数？

Is there a standard F# function for separating a sequence of Choices?

f#