Seq.groupBy 是否保持组内顺序？

Question

我想对序列进行分组，然后取组中每个元素的第一次出现。当我尝试这个时

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

我发现有时我得到的元素与 s 不同。这是预期的吗？

Answer 1

是的，这是意料之中的。序列 (seq) 不能保证是 pure。您可以定义一个序列，每次迭代时都会产生不同的值。如果你调用Seq.take 1两次，你会得到不同的结果。

例如，考虑这个序列：

open System

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

如果你调用 Seq.take 1，你可能会得到不同的结果：

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

使用 Seq.head 对您也没有帮助：

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

如果您想保证确定性行为，请改用 List。

Answer 2

正在查看 source of the groupBy implementation - 这是相关的部分：

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

它遍历源数组并将值添加到键的相应列表中。子序列的顺序直接受输入序列顺序的影响。对于相同的输入序列，我们可以期望 groupBy 到 return 相同的输出序列。这就是 groupBy.

测试的编码方式

如果您发现结果序列有变化，请检查输入序列。

Seq.groupBy 是否保持组内顺序？

Does Seq.groupBy preserve order within groups?

f#

sequences