On 9/16/11 9:38 AM, bearophile wrote:
Jonathan M Davis:
Comparator functions are pretty much always binary predicates.
And I think this has to change a bit in D. Because mapping functions
are quite handy (despite requiring more memory, so it can't be the
only way to do things in D, and both ways need to be supported).
In Python3 sort/sorted/min/max don't take a comparator function, they
only take a key mapping function.
It's often used in Haskell too:
import Data.List (sortBy) import Data.Ord (comparing) main = print $
sortBy (comparing length) [[1,3,1], [5], [7,7]]
Yah, that's what SQL's order by does too.
To sort numbers descending one would sort by mapping through "-a", to
sort case-insensitive one would sort by mapping through "toupper(a)" etc.
Without having thought a lot about this: sorting through mapping and
sorting by binary predicate are not equivalent in power. This is because
any sorting by mapping through some function f can be expressed as
sorting by f(a) < f(b). At the same time, if what you have is an opaque
predicate rank(a, b), you cannot define an equivalent mapper. This
suggests it's better to sort by binary comparison.
That being said, ranking by f(a) < f(b) can be quite wasteful if f is
expensive, so it's good to have it as an option for certain algorithms.
Obviously schwartzSort is one. Are there others?
Andrei
