Tuples, what are they: read-only lists or heterogeneous data arrays?

Tim Peters tim.one at comcast.net
Fri Mar 14 06:06:25 CET 2003

[Thomas Wouters]
> ...
> Well, there is a C type 'immutable list', but its support is incomplete,
> it's not exported to Python and you don't really want to use it other
> than for its original (and still current, I believe) purpose of defying
> __cmp__ methods that mutate the list being sorted.

That hack wasn't obnoxious enough, and the internal immutable list type
doesn't exist in 2.3 anymore.  The problem was that, e.g., in

    mutator = alist.append

mutator was bound to the append method of the mutable view of the list, and
if comarison invoked mutator, a segfault could result despite all the
immutable list hair (alist.append() raises an exception during the sort
because the immutable view's append method gets invoked; capturing mutator
before the sort yields a bound method that doesn't know squat about the
immutable view).

Armin Rigo dreamt up a smaller and meaner hack that's currently thought to
be bulletproof.  It has the peculiar property of making a list appear to be
empty *during* sorting:

Python 2.3a2+ ...
>>> def c(x, y):
...     print "len(list) =", len(list)
...     return cmp(x, y)
>>> list = range(2)
>>> list.sort(c)
len(list) = 0

It also reliably complains if any attempt to mutate the list is made during
the sort:

>>> def d(x, y):
...     list.append(2)
...     return cmp(x, y)
>>> list.sort(d)
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
ValueError: list modified during sort

In fact, it doesn't stop mutations at all, or even try to!  It lets them
happen, but to temp list memory that exists only during the sort.  The
mutation is actually detected after the sort completes.  Let's see someone
try to generalize that into a feature <winK>.

More information about the Python-list mailing list