Order of insertion in sets (when parsing {})

Question

Someone asked here why when putting 1 and True in a set only 1 is kept.

This is of course because 1==True. But in which cases 1 is kept and in which cases True is kept?

Let's see:

passing a list to build the set instead of using the set notation:

>>> set([True,1])
{True}
>>> set([1,True])
{1}

seems logical: set iterates on the inner list, and doesn't add the second element because it is equal to the first element (note that set([True,1]) cannot yield 1, because set cannot know what's inside the list. It may even not be a list but an iterable)

Now using set notation:

>>> {True,1}
{1}
>>> {1,True}
{True}

It seems that in that case, the list of items is processed in reverse order (tested on Python 2.7 and Python 3.4).

But is that guaranteed? Or just an implementation detail?

`python -c 'print({1, True}, {True, 1})'` gives me `{1} {True}` on Python 3.6.1. — skovorodkin, Sep 01 '17 at 16:20
For what it's worth, `{True} == {1}` evaluates to `True`. Or to `1`. I don't know anymore. — Right leg, Sep 01 '17 at 16:22
The culprit *might* be the `BUILD_SET` bytecode instruction, but I can't find its specification. If someone cares to dig into the sources, that's where I'd look. — Right leg, Sep 01 '17 at 16:38
Nice to see you followed this up Jean, might be worth adding some python-internal or CPython tags, just a thought, I'll do a bit more digging myself when I find time — Chris_Rands, Sep 01 '17 at 17:53

score 6 · Accepted Answer · answered Sep 01 '17 at 18:54

6

The order the elements in the set literal will be inserted does not seem to be guaranteed by the language specification. However, Python 3.6 was changed so that it has the expected left-to-right evaluation order. For full details of this change, here is the issue, and also the commit that introduced the change in insertion order.

To describe the change in a bit more detail, building the set literal {True, 1} triggers the BUILD_SET opcode (with oparg equal to 2) after first pushing pointers to True and 1 onto the virtual machine's internal stack.

In Python 3.4, BUILD_SET uses the following loop to insert elements into the set (note that oparg is 2 in our case):

while (--oparg >= 0) {
    PyObject *item = POP();
    if (err == 0)
        err = PySet_Add(set, item);
        Py_DECREF(item);

Since 1 was added to the stack last, it is popped off first and is the first object inserted into the set.

In newer versions of Python (such as 3.6), the BUILD_SET opcode uses PEEK instead of POP:

for (i = oparg; i > 0; i--) {
    PyObject *item = PEEK(i);
    if (err == 0)
        err = PySet_Add(set, item);
        Py_DECREF(item);

PEEK(i) fetches the i^th item down the stack, so for {True, 1}, the object True is added to the set first.

answered Sep 01 '17 at 18:54

Alex Riley

169,130
45
262
238

Superb answer. I suspected that parsing trick but digging this out is another thing. – Jean-François Fabre Sep 01 '17 at 19:12
As I expected. So basically, the answer is "an implementation detail". Nice digging by the way, +1 – Right leg Sep 01 '17 at 23:10
the order *is* [guaranteed](https://stackoverflow.com/a/46007408/4279). Even the title of bug that you've linked says so explicitly: *"set_display evaluation order doesn't match documented behaviour"* – jfs Sep 02 '17 at 06:21
@jfs: I perhaps read the documentation too pedantically, but the specification for set displays says that the elements will be *evaluated* in left-to-right order, but is ambiguous about the order in which these evaluated elements will be added to the set. The insertion order for ordered collections, like list displays, is explicitly defined (for obvious reasons). I read the issue as being that the previous behaviour was not intuitive rather than a contradiction of the language specification, but, like I say, it's possible that my reading is unreasonable given how others have interpreted it. – Alex Riley Sep 02 '17 at 07:37

jfs · Answer 2 · 2017-09-01T20:36:39.893

Left to right order in the set display is guaranteed by the documentation:

its elements are evaluated from left to right and added to the set object

Example:

>>> def f(i, seq="left to right".split()): print(seq[i])
>>> {f(0), f(1), f(2)}
left
to
right
{None}

Therefore, {1, True} is effectively:

>>> S = set()
>>> S.add(1)
>>> S.add(True) # no effect according to docs
>>> S
{1}

The set may contain only one of True or 1 because they are duplicates from the set point of view:

>>> hash(1) == hash(True)
True
>>> 1 == True
True

It is guaranteed on Python 3 that 1 == True. See Is `False == 0 and True == 1 in Python an implementation detail or is it guaranteed by the language?:

Booleans: These represent the truth values False and True [...] Boolean values behave like the values 0 and 1, respectively, in almost all contexts, the exception being that when converted to a string, the strings "False" or "True" are returned, respectively.

If {1, True} prints {True} then it is a bug ("set_display evaluation order doesn't match documented behaviour"). The output should be the same as set([1, True]). It works as expected ({1}) on the recent pypy, jython, and cpython 2.7.13+, 3.5.3+ versions.

damisan · Answer 3 · 2017-09-01T16:25:09.480

0

From one of the most recent version, the dict preserves order as a side effect of an implementation detail. In 3.7 this behaviour may be guaranteed. Maybe it had also some effect on a set literal.

Python 3.6.2:

>>> {True,1}
{True}
>>> {1,True}
{1}
>>> set([True,1])
{True}
>>> set([1,True])
{1}

edited Sep 01 '17 at 16:25

answered Sep 01 '17 at 16:20

damisan

1,037
6
17

ok, so it seems that it was implementation defined, and no longer the case. Any official link to prove that? – Jean-François Fabre Sep 01 '17 at 16:21
1

See: https://stackoverflow.com/questions/39980323/dictionaries-are-ordered-in-python-3-6 – damisan Sep 01 '17 at 16:23
1

note that `set([True,1])` _cannot_ yield `1`, because `set` cannot know what's inside the list. It may even not be a list but a generator. – Jean-François Fabre Sep 01 '17 at 16:23
it's about order in dictionaries. Not about the order of the parsing of the set notation – Jean-François Fabre Sep 01 '17 at 16:24
EDIT: My mistake. It was `dict` not `set`. But this may be a valid starting point for the investigation. – damisan Sep 01 '17 at 16:25
1

I'm sorry I cannot upvote or accept this answer with _maybes_. But thanks for testing on 3.6. And you may be on to something here. Related: https://stackoverflow.com/questions/9792664/set-changes-element-order – Jean-François Fabre Sep 01 '17 at 16:35

Order of insertion in sets (when parsing {})

3 Answers3

Linked