Why does collections.MutableSet not bestow an update method?

Question

When implementing a class that works like a set, one can inherit from collections.MutableSet, which will bestow the new class with several mixin methods, if you implement the methods they require. (Said otherwise, some of the methods of a set can be implemented in terms of other methods. To save you from this boredom, collections.MutableSet and friends contain just those implementations.)

The docs say the abstract methods are:

__contains__, __iter__, __len__, add, discard

and that the mixin methods are

Inherited Set methods and clear, pop, remove, __ior__, __iand__, __ixor__, and __isub__

(And, just to be clear that update is not part of the "Inherited Set methods, Set's mixin methods are:

__le__, __lt__, __eq__, __ne__, __gt__, __ge__, __and__, __or__, __sub__, __xor__, and isdisjoint

However, Set refers to an immutable set, which naturally would not have update.)

Why is update not among these methods? I find it surprising — unintuitive even — that set contains this method, but collections.Set does not. For example, it causes the following:

In [12]: my_set
Out[12]: <ms.MySet at 0x7f947819a5d0>

In [13]: s
Out[13]: set()

In [14]: isinstance(my_set, collections.MutableSet)
Out[14]: True

In [15]: isinstance(s, collections.MutableSet)
Out[15]: True

In [16]: s.update
Out[16]: <function update>

In [17]: my_set.update
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
<ipython-input-17-9ed968a9eb18> in <module>()
----> 1 my_set.update

AttributeError: 'MySet' object has no attribute 'update'

Perhaps stranger is that MutableMapping does bestow an update method, while MutableSet does not. AFAICT, the source code does not mention any reason for this.

Answer 1

The API for MutableSet was designed by Guido van Rossum. His proposal is articulated in PEP 3119's section on for Sets. Without elaboration, he specified that:

"This class also defines concrete operators to compute union, intersection, symmetric and asymmetric difference, respectively __or__, __and__, __xor__ and __sub__"

...

"This also supports the in-place mutating operations |=, &=, ^=, -=. These are concrete methods whose right operand can be an arbitrary Iterable, except for &=, whose right operand must be a Container. This ABC does not provide the named methods present on the built-in concrete set type that perform (almost) the same operations."

There is not a bug or oversight here; rather, there is a matter of opinion about whether you like or don't like Guido's design.

The Zen of Python has something to say about that:

• There should be one-- and preferably only one --obvious way to do it.
• Although that way may not be obvious at first unless you're Dutch.

That said, abstract base classes were designed to be easy to extend. It is trivial to add your own update() method to your concrete class with update = Set.__ior__.

Answer 2

Update:

Raymond Hettinger himself responded to the bug report you raised, as described below, the Set Abstract Base Class uses the operators, not the named methods.

---

Original Response:

Raymond Hettinger wrote a recipe for an OrderedSet based on the MutableSet Abstract Base Class, (see code blob at the bottom.) But he does not use the update method. Instead, he uses the |= operator, which the update method calls. I don't know if your bug report will get any traction, because it might break preexisting code that only expects the current implementation.

You can, however, write an abstract base class that does expect method to include more methods you insist be implemented:

import abc
import collections

class MyMutableSet(collections.MutableSet):
    @abc.abstractmethod
    def update(self, other):
        raise NotImplementedError

MyMutableSet.register(set)

Then the following works:

>>> isinstance(set('abc'), MyMutableSet)
True

And if we attempt to subclass our new Abstract Base Class (see recipe below) instead of MutableSet:

>>> s = OrderedSet()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: Can't instantiate abstract class OrderedSet with abstract methods update

So we see we can require the update method in this way, if we require our users to subclass our customized Abstract Base Class.

This does highlight the fact that you should be careful to only expect the methods implemented by the abstract base class you're using if you want to test for instance, and do not assume you have every method in the builtin (in this case, set). set is registered as a subclass of MutableSet, not the other way around.

Implementing Update in the ABC

If you want to implement update in the abstract base class, since it expects __ior__:

def update(self, other): 
    self |= other

It shouldn't break pre-existing code to do this. But if you're going to do that, you may as well implement all of the other methods too.

---

Raymond's recipe, adapted for our purposes:

import collections

# class OrderedSet(collections.MutableSet):
class OrderedSet(MyMutableSet):
    def __init__(self, iterable=None):
        self.end = end = [] 
        end += [None, end, end]         # sentinel node for doubly linked list
        self.map = {}                   # key --> [key, prev, next]
        if iterable is not None:
            self |= iterable
    def __len__(self):
        return len(self.map)
    def __contains__(self, key):
        return key in self.map
    def add(self, key):
        if key not in self.map:
            end = self.end
            curr = end[1]
            curr[2] = end[1] = self.map[key] = [key, curr, end]
    def discard(self, key):
        if key in self.map:        
            key, prev, next = self.map.pop(key)
            prev[2] = next
            next[1] = prev
    def __iter__(self):
        end = self.end
        curr = end[2]
        while curr is not end:
            yield curr[0]
            curr = curr[2]
    def __reversed__(self):
        end = self.end
        curr = end[1]
        while curr is not end:
            yield curr[0]
            curr = curr[1]
    def pop(self, last=True):
        if not self:
            raise KeyError('set is empty')
        key = self.end[1][0] if last else self.end[2][0]
        self.discard(key)
        return key
    def __repr__(self):
        if not self:
            return '%s()' % (self.__class__.__name__,)
        return '%s(%r)' % (self.__class__.__name__, list(self))
    def __eq__(self, other):
        if isinstance(other, OrderedSet):
            return len(self) == len(other) and list(self) == list(other)
        return set(self) == set(other)


if __name__ == '__main__':
    s = OrderedSet('abracadaba')
    t = OrderedSet('simsalabim')
    print(s | t)
    print(s & t)
    print(s - t)