2.3 list reverse() bug?

[Mark Carter]

I did this:

Python 2.3 (#46, Jul 29 2003, 18:54:32) [MSC v.1200 32 bit (Intel)] on
win32

d1 = [1,2]
d2 = d1
d2.reverse()
print d1 #note: d1, not d2 [2, 1]

Surely that can't be right: d1 should still be [1,2]. If it is
"right", then I expect that many people are in for a suprise.

 

[Paul Rubin]

d1 = [1,2]
d2 = d1
d2.reverse()
print d1 #note: d1, not d2

[2, 1]

Surely that can't be right: d1 should still be [1,2]. If it is
"right", then I expect that many people are in for a suprise.

It's correct. d1 and d2 are the same list, and list.reverse reverses
in place. If you want d1 and d2 to be two separate lists, try

d1 = [1,2]
d2 = d1[:] # makes a copy of d1
d2.reverse()
print d1

 

[Erik Max Francis]

I did this:

Python 2.3 (#46, Jul 29 2003, 18:54:32) [MSC v.1200 32 bit (Intel)] on
win32

d1 = [1,2]
d2 = d1
d2.reverse()
print d1 #note: d1, not d2 [2, 1]

Surely that can't be right: d1 should still be [1,2]. If it is
"right", then I expect that many people are in for a suprise.

It's been that way since the very early versions of Python. The
..reverse method modifies the list object in place, and "assignment"
merely creates another name for the same object. In fact, .reverse's
return value of None is intended to signal exactly this to you. After
all, does this surprise you:

a = [1, 2]
b = a
b.append(3)
a [1, 2, 3]
b

[1, 2, 3]

If it does, then you need to read the Python tutorial on how Python
deals with mutable objects.

 

[Bjorn Pettersen]

(e-mail address removed) (Mark Carter) wrote in

I did this:

Python 2.3 (#46, Jul 29 2003, 18:54:32) [MSC v.1200 32 bit (Intel)] on
win32

d1 = [1,2]
d2 = d1
d2.reverse()
print d1 #note: d1, not d2 [2, 1]

Surely that can't be right: d1 should still be [1,2]. If it is
"right", then I expect that many people are in for a suprise.

Nah, not really. Why do you expect d2 = d1 to make a copy of d1 before
assigning it to d2? (and if d1 contained nested lists, should it copy them
too or just make references to them?)

In Python, assignment binds a name on the left hand side, to the object on
the right hand side... period. There is no magic going on behind the
scenes.

In your example d2 and d1 are two names for the _same_ object, [1,2], which
means that any way you mutate the object through one name will be visible
when the object is accessed through the the other name.

There is a module called copy that let you get the semantics that you're
looking for. I've never used it in my 6+ years of Python programming, since
it normally indicates the presence of flawed logic <wink>.

-- bjorn

 

[Robin Becker]

I did this:

Python 2.3 (#46, Jul 29 2003, 18:54:32) [MSC v.1200 32 bit (Intel)] on
win32

d1 = [1,2]
d2 = d1
d2.reverse()
print d1 #note: d1, not d2 [2, 1]

Surely that can't be right: d1 should still be [1,2]. If it is
"right", then I expect that many people are in for a suprise.

Really need to get a life, but anyhow here goes.

It's right. d1 & d2 both point to the same mutable object and sort is
done in place.

compare with this

d1=[1,2]
d2=d1
d2[0]='a'
d1['a', 2]

 

[Bjorn Pettersen]

I did this:

Python 2.3 (#46, Jul 29 2003, 18:54:32) [MSC v.1200 32 bit (Intel)] on
win32

d1 = [1,2]
d2 = d1
d2.reverse()
print d1 #note: d1, not d2 [2, 1]

Surely that can't be right: d1 should still be [1,2]. If it is
"right", then I expect that many people are in for a suprise.

Really need to get a life, but anyhow here goes.

It's right. d1 & d2 both point to the same mutable object and sort is
done in place.

compare with this

d1=[1,2]
d2=d1
d2[0]='a'
d1['a', 2]

that's probably less confusing when adding the hidden newline:

d1=[1,2]
d2=d1
d2[0]='a'
d1 ['a', 2]

it's-4:30am-here'ly y'rs
-- bjorn

 

[Michael Hudson]

I did this:

Python 2.3 (#46, Jul 29 2003, 18:54:32) [MSC v.1200 32 bit (Intel)] on
win32

d1 = [1,2]
d2 = d1
d2.reverse()
print d1 #note: d1, not d2 [2, 1]

Surely that can't be right: d1 should still be [1,2]. If it is
"right", then I expect that many people are in for a suprise.

Try reading this:

http://starship.python.net/crew/mwh/hacks/objectthink.html

Happy Christmas everyone!

Cheers,
mwh

 

[Arthur]

There is a module called copy that let you get the semantics that you're
looking for. I've never used it in my 6+ years of Python programming, since
it normally indicates the presence of flawed logic <wink>.

Why would you mention this in the context here?

I remain confused by this oft repeated mantra regrading the use of
copy. Are you saying that the need to copy a list indicates flawed
logic, or that doing it otherwise than by list[:] is flawed?

I have to assume the latter, but am willing to learn otherwise.

But if the latter....

Why even mention copy in this context?

But once mentioned, I need to ask then why the use of copy(list) is
flawed.

That is, are there reasons beyond the obvious, of extra keystrokes.
And speed optimization, to the extentf it might be considered material
in a particular instance.

Art

 

[Arthur]

Try reading this:

http://starship.python.net/crew/mwh/hacks/objectthink.html

Not easy sledding IMO. But one get's there.

The post that instigated the tutorial asks the question when
surprised by some behavior along the lines of this thread:

"""
Who is wrong here: my intuition or Python (2.2)?
"""

I would say,neither. It is as it is, let's assume for excellant
reason,

Which doesn't mean it is necessarily what one's naive intution first
expects.

But the response:

"""
Almost needless to say, it was the poster's intuition that was at
fault, but he is (was) far from unique in having this sort of
misconception.
"""

frankly bothers me a bit, though it is understandable somewhat in the
context of the phrasing of the posters question.

Generally speaking, it is hard to understand how someone's intutition
can be flawed. It's just an "is".

That the programming language might do slight damage to one's naive
intution is not either the fault of the programming language.
Something perhaps simply needs to be learned. Once learned, one's
intuition is happly overridden - no hard feelings.

Art

 

[Francis Avila]

Generally speaking, it is hard to understand how someone's intutition
can be flawed. It's just an "is".

<pedantic>
Clearly there is an equivocation going on here. A distinction must be made.

Intuition (your meaning): Direct or immediate perception of truth.
Intuition (link's meaning): An unconscious or implicit conjecture or
expectation.

Certainly, by the first meaning, intuition just *is*: you either percieve
the truth directly or you don't. No right or wrong. (Philosophy: Aristotle
called this "simple apprehension", and he said the same thing about it: no
right or wrong.)

By the second meaning, however, one can certainly say that the expectation
is correct or not.
</pedantic>

By the first meaning, to say "one's intution is wrong" in the face of
Pythonic behavior is certainly an arrogant thing to say, because it implies
that Python is the template from which all language behavior is wrought.
I'm not prone to attribute such to others when another explaination presents
itself, so I offer the above distinction.

HTH. Merry Christmas!

 

[Bjorn Pettersen]

Why would you mention this in the context here?

Because it's true more times than not. People who believe they need a copy,
usually comes from C++ where they've written copy constructors (ctors) as a
matter of course to have their classes work with the std lib.

I remain confused by this oft repeated mantra regrading the use of
copy. Are you saying that the need to copy a list indicates flawed
logic, or that doing it otherwise than by list[:] is flawed?

Creating an exact copy by any means normally indicates to me that something
is more complex than it needs to be. In object oriented terms, the concept
of a copy doesn't really make sense. It's easier to see on a more concrete
object, e.g. let me create an object representing my best friend:

kira = Dog(breed='Akita', age=4, color='tri-colored')

what would a copy.copy(kira) be? Where would I use the copy without being
able to use the original object?

The reason copy ctors are so frequent in C++ is simply because the language
does not have garbage collection. There just isn't a convenient way of
creating an object which outlives function scope yet doesn't leak memory.

There are of course times where a copy is needed (e.g. multi-version
scenarios) but most programmers don't bump into these very frequently...

-- bjorn

 

[Alex Martelli]

Bjorn Pettersen wrote:
...

There are of course times where a copy is needed (e.g. multi-version
scenarios) but most programmers don't bump into these very frequently...

Here's my candidate for "most frequent scenario where copies are needed":

for item in somelist:
if froobable(item):
somelist.append(frooble(item))
elif uncadable(item):
somelist.remove(item)

i.e.: you want to modify the very list you're looping on. This is one
of Python's few but important "traps and pitfalls". The simplest fix:

for item in list(somelist):
...same as above...

list(x) is my favourite way to make a shallow copy of list x, but x[:]
and copy.copy(x) are essentially equivalent.


Alex

 

[Arthur]

Bjorn Pettersen wrote:
...

Here's my candidate for "most frequent scenario where copies are needed":

for item in somelist:
if froobable(item):
somelist.append(frooble(item))
elif uncadable(item):
somelist.remove(item)

I got bit by this early on.

There are many bites to be had in the learning process.

But I agree that this is about the only time I felt the bite was *it*,
not me. A pitfall waiting to happen. Although I don't think I truly
understood the implications of mutability until I fell into it.

But this is also my approach, I guess. Not exactly writing Universe
Critical code, I tend to proceed with a light reading of the docs, and
learn by having my naive intuitions corrected - as necessary when
necessary, by finding something broken.

But there is I feel a valid point implicit in my original question.

The "I have been using Python 42 years and never imported copy" is a
very ambiguous assertion,made time and again. One can be routinely
using copies of lists and dict without ever importing copy, since
there are adequate built-in ways of making those copies, and the copy
method itself (I am never sure why or convinced it is for the best) is
not a built-in.

The assertion about copy being "overused" or potentially overused,
can mean very different things in different contexts, as I think the
early part of this thread clearly demonstrates.

Don't we need to pick one meaning for that assertion? Or make the
meaning clear, when asserted.

Art

 

[Donn Cave]

....

But the response:

"""
Almost needless to say, it was the poster's intuition that was at
fault, but he is (was) far from unique in having this sort of
misconception.
"""

frankly bothers me a bit, though it is understandable somewhat in the
context of the phrasing of the posters question.

Generally speaking, it is hard to understand how someone's intutition
can be flawed. It's just an "is".

Hm, made sense to me. But you have to take "intuition" in the
the operational sense, not the primitive, innate ability to build
on experience but the result, the ability plus the experience.
When introduced to a system that follows different rules, our
intuition will occasionally be at fault when it contributes to
an invalid assumption. Seems to me it couldn't be otherwise
(though honestly if I had much trouble with it, I don't recall
now - likely I just tend to be more interested in such things
and therefore less likely to find out about them by accident.)

That the programming language might do slight damage to one's naive
intution is not either the fault of the programming language.
Something perhaps simply needs to be learned. Once learned, one's
intuition is happly overridden - no hard feelings.

Or better informed. If you mean that in cases like the one that
started this thread, one would just have to learn to ignore one's
intuition, that doesn't sound like a happy state to me!

Donn Cave, (e-mail address removed)

 

[Arthur]

Hm, made sense to me.

Well I don't mean to make a big thing of it, but mostly because it was
in response to a poster asking whether it was him or Python. I think
the better answer is neither. His intuition is informed by ealrier
experiences which presumably does not include vast experience with
Python, and Python is as it is. And certainly a lack of intuitiveness
is not a general reproach that can be made in respect to Python, IMO.

Though it is mortal.

When introduced to a system that follows different rules, our
intuition will occasionally be at fault when it contributes to
an invalid assumption.

I guess. I came to Python with little previous programming
experience. And chose, for example, not to study operator precedence.
But to rely on what made sense based on "intuition". And was OK, 95%
of the time. The other 5% was just learning what I might have
otherwise learned by a more deliberate contemplation of the
documentation - which is certainly clear and thorough enough on the
general subject.

In some sense, making any assumption is a fault. On the other hand, I
guess I am here because my approach worked for learning Python much
better than it did when making false starts at learning other
languages.

Seems to me it couldn't be otherwise

I agree, But as a matter of degree, I like where Python is.

Or better informed. If you mean that in cases like the one that
started this thread, one would just have to learn to ignore one's
intuition, that doesn't sound like a happy state to me!

Better informed, in respect to the workings of Python. Which in the
case of operator precedence is probably generically better informed.
In the case of mutablility, I am not sure.

Art

 

[Bjorn Pettersen]

Bjorn Pettersen wrote:
...

Here's my candidate for "most frequent scenario where copies are needed":

for item in somelist:
if froobable(item):
somelist.append(frooble(item))
elif uncadable(item):
somelist.remove(item)

i.e.: you want to modify the very list you're looping on. This is one
of Python's few but important "traps and pitfalls".

That is an interesting version in that it iterates while either (1)
appending or (2) removing. I.e. froobable(frooble(item)) must always be
false to prevent infinite recursion. I don't think I've seen one of these
and it made me curious, do you have a concrete example?

The more frequently encountered algorithm is one the iterates while either
(1) mutating or (2) removing items [and a gazzilion variations you can find
in any Scheme/ML/Lisp/etc. introduction (current pet-peeve: aren't there
interesting things you could do in an introduction to those languages?)].

First the version using a copy, pretty straight forward, but only able to
deal with lists of mutable objects (see last solution below):

# O(n**2)
for item in somelist[:]: # or copy.copy(somelist) or list(somelist)
if shouldModify(item):
mutate(item) # assuming item is mutable in the Python sense
elif shouldRemove(item):
somelist.remove(item)
else:
pass

My first instinct would be a "functional" approach, creating a new correct
list and abandoning the old incorrect version:

# O(n)
tmp = []
for item in somelist:
if shouldModify(item):
tmp.append(mutate(item))
elif shouldRemove(item):
pass
else:
tmp.append(item)
somelist = tmp

; it doesn't look quite so forced in [pseudo-]lisp [I didn't
; count the parens or actually run it -- I'm sure there are
; enough lispers here to correct it <grin/wink>].
(defun frooble (lst)
(cond ((shouldModify (car lst))
(cons (mutate (car lst)) (frooble (cdr lst)))
((shouldRemove (car lst))
(frooble (cdr lst)))
(t (cons (car lst) (frooble (cdr lst))))))


if I was programming in C++ or especially C, a pure imperative approach
would probably bubble to the top (assuming the list could have variable
size without leaking memory). The fact that I wrote a bug in this code
originally, without noticing, would (at least for me) be filed in the
"don't destroy what you're iterating over" category. Alternatively, it
would indicate that you are using the wrong datastructure, i.e. an array,
instead of some sort of linked list.

# O(n**2)
i = 0
while i < len(somelist):
if shouldModify(item):
somelist = mutate(item)
i += 1
elif shouldRemove(item):
del somelist
else:
i += 1

I thought I found a solution using enumerate, but it was a mirage ;-) So
far the functional solution still seems like a winner, it's both faster
(yeah, I know, see below), and easy to verify for correctness visually (in
fact, it's set up for an inductive proof, if that exites anyone ;-)

Returning to the example in the beginning, the functional version would be

tmp = []; tail = []
for item in somelist:
if froobable(item):
tail.append(frooble(item))
elif uncadable(item):
pass
else:
tmp.append(item)
somelist = tmp + tail

provided froobable(frooble(item)) is always false. If that is not the case,
it would make a functional solution messier. (but I think that would be a
rather perverse problem space ;-)

The case I've seen come up repeatedly is a little simple, only involving
deletions of the list:

x = range(30)
for i in x:
if 5 <= i <= 10: # try to remove 5,6,7,8,9,10
x.remove(i)

the above removes 6,8,10 instead. The solution doesn't require a copy to
iterate over though, a list comprehension will do (as will calling filter
if you want to go against the times)::

x = [n for n in x if not 5 <= n <= 10]

-- bjorn

(*)
# I realize there are quite a number of Python programmers that aren't
# CS majors. Big-O notation [ O(n) and O(n**2) above ] is simply a
# measure of how bad the worst case scenario of a function would be
# (most frequently) measured in operations, and for the cases above
# I'll make another absolute statement <wink> and say that so few
# people will work with lists big enough to ever care that it's
# irrellevant largely

The quatratic complexity comes from deleting an item in the middle of the
list, since this causes all items above the empty spot to be shifted down.
Shifting all elements down is O(n), and you could end up doing it for every
element, <waving hands> O(n) work for each of the O(n) elements gives O(n**
2)</wave>

 

[Bjorn Pettersen]

[posted and mailed]



[...]

But this is also my approach, I guess. Not exactly writing Universe
Critical code, I tend to proceed with a light reading of the docs, and
learn by having my naive intuitions corrected - as necessary when
necessary, by finding something broken.

My late boss approached languages and other problems the same way, and I
never could understand how he dealt with what for me would be continous
frustration. He seemed to have no problems with it though -- allthough
there was the "what do you mean Python doesn't have a case statement?"
meltdown that almost lead to an in-house Python dialect *eek*... Now, I'm
not against a case statement in Python per se, but until one has
experienced pattern matching in SML, one can't understand how inadequate
the Pascal/C case/switch statements are -- and I _am_ against C style
switches in Python (... and we all know how much my vote counts <grin>).

I'm more the kind of person that reads the user's manual to the VCR before
ever putting a tape in (did I just date myself?). Doing language theory in
grad school, while not always the most immediately useful, is a wonderful
way to develop passionate ideas about how things ought to be (you should

But there is I feel a valid point implicit in my original question.

The "I have been using Python 42 years and never imported copy" is a
very ambiguous assertion,made time and again.

You're most certainly correct, although I don't believe it was very
ambigous when I stated it. If you look at my response to Alex, you'll see
that I really do mean that copies are virtually never needed [in the
aesthetic, not the Turing complete sense], and if you do use them you're
likely to (a) do more work, sometimes potentially _much_ more work, (b)
complexificate the algorithm making it harder to visually verify, (c) make
it _much_ harder to _prove_ correct, and (d) you're adding another entity
that you'll have to keep in memory when you're visualizing the system.

[digressing, I never thought I'd feel the need to do algorithmic proofs
until I started working for the people who give you your FICO score. The
thought that we measure personal information in (a lot of) Tera-bytes, that
we can store over 4000 individual pieces of data about a person and that a
bug could make someones life severly miserable.. No wonder that for such a
mission critical subsystem as the 'data-structure' managing this
information we wouldn't use anything but a Python code generator,
generating over 380KLoc of C++ code, SQL schemas and stored procs, etc.)].

Getting back to my point about copies, it is almost purely an aesthetic
issue. You can get working code while creating copies all over the place
without too much effort. If getting the code to work is the final goal,
there is no place for what I call "clean" code. For me, working code hasn't
been very exciting, probably since I saw the BSD sources long ago and was
utterly flummoxed when the pinnacle of what I considered a big, complex
"program" was easier to understand than what I was writing. I was
immediately convinced that only clean code can be good code, and only good
code can create exceptional systems. Being an aestethic quality, crafting
clean code is more art than engineering, but listening to coders around me
who wrote good code, and my own trial and error, I have no problem
categorically denouncing the creation of copies.

I can also categorically say that it's a really bad idea to walk to the
middle of a bridge, precariously climb up on the railing, before doing a
swan dive towards the dry riverbed several hundred feet below... but it's
really fun if you have a bungie-cord attached.

I haven't encountered any rules that didn't come with their own list of
exceptions. However, while the exceptions _are_ important, focusing on them
is perhaps misplaced. Taking an extra look when you're creating a copy has
an amazing track record in languages with gc... as does removing functions
bigger than 25x80, more than two levels of nested loops in a function, more
than two sequential loops in a function, more than three levels of
inheritance, almost all cases of multiple inheritance, classes with more
than a dozen methods, inconsistent use of whitespace, etc., etc.

Sure it is weird to want to think of such trivialities when the code is
working, but clean code makes me happy <smile>, and hey, after 20+ years of
programming, I'm still excited when I go to work and I still program after
I come home...

I hope you don't take my verbose mode as any kind of criticism -- while I
have no problem voicing my opinion about how things should be, I never
presume to tell someone else what to do (no desire, besides friends who
disagree with me are much more interesting ;-) I sincerely do not grasp
mentally however, how some people can "break path" in a new domain guided
mainly by their intuition? My intuition definitely doesn't work at that
level If you have any meta-analysis it would be very interesting to
contemplate...

[...]

Don't we need to pick one meaning for that assertion? Or make the
meaning clear, when asserted.

Of course not, this is USENET <wink>. I was going to put something here
about the quote from Winnie the Pooh about "when I say ___ I mean ___", but
googling for "Winnie the Poo" is not something anyone should do before
lunch... seriously.

Anyways, God Jul og Godt Nytt År allesammen,
-- Bjørn Steinar

 

[Terry Reedy]

The case I've seen come up repeatedly is a little simple, only involving
deletions of the list:

x = range(30)
for i in x:
if 5 <= i <= 10: # try to remove 5,6,7,8,9,10
x.remove(i)

the above removes 6,8,10 instead.

For those who don't know, in-place removal must be done in reverse.

x = range(15)
for i in range(14,-1,-1):
if 5 <= i <= 10: # try to remove 5,6,7,8,9,10
x.remove(i)[0, 1, 2, 3, 4, 11, 12, 13, 14]

tjr

 

[Andrew MacIntyre]

list(x) is my favourite way to make a shallow copy of list x, but x[:]
and copy.copy(x) are essentially equivalent.

Behaviourally yes, performance wise no.

 

[Alex Martelli]

Bjorn Pettersen wrote:
...

That is an interesting version in that it iterates while either (1)
appending or (2) removing. I.e. froobable(frooble(item)) must always be
false to prevent infinite recursion.

It doesn't have to _always_ be false -- some frooble(item)'s might be
froobable, as long as each such chain always ends in a non-froobable.

I don't think I've seen one of these
and it made me curious, do you have a concrete example?

Roughly, yes, though not quite as direct and obvious as this one. E.g.:

for listener_method in this_object.registered_listeners:
listener_method(this_object, change_hint)

where some of the registered listener methods were trying to deregister
themselves and/or register some other listener(s). This hidden case of
"mutating the list being iterated on" was a rather serious bug, but it
only led to infinite recursion (and hence to discovery) when a subtle
combination of circumstances led to addition of unlimited number of new
listeners. In a simpler variation, twisted's woven component had a
list of _weak_ references to listeners giving potential for similar
misbehavior (now fixed by the usual, simple approach of looping over a
copy of the list).

Sometimes I wonder if it might not be worth giving such "fragile"
iterables as lists and dicts the ability to emit warnings when mutated,
while they have iterators outstanding, in the ways that are likely to
misbehave (adding or removing items to a list, or keys to a dict --
some container mutations, namely change of what value corresponds to
a fixed key in a dict, are obviously benign in this sense).

My first instinct would be a "functional" approach, creating a new correct
list and abandoning the old incorrect version:

# O(n)
tmp = []
for item in somelist:
if shouldModify(item):
tmp.append(mutate(item))
elif shouldRemove(item):
pass
else:
tmp.append(item)
somelist = tmp

Sure, this is often a feasible approach (assuming mutate(item) returns
the value one wants in lieu of item, of course). It's often particularly
attractive to express it as a list comprehension:

def possibly_mutated(item):
if shouldModify(item):
mutate(item) # no assumption it returns the value
return item

somelist[:] = [ possibly_mutated(item) for item in somelist
if not shouldRemove(item) ]

(I'm changing somelist in-place, rather than just rebinding the
name, but of course depending on one's needs name rebinding can
sometimes work just as well).

# O(n**2)
i = 0
while i < len(somelist):
if shouldModify(item):

this would raise a NameError about item, so I don't think this is
the solution you wanted to post -- perhaps missing an
item = somelist
?

somelist = mutate(item)
i += 1
elif shouldRemove(item):
del somelist
else:
i += 1

Yeah, the (possibly repeated) 'del' in the middle of the list has
bad performance (even worse, of course, is the somelist.remove I
had in the original example). Might as well keep two indices (and
enumerate lets you update manually just one of them...):

itarget = 0
for isrc, item in enumerate(somelist):
if shouldModify(item):
somelist[itarget] = mutate(item)
itarget += 1
elif shouldRemove(item):
pass
else:
somelist[itarget] = item
itarget += 1
del somelist[itarget:]

possibly more elegantly expressed, if the tests can be applied
in different order without affecting their outcome, as:

itarget = 0
for isrc, item in enumerate(somelist):
if shouldRemove(item):
continue
if shouldModify(item):
item = mutate(item) # or just mutate(item) ...
somelist[itarget] = item
itarget += 1
del somelist[itarget:]

I thought I found a solution using enumerate, but it was a mirage ;-) So

Maybe one of the above ones...? They're both O(N), btw.

Returning to the example in the beginning, the functional version would be

tmp = []; tail = []
for item in somelist:
if froobable(item):
tail.append(frooble(item))
elif uncadable(item):
pass
else:
tmp.append(item)
somelist = tmp + tail

provided froobable(frooble(item)) is always false. If that is not the

You also need to assume uncadable(frooble(item)) is also always false,
otherwise the original version would remove the frooble(item) (after first
adding it) and this one wouldn't.

case, it would make a functional solution messier. (but I think that would

Not all that much, I think -- you just need to recurse on tail (the end
case for the recursion is when tail is empty), i.e. something like:

def froobanduncad(somelist):
tmp = []; tail = []
for item in somelist:
if froobable(item):
tail.append(frooble(item))
elif uncadable(item):
pass
else:
tmp.append(item)
if tail:
froobanduncad(tail)
somelist[:] = tmp + tail

of course, you DO need to change-in-place (or return the result) -- just
rebinding the argument name would be little use;-).

be a rather perverse problem space ;-)

As long as the recursion eventually terminates, not particularly, IMHO.

The case I've seen come up repeatedly is a little simple, only involving
deletions of the list:

x = range(30)
for i in x:
if 5 <= i <= 10: # try to remove 5,6,7,8,9,10
x.remove(i)

You're luckier than I am, I think -- in the buggy cases I see, there
is often some 'else:' branch to the if guarding the removal, as well
as some extra action around the removal itself -- and it's not
necessarily the case that the loop can be split into a list comprehension
first (to weed out the items that need to be removed) and a loop later (for
the actions on surviving items) because the order in which things are
performed can be significant (sometimes it's quite a bother to check
whether it is, or isn't, significant...). You can handle it with appending
nonremoved items to an empty list (unless order of execution including
possible __del__ special methods bites you...) -- but simply looping on
a copy is the simplest, least-invasive modification you can perform on
the subtly buggy code to make it non-buggy.

the above removes 6,8,10 instead. The solution doesn't require a copy to
iterate over though, a list comprehension will do (as will calling filter
if you want to go against the times)::

x = [n for n in x if not 5 <= n <= 10]

If removal is ALL you need, yes -- and in this case a LC or the like is
also far more efficient (the .remove method is a dog...;-).

# I realize there are quite a number of Python programmers that aren't
# CS majors. Big-O notation [ O(n) and O(n**2) above ] is simply a

I'm not a CS major, for example, but that doesn't imply I'm not pretty
good at O()-notation anyway...;-). (Some of us engineers aren't all
that bad, you know...).

# I'll make another absolute statement <wink> and say that so few
# people will work with lists big enough to ever care that it's
# irrellevant largely

It doesn't take much for O(N*N) to bite, in cases, such as this one,
where the multiplicative constants aren't all that different from
the O(N) possibilities. I.e., lists of a few hundreds items are very
common in many programs. Removing half the items from a list with
..remove takes about 670 usec [[on my machine, according to timeit.py]],
while a LC takes 115 usec, for a list of length 200; when the list's
length is 400, the time is 220 for the LC, 2100 for the .remove's.
These levels of performance hits can often be quite relevant, IMHO.


Alex