3

Suppose someone designs an indexable iterator class, i.e. an iterator that supports __getitem__ for (non-negative) integer indexes such as the following:

In [1] it = indexed_iter("abcdefghij")

In [2]: next(it)
Out[2]: 'a'

In [3]: next(it)
Out[3]: 'b'

In [4]: it[1]
Out[4]: ???

In [5]: it[2]
Out[5]: ???

In [6]: next(it)
Out[6]: ???

What is the most intuitive behavior for outputs 4-6? Some candidate options:

1a. it[0] is the item that would be returned by next, it[1] the item after than and so on. Additionally, the iterator is forwarded as a side-effect of indexing:

In [4]: it[1]
Out[4]: 'd'

In [5]: it[2]
Out[5]: 'g'

In [6]: next(it)
Out[6]: 'h'

1b. Same as (1a) but idempotent; the iterator is not forwarded by indexing:

In [4]: it[1]
Out[4]: 'd'

In [5]: it[2]
Out[5]: 'e'

In [6]: next(it)
Out[6]: 'c'

2a. it[0] is the first item (already or to be) returned by next, regardless of the current state of the iterator. Additionally, the iterator moves at the index position as a side-effect of indexing:

In [4]: it[1]
Out[4]: 'b'

In [5]: it[2]
Out[5]: 'c'

In [6]: next(it)
Out[6]: 'd'

2b. Same as (2a) but idempotent; the iterator's state does not change by indexing:

In [4]: it[1]
Out[4]: 'b'

In [5]: it[2]
Out[5]: 'c'

In [6]: next(it)
Out[6]: 'c'
  1. None of the above is intuitive, or at least more intuitive than the alternatives; __getitem__ should be supported at all for iterators.

This is a question about API design only; it's not about implementation, performance, memory implications or other concerns.

Improve this question
1
  • I think idea of any Iterator interface is not about providing more sugar for clients, it is all about proposing the simplest possible interface for implementation. Commented Dec 16, 2020 at 11:28

3 Answers 3

Reset to default
4

Indexing should be free of side effects. That is, I expect x[a] == x[a] for all objects x and all valid indices a. This rules out solutions 1a and 2a. Reasoning about iterator indexing in 1a sounds very similar to writing a program in the Brainfuck language.

Moving the iterator to a random-access location is useful, but that is a separate operation to consuming the iterator. Compare also the Command–Query Separation principle. For files, we call such a feature seeking. Your approach 1a involves relative seeking, 2a absolute seeking. If you want to offer such functionality, use an explicitly named method rather than overloading indexing. Which kinds of seeking can be supported depends on the object being iterated. Seeking backwards is only possible when there's an underlying collection or buffer, but not for generators. Similar concerns exist for absolute seeking. A relative forwards seek can be emulated in all cases by calling next() the appropriate number of times.

Now on to your idempotent approaches. 2b behaves like a view onto a list that also maintains an iterator state. This is fine, though I don't see the use case: if I want to index the original collection, I can just use the original collection.

1b is more interesting, since indices are now relative to the current iterator location. This e.g. lets me peek at the next elements without immediately consuming those elements. That's an unique capability not supported by your other approaches. This is also closely related to how pointers work. This 1b iterator design would be a close match for the C++ Random Access Iterator concept. One thing to consider is whether negative indices should also be allowed, e.g. to look back at previous elements. When iterating over a generator, peeking will require a buffer and is typically bounded by a constant size.

Improve this answer
2

Here's something to consider; in terms of API-design, an iterator is an abstraction of a traversal strategy. So, calling next() doesn't have to do

"a, b, c, d, e, f, g, h, i, j",

it could do

"j, i, h, g, f, ...", or,
"a, j, b, i, c, h, ...", or whatever.

So, that's an argument in favor of indexing being independent. But, as the structure being iterated over doesn't have to be indexable at all, this means that, in order to use this feature, clients need to know if the structure supports indexing (or that there's a method that can provide a random-access view into the structure). And if that's the case, then it would seem that such a client doesn't really need the iterator.

In effect, your iterator is playing two roles - it's (1) an iterator in the traditional sense, and (2) it's a random-access view.

Now, while you may or may not use the same object to implement support for both of these roles, it probably makes more sense to separate the two in the client facing API (by offering distinct methods). This will also enable you to offload some of the decision-making to clients - e.g., you could let the client specify the start-end range for the random access view. And if they want, they can also get a random-access sequence from an iterator by enumerating it in advance (you could even provide a helper method for this). This then takes away a lot of guesswork on your side.

To be clear, what I'm saying is that, in terms of API design, it doesn't seem like combining (1) & (2) is a good idea in general, although it might make sense for a particular class of problems.

Improve this answer
1

PEP 234 says

A class that wants to be an iterator should implement two methods: a next() method that behaves as described above, and an iter() method that returns self.

The two methods correspond to two distinct protocols:

  • An object can be iterated over with for if it implements iter() or getitem().

  • An object can function as an iterator if it implements next().

This looks reasonable because one can do forward seek with x times of next() operations, and the iterator state in this case is not expected to be changed by a random access operation. So 1a and 2a seems to be ruled out.

2b:

__getitem__ and next() are implemented complete independently, i.e., the index increment in next() should not affect the index used in getter in the iter object. On the other hand, however, it also means the API should be separated to two -- one for iterator another for indexing. Or even no need to implement indexing at all --- you can use "abcdefghij"[1] for index purpose already.

1b:

This does not violate the independent-protocols mentioned above, I'm interested in the specific use case of such an indexable iterator class though. Also the case -- when next() is called several times and the pos reaches to the end, then __getitem__ is called -- needs to be handled too.

Improve this answer

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.