Which programming languages provide a Schwartzian transform like interface for sorting

Question

Introduction

The Schwartzian transform -- also known as map-sort-map or decorate-sort-undecorate (DSU) --, attributed to Randal Schwartz of the Perl community, sorts elements of a list or array by a metric which maps each element to its “sort value”.

Example for those who are not familiar with the Schwartzian transform

For instance in Python 2.4 and above, both the sorted() function and the in-place list.sort() method take a key parameter that allows us to provide a special "key function".

This function is simply called on each list element before making comparisons and thus cleverly avoids computing the criterion value every time.

In other words, sorting a (Python) list of strings case-insensitive:

>>> sortList = ["the", "Schwartzian", "Transform", "rocks"]

>>> sortList.sort(key = lambda e: e.lower())
['rocks', 'Schwartzian', 'the', 'Transform']

This could be also split into the 3 basic steps Schwartz suggests:

#1:  Turn the list into an array of references to pairs
>>> temp = [(e.upper(), e) for e in sortList]
>>> temp
[('THE', 'the'), ... , ('TRANSFORM', 'Transform'), ('ROCKS', 'rocks')]

#2: Sort this list by the second elements
>>> temp.sort()

#3: Turn the sorted list back into one one value list
>>> sortList = [e[1] for e in temp]   
>>> sortList
['rocks', 'Schwartzian', 'the', 'Transform']

The Question

Now I wonder if other well-known programming languages like C++, C#¹⁾, Java, JavaScript, VisualBasic and so on provide Schwartzian transform like interface too or is a "workaround" (a own implementation rather than a language feature) needed instead like this sample in C#:

var unsorted = new string[] { "the", "Schwartzian", "Transform", "rocks"};
var sorted = unsorted.Select(word => new { word, lower = word.ToLower() })
                     .OrderBy(t => t.lower)
                     .Select(t => t.word)
                     .ToArray();

^{1) As far as I know it’s possible using the Linq syntax}

Answer 1

C++ normally uses < to specify sort order and this makes its sort interface more complicated, but still somewhat similar:

std::sort(
    vec.begin(), vec.end(), [](auto s1, auto s2) { return to_lower(s1) < to_lower(s2); });

Also note that std::sort modifies the original collection, it does not produce a new one.

---

C# and VB.NET support this directly, using syntax you already used:

var sorted = unsorted.OrderBy(t => t.ToLower())
                     .ToArray();

---

Java 8 Streams use Comparator, which has similar interface than < in C++. But it also provides Comparator.comparing(), which lets you just specify the key:

List<String> sorted = unsorted.stream()
    .sorted(Comparator.comparing(s -> s.toLowerCase()))
    .collect(Collectors.toList());

---

JavaScript's Array.sort accepts a comparer, just like Java, but has no helper function. The result is similar to C++:

arr.sort(
    function(a, b) { return a.toLocaleLowerCase().localeCompare(b.toLocaleLowerCase()); });

---

To sum up: while all the languages you mentioned offer a similar functionality, only C#, VB.NET and, with a more verbose syntax, Java let you specify just the key out of the box.

Answer 2

The Schwarzian transformation is a way to do O(N) transforms on the data that is being sorted (a O(n log n) process). It is used to overcome needing to do 2 * O(n log n) conversions.

The 'decorate' part of the pattern style name is also known as memoization in which frequently used values are cached.

We can see similar things being done with the hashCode in Java's String where it is computed once, and only once.

So, why all this pretext and no Schwarzian transformation in other languages?

First and foremost, often the components to make this idiomatic aren't there. Streams weren't in Java until 1.8. The @s = map { ... } sort { ... } map { ... } @u from perl is a streamish style of flow.

The other thing is, there are other idiomatic ways to work on this.

If you have an expensive comparator transformation in Java, then make a private method that does the transformation one time and cache that value, or if this is code that you can't modify or subclass (such as String) make a wrapper class that (for example) holds the String itself and the lowercase converted value.

This all gets back to the part - its not there because it wasn't doable cleanly with the parts of the language in a way that is idiomatic, of it is doable in another way that doesn't look the same.

Answer 3

I think the wikipedia article that you linked in the opening post really answers your question well. Schwartzian transform is a name of a particular idiom used in Perl to implement a specific simple algorithm that optimizes sorting by precomputing the keys to sort by. As noted in the article, other communities might implement the same algorithm in different ways, or might have a different name for the same idiom.

So, there are at least three conditions that have to be met in order for a language and/or its community to adopt schwartzian transform as an idiom:

1. The language should have higher order functions like map and sort and a way of composing pipelines of such functions,
2. The language shouldn't already have a better way of achieving the same result,
3. The community must be familiar with the term "schwartzian transform".

Point 1. obviously eliminates languages without HOFs, like older versions of Java, or languages where HOFs are possible, but cumbersome and hardly idiomatic, like C and older versions of C++. Note that this is the mechanism that makes implementing a schwartzian transform-like pipeline for processing collections possible, and many languages - from C# to Haskell - offer and encourage such a style of programming.

Point 2. eliminates languages like C#, F# or Ruby with their variants of sortBy function. Schwartzian transform as an idiom doesn't make much sense when you have a single function that does all the work in the standard library of your language (that function may or may not be implemented as a schwartzian transform itself). Notice how in your C# example both Selects are in fact unnecessary - you only need an OrderBy(x => x.ToLower()) to achieve what you need, making the whole idiom seem out of place.

As for point 3 - obviously you need to know the name to use it, and I for one have never heard it before. You learn something new everyday ;)

How many languages meet all three criteria? I don't know. But it's quite possible that only Perl and Python (arguably a language with many Perl "expats") do.

Answer 4

It is doable in C++, except that you have to write the utility function yourself.

In general, if there is something that you think is missing in the C++ standard library, it is because nobody has written a proposal to include it into C++ and submit that proposal to the C++ standards committee.

Prior to C++11, some crucial parts are missing:

• decltype specifier
• declval convenience template

Even with C++11, one crucial bit is still missing:

• Currently there is no way to constrain the keyFunc argument to be a C++ functor (function object, lambda, or a function pointer) that takes an input of type T and return a value of type K.
  If a programmer passes in something that doesn't fit, the compiler will just print out lots of errors.

Now that these crucial parts are in C++11, a lot of C++ programmers have been posting useful bits of template code on Stack Overflow. These will eventually "trickle" into the C++ standards library, if they are found to be useful and if someone would write a formal proposal for submission to the committee.

Sample implementation in C++11 - barely tested; disclaimers apply.

template <typename T, class KeyFunc>
auto SchwartzianCPlusPlusMemoized( 
    const std::vector<T>& inputVector, 
    const KeyFunc& keyFunc) 
-> std::vector<T>
{
    typedef decltype(declval<KeyFunc>()(declval<T>())) K;
    typedef std::pair<K, const T*> P;
    std::vector<P> tempVector;
    for (const T& t : inputVector) {
        tempVector.emplace_back(keyFunc(t), &t);
    }
    auto lessFunc = [](const P& left, const P& right) -> bool {
        return (left.first < right.first);
    };
    std::sort(tempVector.begin(), tempVector.end(), lessFunc);
    std::vector<T> outputVector;
    for (const P& p : tempVector) {
        outputVector.emplace_back(*p.second);
    }
    return outputVector;
}

Answer 5

It's quite easy to do it idiomatically in modern JavaScript:

arrOfDateStrings
 .map((d) => [new Date(d).getTime(), d])
 .sort(([a], [b]) => a - b) // or some other comparator
 .map(([, d]) => d),

And the usual name in helper libraries like lodash is "sortBy"