Сохраняет ли Seq.groupBy порядок внутри групп?

Question

Я хочу сгруппировать последовательность, а затем взять первое вхождение каждого элемента в группе. Когда я попробую это

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

Я нахожу, что иногда я получаю другой элемент от s. Ожидается ли это?

Answer 1

Глядя на 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 вернет идентичные выходные последовательности. Вот как кодируются тесты для groupBy.

Если вы видите изменения в результирующих последовательностях, проверьте входную последовательность.

Answer 2

Да, это ожидается. Не гарантируется 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 

Если вы хотите, чтобы гарантировать детерминистическое b ehaviour, используйте вместо этого List.