DSU pattern (was Re: Trouble sorting lists (unicode/locale related?))

[Alex Martelli]

Duncan Booth wrote:
   ...
>>> So maybe it's about time to change the sort() method to support a
>>> second argument
>>> 
>>> list.sort(compare=None, mapping=None)
>>> 
>>> that, if provided, would perform the DSU magic. Or was that already
>>> proposed and rejected?
>> 
>> I have not seen this proposed before, and I'm not very clear on what
>> the "compare" and "mapping" arguments are supposed to be in order to
>> let you specify any DSU.  Basically it seems you would need two
>> callables, "decorate" to be called with each item in the list (to
>> return for each item the decorated tuple) and "undecorate" to be
>> called with each decorated tuple after the sort (to return the item
>> for the result).  How do you turn that into "compare" and "mapping"?
>> 
>> 
> You don't need two callables because the sort function would be doing
> the decorating, so it knows also how to undecorate. I think the
> suggestion is that the mapping argument returns something that can be
> compared.
> 
> For example, here is a DSU function that does a not-in-place sort and
> takes a suitable mapping argument. Changing it to in-place sort is,
> of course, trivial.
> 
>>>> def DSU(aList, aMapping):
> newList = [ (aMapping(item), index, item) for (index, item)

Ah, I see -- the alleged "mapping" is in fact meant to be a
*CALLABLE*, NOT a mapping in the Python sense.  Yes, you could
get away with just one callable in this way, of course.  It
also seems to me that shoe-horning that second argument (in
practice mutually exclusive with the first one) to the sort
method, when there seem to be no real advantages to keeping
it a method, is not a great idea.  Rather, a new built-in
function appears to me to be best here -- something like:

def sort(iterable, decorate=None):
    if decorate is None:
        aux = [ (item, index, item) 
                 for index, item in enumerate(iterable) ]      
    else:
        aux = [ (decorate(item), index, item) 
                 for index, item in enumerate(iterable) ]
    aux.sort()
    return [ item for __, __, item in aux ]

so as to have no arbitrary constraints on the iterable being
a list, or the sort being necessarily in-place, when there
is no performance advantage in so doing -- and also serve the
frequent need of a non-in-place sort returning the sorted
list without any actual need for decoration.  E.g., I often
use the equivalent of:

    for key in sort(somesmalldict):
        print key, somesmalldict[key]

and it would be handy to have that little 'sort' function
built-in for all such uses.

The only downside I can see to this proposal is that Python
isn't really all that good at passing the callable decorate
argument -- one would end up with a lot of little ad hoc
functions, or lambdas, and neither is a great solution.  It's
the kind of situation where Smalltalk/Ruby shine by letting
an arbitrary block of code (albeit one only) be passed into 
any method (in Ruby, this DSU-sort would probably become a 
method of the Enumerable "module" [mix-in] -- a rather elegant
solution overall, "architecturally" nicer-looking than Python's,
although "pragmatically" we're probably abot even).


Alex