26

Randomly experimenting with JavaScript (ES6) and reading its documentation I found out that Set maintains the insertion order of its elements.

I wonder what is the rationale behind this decision? I always thought of a set as an unordered collection. Requiring anything more would lead to a more costly implementation, whereas, in my opinion, this feature is mostly unused.

Axs
  • 397
  • 1
  • 3
  • 6
  • 4
    Because the API says it's iterable in insertion order, see e.g. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set. – jonrsharpe Apr 01 '19 at 17:11
  • Your question is not really a question. That specific implementation on that specific data may keep order. But Set does not guarantee order. So the bottom line is, do not use a set if you care about order. – nycynik Apr 01 '19 at 17:11
  • 2
    @nycynik A set does guarantee order...insertion order – charlietfl Apr 01 '19 at 17:12
  • @nycynik the ES2015 spec explicitly mandates that insertion order be used for iteration over set contents. I wouldn't write code to exploit that of course. – Pointy Apr 01 '19 at 17:12
  • *Ordered* sets can be useful. If you want to know why though, I'd recommend to search through the meeting notes of the TC39 committee and/or reach out to them directly. – Felix Kling Apr 01 '19 at 17:13
  • 3
    I don't get you all. This is a valid question. – Jonas Wilms Apr 01 '19 at 17:13
  • @felixKling probably the later, the [notes](https://github.com/tc39/tc39-notes/tree/master/es6) aren't complete – Jonas Wilms Apr 01 '19 at 17:23
  • 2
    It’s useful occasionally, not easy to implement on top of `Set`, and probably doesn’t have to come with that much overhead. When Python moved to ordered dicts, they got faster =) – Ry- Apr 01 '19 at 17:38
  • 2
    @jonrsharpe – as others noted – my question is not "why JS code runs this way", but "why JS was **designed** to run this way". – Axs Apr 01 '19 at 17:41
  • @FelixKling – thank you for the note about TC39. However, I can hardly find anything about "insertion order" in available TC39 notes. I'm looking for any reason for such spec. Maybe it was already obvious at the time EC2015 was created and required no discussion, or it's some kind of legacy assumptions? – Axs Apr 01 '19 at 17:42
  • @Axs: BTW, don't mind downvotes and welcome to SO! – georg Apr 01 '19 at 19:30

1 Answers1

34

Ordered Sets are very useful, consider for example:

unique_elements_in_order = [...new Set(some_array)]

In an "unsorted set" language, like python, you'd need a separate OrderedSet implementation for this to work.

Yes, theoretically, sets are not ordered, but mathematical abstractions, like sets, functions, numbers etc, are only tangentially related to similarly named objects we use in programming. Set is just a special kind of data structure, and it's up to the language designers to define its specific properties, like "Sets are in the insertion order" or "Sets can only contain hashable objects" etc.

As to the committee's motivation, some googling brought this

Mark S. Miller:

Mon Feb 13 22:31:28 PST 2012

There are many benefits to determinism. E started with non-deterministic iteration order, which opens a covert channel hazard. I initially changed to deterministic order merely to plug this leak. Having done so, I found it had many software engineering benefits. For example, it becomes much easier to write regression tests and to reproduce bugs by re-execution. In my implementation, it also had a minor additional space and time cost. Tyler's Waterken tables show that even the minor runtime costs I was paying were unnecessary.

Let's not introduce yet another source of non-determinism for the sake of an unmeasured efficiency. Let's measure, and if the cost turns out to be high after all, then let's reconsider determinism.

georg
  • 211,518
  • 52
  • 313
  • 390
  • Too bad that Python sets don't keep insertion order. There are [third party packages](https://pypi.org/project/ordered-set/) for this but that means that I do not have the nice set syntax at hand. – Nils Lindemann Jul 09 '20 at 14:43
  • 3
    Interesting that golang has the completely opposite philosophy – Paul Sep 29 '20 at 17:38
  • it's not that simple. Ordered Sets and Sets would need different Equality test implementation. Eg. in python {3,4} == {4,3} which is super useful and logical. JS has no real equality typeclass (trait, interface whatever) so you have to implement the check yourself anyways. – goteguru May 07 '22 at 21:26