sublist copies result in behavioural anomoly

[Paul Whipp]

Hi there,

I'm new to Python so apologies if this is too naive...

I wanted to recurse down a list to do an ordered insert. All was well
until...

def splung(l,x):
if l[1:]==[]:
l[1:]=[x]
elif x>l[1]:
splung(l[1:],x)
else:
l[1:1]=[x]

foo=[1]
splung(foo,2)
foo [1, 2]
splung(foo,3)
foo [1, 2]

It took me a while to divine that the l[1:] is destroyed if its an lvalue
but returns a copy when used as an argument parameter. If that is the case,
then is there an effective way to recurse and destructively do an ordered
insert on a list?

Cheers,
Paul

 

[Alex Martelli]

Hi there,

I'm new to Python so apologies if this is too naive...

Not at all, it's a subtle trap. SOME sequences have slices that
"share" the data with the underlying sequence -- Numeric.array are
the classic examples of that. Most sequences treat slices as
(shallow) copies, so your code doesn't work on those, as you saw.
[[ _assigning_ to a slice of a mutable sequence does always mutate
the underlying sequence -- the problem is with _accessing_ ]]

So, basically, instead of "passing down" a slice such as L[1:], which
might easily be a copy, you want to pass L and the start index
separately. Doing that overtly in your case gives us:

def splung(L, x, i=1):
if L[i:] == []:
L[i:] = [x]
elif x > L:
splung(L, x, i+1)
else:
L[i:i] = [x]

Now, this, of course, is still extremely inefficient (see standard
library module bisect for an O(log N) way to do the job you're doing
in O(N) time here; even within the compass of O(N), that tail recursion,
which Python does NOT optimize away, kills your performance compared
with that of a simple loop). But at least it does work.

If you find yourself doing a lot of work with list slices that must NOT
be copies (but rather share the underlying sequence at all times), you
may want to wrap them into a 'delegating wrapper' class, whose instances
hold a reference to the underlying list and a set of indices on it that
they must affect. It _is_ a somewhat delicate job, and it's not clear
what should happen to outstanding slices when the underlying list mutates,
so I'm not going to pursue this idea further for now.


Alex