Python's simplicity philosophy

[Andrew Dalke]

Paul Rubin:
> I think that decision is a little too CPython-centric.  Some other
> Python implementation (maybe even Jython) might like to implement the
> list.sort method by calling some other sort routine (like the one
> already in the library for that language)

That's not a problem with Jython, since Java has a stable sort, see
http://java.sun.com/j2se/1.4.2/docs/api/java/util/Collections.html#sort(java
.util.List)

There was a OCaml implemenation of a Python variant, called
Vyper.  OCaml has a stable sort
  http://caml.inria.fr/devtools/doc_ocaml_classic/Array.html

C++'s STL include a stable_sort
  http://www.codeguru.com/cpp/stlguide/stable_sort.shtml

C# doesn't appear to have a stable sort.

WWPyPyD?  (What Would PyPy do?)  I don't know.

> Also, someone might want to
> implement an indexable class that isn't a list (maybe it's a disk file
> or something) and want to give it a sort method that cannot work by
> sucking the keys into memory and calling timsort (maybe there are too
> many keys to fit in memory, so external methods must be used).

There are a couple of misconceptions here:

  - sort is a method on lists.  It only works on lists.  Unlike STL,
     which distinguishes between a container and an algorithm, there
     is no way to apply sort directly to anything which isn't a list.  Your
     case (using sort on "a disk file or something") cannot occur.

  - All the keys must fit in memory.  This is a consequence of being
     a list.  (The keys may depend on other resource to do the
     comparison.)  C++ is different in this regard as well.

  - The sort only rearranges references so there's no way to use
     sort to directly sort the values on disk as you could in C++.

> It may
> turn out to work best to use some nonstable sorting method, but then
> the behavior will be inconsistent with list.sort and that makes more
> cruft that the application programmer has to remember.

It may have, but now with the restriction on what the sort must do
there's been a redefinition of what 'best' means for Python.  No
implementation of Python is now allowed to do so, so the application
programmer won't have to remember it.  All it does it make it
slightly harder for a C# programmer to write a Python implementation.
And I assume there's plenty of 3rd party libraries which can help out.

> Most sorting applications don't care about stability.

Really?  I prefer my sorts to be stable since it best agrees
with what a person would do, assuming infinite patience.
It's nice because it's well defined and platform independent --
which is important because I've seen bugs crop up in some
programs which assumed a sort (3C) under IRIX will give
the same order as under Solaris -- C's sort is not stable.

> I think if a
> new sorting method is going to get added so there's separate methods
> for guaranteed-stable and possibly-nonstable sorting, it's best to let
> the new method be the stable one (maybe list.ssort) and leave the
> existing one alone.

Humbug.  You want an extra method (and possibly a couple of
independent algorithms which can be used on your disk-based
but list-like data structures) which for the most widely used version
of Python (CPython) will not do anything different and for which
the second most widely used version (Jython) is a trivial change,
all so that *someday* someone who implements a Python in a
language which doesn't have a fast stable search doesn't have
to write one (copying out of any standard text book), find a
3rd party version, or translate one?

Why not worry about something more complex, like regular
expressions.  CPython and Jython almost certainly have
differences in edge cases, and what will the version of Python
written in Prolog use?

                    Andrew
                    dalke at dalkescientific.com