Elvish: sort function

[zzamboni]

It would be nice to have a sorting function in Elvish (maybe named something else, to avoid conflicting with the standard Unix sort command). Ideally it would support structured data, and allow specifying a sorting function (like Clojure's sort-by).

[xiaq]

Since Elvish uses strings for numbers, a sort function needs an explicit sorting criteria. Let's call it sort-as:

~> put 2 100 | sort-as number
▶ 2
▶ 100
~> put 2 100 | sort-as string
▶ 100
▶ 2
~> sort-as number [2 100] # also take list argument, like each
▶ 2
▶ 100

[zzamboni]

This works fine for strings and numbers, but how about structured types? One idea would be to allow the specification of a comparator function which returns whether two elements are in the correct order. For example:

~> edit:command-history | sort-with [a b]{ <= a[id] b[id] } # sort using the id field

[zzamboni]

If number and string were two "magical" comparator functions, then the same function could be used for both purposes (i.e. builtin or user-specified comparators).

[xiaq]

Yes, the most generic solution is to use functions as comparators.

On the other hand defining functions as comparators can be a bit verbose, and I like the idea of making a mini-DSL for specifying how things should be ordered, string and number being just the simplest examples. For instance, to sort maps first based a numeric score field, and then on the lexical order of a name field can be sort-as [id=number name=string] (this cannot use the map syntax because map pairs are unordered).

Let's make two functions, the one that takes a comparator named sort-with and the one taking the "order DSL" named sort-as.

Why not just one function? It is doable now, because strings and lists are not callable, so comparator functions and order DSLs are disjoint. But it might be possible that we make strings or lists callable in future, and it might make sense for sort-as [a list] and sort-with [a list] to do different things.

[zzamboni]

@xiaq makes sense. I think the order-DSL should be sufficient for most cases, but the generic function would be nice for more complex ones.

[zzamboni]

@xiaq just a gentle ping on this topic, since I've recently wished we had it :)

[xiaq]

Now that Elvish has a dedicated number type, the sort function does not need to take an explicit sorting criteria any more.

[zzamboni]

I'm not sure I understand - you would still need a function that receives two elements of the list to sort, and tell which one should go first, no? Number comparison would allow sorting lists of numbers natively, but for strings or structured data you still need a sorting criteria function.

[xiaq]

Well, sort can still accept such a function as an option, but it no longer needs to be required for the common use cases of sorting numbers, strings and lists - they all have a natural ordering. It will be be required for sorting other types of values.

[xiaq]

Hmm, this needs another name since sort is taken by the classical Unix command sort(1).

[hanche]

How about order?

[xiaq]

Sounds good. order then.

[krader1961]

I can live with order but prefer sorted from Python: sorted(iterable, cmp=None, key=None, reverse=False) --> new sorted list. Obviously the Elvish signature will be different but it still seems useful for the command, whatever it ends up being called, to accept options for specifying a comparison function and whether the output should be reversed.

[zzamboni]

I don't have strong feelings between order and sorted, both would be fine.

I fully agree with the need to be able to specify at least a comparison function (maybe a key as a special case).

With respect to the reverse option - I think it would be much better to have a separate reverse function, which can be applied to lists in general, including the output from the sorting function.

[krader1961]

A reverse (or reversed) command would be useful in its own right. But it's important, from an efficiency perspective, for the sorting command to have a means of easily inverting the results of the comparison function. Sure, you could pass a custom comparator but when all you want is the "natural" order, but descending rather than ascending, it's far simpler and clearer to say something like sorted &reversed $@list.

[xiaq]

The name sorted could be confused for a predicate that determines whether some values are already sorted. Moreover, Python needs a sort/sorted dichotomy since the former is destructive; Elvish has very few destructive operations, so having a sorted without a sort is weird.

[krader1961]

The name sorted could be confused for a predicate that determines whether some values are already sorted.

Yes, but that is mitigated, somewhat, by the well established pattern for commands that implement boolean predicates to have a has- or is- prefix; e.g., has-key. Having said that sorted isn't normally used as a verb. Of the synonyms for sort the only candidate I like is order so let's go with that.

[hanche]

I don't find the argument that sorted is not a verb compelling. Rather, I imagine an implicit verb: “Give me the sorted data”. If the command had side effects, such as replacing the data by a sorted version, I would find the argument more convincing.
Even so, I do like order, more as a personal preference – even if one could argue that the verb form indicates a side effect.