Re: [Tutor] list iteration [iteration and mutation?]

[Magnus Lycka]

Chad Crabtree wrote:
>   I wanted to chime in a moment about this.  I
> recently ran in to this very bug where I needed to
> remove items from a list.  I was making a GUI two list
> box's you click on a button to send items from one
> listbox to the other and backand forth.   Naturally
> when deleted items  I got an out of index error.  What
> I did was built a list of index numbers then iterated
> over them from highest to lowest using .reverse().  
> 
> 		self.buildlist=list(self.origin.GetSelections())
> 		for v in self.buildlist:
> 			self.destlist.append(self.emotionlist[v])
> 		self.buildlist.reverse()
> 		for v in self.buildlist:
> 			del self.emotionlist[v]

Often, it's simplest to just iterate over a reversed range, such as in:

l = <some kind of list we want to remove from>

for i in range(len(l)-1, -1, -1):
    if we_want_to_remove(l[i]):
        del l[i]

Modification of a list while we iterate over it, is probably something many
Python programmers have stumbled over at some time (but we learn...)

Here is a little study to display the phenomena in a simple case. Remove
all strings in a list that start with 'm'.

>>> l =['molly', 'monkey', 'polly', 'dolly', 'mike', 'pike', 'moo', 'mew']
>>> for name in l:
..     if name.startswith('m'):
..         l.remove(name)

>>> l
['monkey', 'polly', 'dolly', 'pike', 'mew']

Oops. This trivial implementation fails when there are adjacent strings that
start with 'm'. After the first turn in the loop, 'molly' has been removed, so
'monkey' is at index 0, but we've done that location in the list, so we go on
with index 1, which is now 'polly'. 'monkey' never gets tested.

>>> l =['molly', 'monkey', 'polly', 'dolly', 'mike', 'pike', 'moo', 'mew']
>>> for ix, name in enumerate(l):
..     if name.startswith('m'):
..         del l[ix]

>>> l
['monkey', 'polly', 'dolly', 'pike', 'mew']

Since the problem was in our test, it doesn't make a difference whether we
try to delete with "l.remove(name)" or "del l[ix]". Same result as above.

>>> l =['molly', 'monkey', 'polly', 'dolly', 'mike', 'pike', 'moo', 'mew']
>>> for name in l[:]:
..     if name.startswith('m'):
..         l.remove(name)

>>> l
['polly', 'dolly', 'pike']

This time it works, because we iterate over the copy, find all names, and
use "l.remove(name)" which doesn't care about indices to manipulate the
list. It doesn't matter that l and l[:] gets unsynched. No reversal here,
but it still works.

>>> l =['molly', 'monkey', 'polly', 'dolly', 'mike', 'pike', 'moo', 'mew']
>>> for ix, name in enumerate(l[:]):
..     if name.startswith('m'):
..         del l[ix]

Traceback (most recent call last):
  File "<pyshell#54>", line 4, in -toplevel-
    del l[ix]
IndexError: list assignment index out of range

On the other hand, if we try to do "del l[ix]" repeatedly while we iterate over
l[:] we obviously get in trouble, since l[i] and l[:][i] will point to different 
things once we start to modify l.

>>> l =['molly', 'monkey', 'polly', 'dolly', 'mike', 'pike', 'moo', 'mew']
>>> for ix in range(len(l)-1, -1, -1):
	print ix, l[ix]
	if l[ix].startswith('m'):
		del l[ix]

>>> l
['polly', 'dolly', 'pike']

Here, we use range with arguments that looks strange the first time you see
them. Reading from right to left, we have: step = -1, i.e. step backwards, 
5, 4, 3, etc, stop = -1, i.e. 0 should be the last number included in our
range, and finally, start = len[l]-1, i.e. start with the index for the last 
object in l.

By iterating backwards, we will only change location in the list for items
that we have already processed.

I think there are three lessons we can learn from this:

1. Modifying a list that we are iterating over is error prone.
2. Iterating backwards, from the end to the beginning, typically
   makes this problem go away.
3. Identifying objects by *what* they are, is often more robust
   that to identify them based on *where* they are.
   

-- 
Magnus Lycka, Thinkware AB
Alvans vag 99, SE-907 50 UMEA, SWEDEN
phone: int+46 70 582 80 65, fax: int+46 70 612 80 65
http://www.thinkware.se/  mailto:magnus at thinkware.se