sublist copies result in behavioural anomoly

[Alex Martelli]

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