# sublist copies result in behavioural anomoly

Discussion in 'Python' started by Paul Whipp, Nov 7, 2003.

1. ### Paul WhippGuest

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

Paul Whipp, Nov 7, 2003

2. ### Alex MartelliGuest

Paul Whipp wrote:

> 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

Alex Martelli, Nov 7, 2003