Does Seq.groupBy preserve order within groups?

Question

I want to group a sequence and then take the first occurrence of each element in the group. When I try this

Seq.groupBy f inSeq
|> Seq.map (fun (k,s) -> (k,s|>Seq.take 1|>Seq.exactlyOne))

I find that sometimes I get a different element from s. Is this expected?

Answer 1

Looking at the source of the groupBy implementation - here's the relevant bit:

// Build the groupings

seq |> iter (fun v ->
    let safeKey = keyf v
    let mutable prev = Unchecked.defaultof<_>
    match dict.TryGetValue (safeKey, &prev) with
    | true -> prev.Add v
    | false ->
        let prev = ResizeArray ()
        dict.[safeKey] <- prev
        prev.Add v)

It iterates through the source array and adds the values to the corresponding list for the key. The order of subsequences is directly affected by the order of the input sequence. For the same input sequence, we can expect groupBy to return identical output sequences. This is how tests are coded for groupBy.

If you're seeing variations in the resulting sequences, check the input sequence.