Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

sort function #651

Closed
zzamboni opened this issue Mar 21, 2018 · 18 comments
Closed

sort function #651

zzamboni opened this issue Mar 21, 2018 · 18 comments
Labels
Milestone

Comments

@zzamboni
Copy link
Contributor

@zzamboni zzamboni commented Mar 21, 2018

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 xiaq added this to the 0.13 milestone Mar 21, 2018
@xiaq
Copy link
Member

@xiaq xiaq commented Mar 21, 2018

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
Copy link
Contributor Author

@zzamboni zzamboni commented Mar 21, 2018

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
Copy link
Contributor Author

@zzamboni zzamboni commented Mar 21, 2018

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
Copy link
Member

@xiaq xiaq commented Mar 21, 2018

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
Copy link
Contributor Author

@zzamboni zzamboni commented Mar 25, 2018

@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
Copy link
Contributor Author

@zzamboni zzamboni commented Dec 5, 2018

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

@xiaq xiaq removed this from the 0.14 milestone Apr 6, 2019
@xiaq xiaq removed the type:enhancement label Oct 18, 2019
@xiaq xiaq added this to the 0.14 milestone Feb 16, 2020
@xiaq
Copy link
Member

@xiaq xiaq commented Feb 16, 2020

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

@zzamboni
Copy link
Contributor Author

@zzamboni zzamboni commented Feb 16, 2020

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
Copy link
Member

@xiaq xiaq commented Feb 16, 2020

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
Copy link
Member

@xiaq xiaq commented May 5, 2020

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

@hanche
Copy link

@hanche hanche commented May 6, 2020

How about order?

@xiaq
Copy link
Member

@xiaq xiaq commented May 6, 2020

Sounds good. order then.

@krader1961
Copy link
Contributor

@krader1961 krader1961 commented May 9, 2020

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
Copy link
Contributor Author

@zzamboni zzamboni commented May 9, 2020

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
Copy link
Contributor

@krader1961 krader1961 commented May 9, 2020

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
Copy link
Member

@xiaq xiaq commented May 24, 2020

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
Copy link
Contributor

@krader1961 krader1961 commented May 24, 2020

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
Copy link

@hanche hanche commented May 25, 2020

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.

@xiaq xiaq closed this in 1cd192d May 25, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
4 participants
You can’t perform that action at this time.