Seq.groupBy: сохранить исходный порядок

Dictionary<_,_> – и Seq.groupBy по расширению – похоже, перечисляют элементы в порядке вставки, однако этот порядок официально не определен (см. этот вопрос).

Вот небольшой код для демонстрации:

let groupByPreservesOrder l =
  let l2 =
    l
    |> Seq.groupBy id
    |> Seq.map fst
    |> Seq.toList
  (l = l2)

let l = List.init 1000 (fun i ->
  if i % 2 <> 0 then -(i) else i / 2)

groupByPreservesOrder l //true

Мне нужна функция группировки, которая гарантирует такое поведение. Как лучше всего (разумный, эффективный, идиоматический, ...) это сделать?

РЕДАКТИРОВАТЬ

Вот один из способов сделать это:

let groupByStable f items =
  let items = items |> Seq.map (fun x -> f x, x) |> Seq.toList
  let d = items |> Seq.groupBy fst |> dict
  items
  |> Seq.distinctBy fst
  |> Seq.map (fun (k, _) -> k, Seq.map snd d.[k])

dictionary f# enumeration
person Daniel    schedule 22.03.2012    source источник
comment
Я тупой или этот вопрос немного сбивает с толку?   -  person ChaosPandion    schedule 22.03.2012
comment
если вам это нужно гарантировано, я думаю, вам придется либо реализовать это самостоятельно, либо использовать (некоторые) Seq.order вызовы   -  person Random Dev    schedule 22.03.2012
comment
@ChaosPandion: Я не уверен. :-)   -  person Daniel    schedule 22.03.2012
comment
@ CarstenKönig: Да, это нормально. Это очевидный подход. Я здесь ловлю на творчество. Я знаю, что это не встроено ... это повод для вопроса.   -  person Daniel    schedule 22.03.2012
comment
В общем случае, когда ключи не (обязательно) идентичны элементу в исходной последовательности и ключи могут повторяться, что означает сохранение исходного порядка? Вас беспокоит порядок самих групп, порядок внутри групп или и то, и другое?   -  person kvb    schedule 22.03.2012
comment
@kvb: В моем случае ключи должны быть упорядочены по их первому появлению (порядок вставки, с точки зрения реализации Seq.groupBy), но было бы неплохо также сохранить порядок элементов.   -  person Daniel    schedule 22.03.2012

Ответы (1)


arrow_upward
2
arrow_downward

Если вы хотите, чтобы последовательность была отсортирована по первому появлению каждой клавиши, то вот один из способов сделать это:

let groupByOP f s =
    s
    |> Seq.mapi (fun i x -> i,x)
    |> Seq.groupBy (snd >> f)
    |> Seq.sortBy (snd >> Seq.map fst >> Seq.min)
    |> Seq.map (fun (k,vs) -> k, vs |> Seq.map snd)

Если вы дополнительно хотите, чтобы каждая группа была отсортирована по начальному размещению, я думаю, что что-то вроде этого должно сработать:

let groupByOP f s =
    s
    |> Seq.mapi (fun i x -> i,x)
    |> Seq.groupBy (snd >> f)
    |> Seq.map  (fun (k,vs) -> k, vs |> Seq.sortBy fst)
    |> Seq.sortBy (snd >> Seq.head >> fst)
    |> Seq.map (fun (k,vs) -> k, vs |> Seq.map snd)
person kvb    schedule 22.03.2012
comment
Дох! 15 секунд спустя с точно кодом (и не только семантически, а буквально!) - person Tomas Petricek; 22.03.2012
comment
Документы не гарантируют этого, но мы знаем, что Seq.groupBy сохраняет порядок значений внутри каждой группы, поэтому ваша первая функция должна помочь. Я добавил еще одно возможное решение своего вопроса. Он работает так же, как ваш. Вы знаете какие-нибудь практические отличия между ним и вашим? - person Daniel; 22.03.2012
comment
Из-за композиции функций у меня сильно болит голова :) Мне понадобилось 5 минут, чтобы понять, что snd ›› Seq.map fst ›› Seq.min пытался выполнить. - person Bryan Slatner; 01.12.2015