Seq.groupBy: preserve original order

Question

Dictionary<_,_>–and Seq.groupBy by extension–appears to enumerate elements in insertion order, however the order is officially undefined (see this question).

Here's a bit of code to demonstrate:

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

I need a grouping function that guarantees this behavior. What is the best (consice, efficient, idiomatic, ...) way to go about it?

EDIT

Here's one way to do it:

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

if you need it *guaranteed* I guess you either have to implement it by yourself or use (some) `Seq.order` calls — Random Dev, Mar 22 '12 at 15:29
@CarstenKönig: Yes, that's fine. That's the obvious approach. I'm fishing for creativity here. I know it's not built-in...that's the impetus for the question. — Daniel, Mar 22 '12 at 15:31
In the general case where keys are not (necessarily) identical to the element in the source sequence and keys may be repeated, what does it mean to preserve the original order? Are you worried about the order of the groups themselves, the order within the groups, or both? — kvb, Mar 22 '12 at 15:35
@kvb: In my case, the keys need to be ordered by their first occurrence (insertion order, in terms of `Seq.groupBy`'s implementation), but it would be nice to preserve element order too. — Daniel, Mar 22 '12 at 15:42

score 2 · Accepted Answer · answered Mar 22 '12 at 15:56

2

If you want to ensure that the sequence is sorted by first appearance of each key, then here's one way to do it:

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)

If you additionally want each group to be sorted by initial placement, then I think something like this should work:

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)

answered Mar 22 '12 at 15:56

kvb

54,864
2
91
133

Doh! 15 seconds later with **exactly** the same code (and not just semantically same, but literally same!) – Tomas Petricek Mar 22 '12 at 15:58
The docs don't guarantee it, but we know `Seq.groupBy` preserves the order of values within each group, so your first function should do the trick. I added another possible solution to my question. It performs similarly to yours. Do you know of any practical differences between it and yours? – Daniel Mar 22 '12 at 18:29
Function composition really makes my head hurt :) It took me 5 minutes to figure out what snd >> Seq.map fst >> Seq.min was trying to accomplish. – Bryan Slatner Dec 01 '15 at 00:03

Seq.groupBy: preserve original order

1 Answers1