Is this "greedy" = behavior of lists guaranteed?-CodePudding

I occasionally use the "trick" to extend a list by a mapped version of itself, for example to efficiently compute powers of 2:

from operator import mul

powers = [1]
powers  = map(mul, [2] * 10, powers)

print(powers)   # prints [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]

This relies on the = immediately appending each value from map to the list, so that the map then finds it and the procedure continues. In other words, it needs to work like this:

powers = [1]
for value in map(mul, [2] * 10, powers):
    powers.append(value)

And not first compute and store the whole right-hand side like this, where powers ends up being [1, 2]:

powers = [1]
powers  = list(map(mul, [2] * 10, powers))

Is it somewhere guaranteed that it works like it does? I checked the Mutable Sequence Types documentation but it doesn't say much about it other than implying equivalence of s = t and s.extend(t). It does refer to MutableSequence, whose source code includes this:

    def extend(self, values):
        'S.extend(iterable) -- extend sequence by appending elements from the iterable'
        if values is self:
            values = list(values)
        for v in values:
            self.append(v)

    def __iadd__(self, values):
        self.extend(values)
        return self

This does suggest that it's indeed supposed to work like it does and like I want it, but some source code being what it is doesn't feel as safe as a guarantee in the documentation.

CodePudding user response：

I don't see any tests or docs that the greedy behavior is guaranteed; however, I do think it is the expected behavior and that code in the wild relies on it.

FWIW, = with lists is equivalent to list.extend(), so your "trick" boils down to:

>>> powers = [1]
>>> powers.extend(2*x for x in islice(powers, 10))
>>> powers
[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]

While I haven't found a guarantee for = or extend, we do have a guarantee that the list iterator allows mutation while iterating.¹ So, this code is on firm ground:

>>> powers = [1]
>>> for x in powers:
        if len(powers) == 10:
            break
        powers.append(2 * x)

>>> powers
[1, 2, 4, 8, 16, 32, 64, 128, 256, 512]

¹ See the second paragraph following the table at: https://docs.python.org/3/library/stdtypes.html#common-sequence-operations:

Forward and reversed iterators over mutable sequences access values using an index. That index will continue to march forward (or backward) even if the underlying sequence is mutated. The iterator terminates only when an IndexError or a StopIteration is encountered (or when the index drops below zero).