How to know if a Python type has a concept of order? What is a sequence, really?

Question

It's blowing my mind a little bit that OrderedDict in Python is not a sequence type. It has a concept of order, but it's not a sequence.

The Python docs say

There are seven sequence types: strings, Unicode strings, lists, tuples, bytearrays, buffers, and xrange objects.

For other containers see the built in dict and set classes, and the collections module. ...Most sequence types support the following operations....Sequence types also support comparisons.

Those operations corresponding to __contains__, __add__ for concatenation, __getitem__ with integers (in range(len(foo))), __len__, __min__, __slice__, index and count. __lt__ etc implement comparisons.

OrderedDicts implement some of these methods but not others, probably because the syntactic sugar for accessing items by key (as in dict) or order (as in index) is the same.

I know if something implements __iter__ I can loop through it. How can I definitely know if something has an order? I would have thought that is what is meant by "sequence", the nth item is always the nth item.

Answer 1

In a duck typing world, this is a difficult question.

Both sequences and mapping use __getitem__() to access items, using inter indexes and keys, respectively. Looking for the availability of the __getitem__() method does not tell them apart, you need to look at what the method actually does.

For the dict it is not possible to know whether the integer argument to __getitem__() is an index or a key, so it always works mapping-style.

Therefore, I think a dict is not a sequence at all, even though it supports iteration. Same applies to the set.

Looking at the collections.abc.Sequence base class may be the best test. For custom types, just make sure they are derived from this base class.

Answer 2

issubclass(list, collections.abc.Sequence)

Note this only works on built-in types.

Answer 3

The idea is that of indexing. An example with lists:

>>> ['a', 'b', 'c'][1]          # get element with index 1
'b'
>>> ['a', 'b', 'c'].index('b')  # what is the (first) index of 'b'?
1

Now with strings:

>>> 'abc'[1]
'b'
>>> 'abc'.index('b')
1

Now with Ordered Dictionaries:

>>> from collections import OrderedDict
>>> od = OrderedDict(zip(['cat', 'dog'], ['meow', 'auuu']))
>>> od[1]
(...)
KeyError: 1
>>> od.index('dog')
AttributeError: 'OrderedDict' object has no attribute 'index'

So OrderedDict preserves the order the items are added, so that it can be iterated in the same order, but it's not possible to use an index on it.