f# - (Array/List/Seq).groupBy 是否保持组内的排序顺序？

Question

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

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

Answer 1

保留排序顺序是什么意思？ 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 编写属性并查看它是否通用:

open FsCheck.Xunit
open Swensen.Unquote

[<Property>]
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)] ，分组序列不会保留排序顺序(这对我来说并不奇怪)。

<小时/>

根据更新的问题，以下是检查该问题的属性:

[<Property(MaxTest = 10000)>]
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# 的后续版本中发生变化。就我个人而言，我会采纳 the Zen of Python 的一条建议:

Explicit is better than implicit.

顺便说一句，所有转换为 F# 列表的原因是列表具有结构相等性，而序列则不然。