CODEWITHSUNDEEP
f#
Brian Berns
Brian Berns

Reputation: 17038

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

I'm looking for a standard F# function that takes a sequence of 2-choices and returns a pair of sequences:

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

A naive implementation is pretty simple:

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

This works fine, but iterates the sequence twice, which is less than ideal. Is this function defined in one of the semi-standard libraries? I looked around, but couldn't find it. (If it exists, I'm sure it goes by some other name.)

For bonus points, versions that work with 3-choices, 4-choices, and so on, would also be nice, as would versions for List, Array, etc. Thanks.

Upvotes: 2

Views: 148

Answers (2)

Martin Freedman
Martin Freedman

Reputation: 738

This is sort of inspired by TraverseA but has come out quite different. Here is a single pass solution (UPDATE: however while the core algorithm might be single pass from List to List, but getting it to match your type signature, and ordering the result the same way makes it 3*O(n), it depends how important the ordering and type signature are to you)

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

Update: To be clear, if ordering and List instead of Seq are ok then this is a single pass:

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

You might find something more general, performant and with appropriate type signature in the FSharpPlus "semi-standard" library using TraverseA?

Upvotes: 0

JL0PD
JL0PD

Reputation: 4488

I can't find builtin implementation but can write my own. It uses IEnumerator<> based approach, so it will work with any collection type but it's not optimal (e.g. arrays will work slower than could be). Order is reversed (easy to fix with ResizeArray but more code). Also this version is not lazy, but can be easily adapted to work with Choice<'a, 'b, 'c> and others

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"

Update: ResizeArray based approach without reversed order and potentially less expensive enumeration

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

Upvotes: 3

Related Questions