(Array/List/Seq).groupBy是否维护组内的排序顺序？

是否groupBy保证在以下代码中保留排序顺序？

x
|> Seq.sortBy (fun (x, y) -> y)
|> Seq.groupBy (fun (x, y) -> x)

通过保留排序顺序,我的意思是我们可以保证在每个分组中x,结果仍然按顺序排序y.

对于简单的例子,这是真的,

[(1, 3);(2, 1);(1, 1);(2, 3)]
|> Seq.sortBy (fun (x, y) -> y)
|> Seq.groupBy (fun (x, y) -> x)
// seq [(2, seq [(2, 1); (2, 3)]); (1, seq [(1, 1); (1, 3)])]

我想确保没有奇怪的边缘情况.

保留排序顺序是什么意思？Seq.groupBy改变序列的类型,那么你怎么能在之前和之后进行有意义的比较呢？

对于给定xs的类型seq<'a * 'b>,表达式的类型xs |> Seq.sortBy snd是seq<'a * 'b>,而表达式的类型xs |> Seq.sortBy snd |> Seq.groupBy fst是seq<'a * seq<'a * 'b>>.因此,问题的答案是肯定还是否定取决于保留排序顺序的含义.

正如@Petr在评论中写道的那样,很容易对此进行测试.如果您担心特殊情况,请使用FsCheck编写一个Property,看看它是否通用:

open FsCheck.Xunit
open Swensen.Unquote

[]
let isSortOrderPreserved (xs : (int * int) list) =
    let actual = xs |> Seq.sortBy snd |> Seq.groupBy fst

    let expected = xs |> Seq.sortBy snd |> Seq.toList
    expected =! (actual |> Seq.map snd |> Seq.concat |> Seq.toList)

在这个属性中,我已经解释了排序顺序保存的属性,意味着如果随后连接分组序列,则保留排序顺序.您的定义可能有所不同.

但是,根据这个特定的定义,运行该属性清楚地表明该属性不成立:

Falsifiable, after 6 tests (13 shrinks) (StdGen (1448745695,296088811)):
Original:
[(-3, -7); (4, -7); (4, 0); (-4, 0); (-4, 7); (3, 7); (3, -1); (-5, -1)]
Shrunk:
[(3, 1); (3, 0); (0, 0)]

---- Swensen.Unquote.AssertionFailedException : Test failed:

[(3, 0); (0, 0); (3, 1)] = [(3, 0); (3, 1); (0, 0)]
false

在这里我们看到,如果输入是[(3, 1); (3, 0); (0, 0)],分组序列不保留排序顺序(这对我来说并不奇怪).

根据更新的问题,这是一个检查该问题的属性:

[]
let isSortOrderPreservedWithEachGroup (xs : (int * int) list) =
    let actual = xs |> Seq.sortBy snd |> Seq.groupBy fst

    let expected =
        actual
        |> Seq.map (fun (k, vals) -> k, vals |> Seq.sort |> Seq.toList)
        |> Seq.toList
    expected =!
        (actual |> Seq.map (fun (k, vals) -> k, Seq.toList vals) |> Seq.toList)

确实,这个属性确实有:

Ok, passed 10000 tests.

您仍应仔细考虑是否要依赖未记录的行为,因为它可能会在以后的F#版本中发生变化.就个人而言,我会采用来自Python的Zen的一条建议:

显式优于隐式.

BTW,所有转换为F#列表的原因是因为列表具有结构相等性,而序列则没有.