4

In Python, how do I determine if an iterable has stable iteration order?

There's collections.Iterable abstract base class but there's no stable counterpart.

The reason I'm asking is to be able to prevent users or warn them when they pass (by mistake) iterable with unstable iteration order (dict, set, etc.) to a function where stability of iteration is crucial.

Piotr Dobrogost
  • 41,292
  • 40
  • 236
  • 366

1 Answers1

6

One thing you might be looking for is collections.Sequence. This is a bit more specific than what you want, since according to the docs a sequence "supports efficient element access using integer indices"; it's also not specific enough, since nothing explicitly guarantees that getting the same index twice has to return the same value both times. But this would suffice to distinguish lists and tuples from dicts and sets.

However, in general there is no way. In general there cannot be a way, because you can write any iterable you like and there's no requirement that you specify whether it's stable or not. E.g., you can do something like this:

>>> def f():
...     if random.random() < 0.5:
...         for a in xrange(10):
...             yield a
...     else:
...         stuff = range(10)
...         random.shuffle(stuff)
...         for a in stuff:
...             yield a
>>> list(f())
0: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> list(f())
1: [7, 0, 2, 8, 5, 1, 4, 3, 6, 9]

The fact that iterators can be written without having to declare whether they are stable or not, together with the fact that there isn't a way to tell by iterating over something whether it will iterate the same way later, means that there can be no way to tell if a given iterator is stable or not.

I would advise you to simply document that your function needs stability of iteration order. You can also explicitly check for builtin types that you know might not be stable, and raise an error on those. But there is no way to check in general for the stability of an arbitrary user-defined iterator's stability.

BrenBarn
  • 242,874
  • 37
  • 412
  • 384
  • +1. The only other thing you could really do is try to detect instability (e.g., you've seen this id before and the indices are coming in a different order) and assert, and that hardly seems worth doing. – abarnert Sep 25 '12 at 21:02
  • `collections.Sequence` is of no use here as it mandates element access using integer indices in addition to iterability. I'm looking for generic solution as I would like to avoid explicit type checking. But I agree it's probably not possible without a language providing a way to declare stability of iteration upfront. – Piotr Dobrogost Sep 25 '12 at 21:02
  • @PiotrDobrogost: You could define your own abstract base class for stable iteration order. Something like what was done in [this](http://stackoverflow.com/a/306222/355230) answer to another question. – martineau Sep 25 '12 at 21:11
  • 1
    @martineau: That's a good idea for streamlining the identification of known stable iterabletypes (or known unstable iterable types), but it still won't help you determine whether an arbitrary iterable is stable or not. – BrenBarn Sep 25 '12 at 21:15
  • 1
    As mentioned in the linked answer external users of the code can register classes on their own so that they will be handled properly. I don't think there's a practical way to do it for an arbitrary unknown class. Guess the best one could do is assume it wasn't and issue a warning suggesting to the user that they register the class of the instance being passed. – martineau Sep 25 '12 at 21:21
  • @BrenBarn: In your example both `list`s created by calling `f()` _are_ themselves stably iterable things. – martineau Sep 25 '12 at 21:30
  • @martineau: The lists are, but I just printed the lists to show what the function returns. The function itself is a generator that provides an unstable iterator. – BrenBarn Sep 25 '12 at 21:33