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[i]:
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