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.

Answer 2

Yes, this is expected. Sequences (seq) aren't guaranteed to be pure. You can define a sequence that will yield different values every time you iterate over them. If you call Seq.take 1 twice, you can get different results.

Consider, as an example, this sequence:

open System

let r = Random ()
let s = seq { yield r.Next(0, 9) }

If you call Seq.take 1 on that, you may get different results:

> s |> Seq.take 1;;
val it : seq<int> = seq [4]
> s |> Seq.take 1;;
val it : seq<int> = seq [1]

Using Seq.head isn't going to help you either:

> s |> Seq.head;;
val it : int = 2
> s |> Seq.head;;
val it : int = 6

If you want to guarantee deterministic behaviour, use a List instead.