Does (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

В документации не указано явно (кроме примера), но the implementation does preserve the order of the original sequence. Было бы удивительно, если бы это не так: эквивалентные функции на других языках, о которых я знаю.

Answer 2

Что вы хотите сказать, сохранив порядок сортировки? 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>>. Таким образом, ответит ли вопрос на вопрос да или no зависит от того, что вы подразумеваете под , сохраняя порядок сортировки.

Как @Petr написал в комментариях, это легко проверить. Если вы беспокоитесь о специальных случаях, написать Property с помощью 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 #.Лично я бы принял рекомендацию от :

Явный лучше, чем неявный.

BTW, причина для всего этого преобразования в списки F # заключается в том, что списки имеют структурное равенство, а последовательности - нет.

Answer 3

Кому это нужно. Вместо сортировки, а затем группировка, только группы, а затем сортировать и упорядочение гарантировано, даже если F # реализация GroupBy в конечном счете меняется:

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