This topic was moved here from #beginners > Sorting tuples? by Richard Feldman.
Aurélien Geron said:
Yes, it's commonly used in Python, and really quite handy, for example to compare versions (3, 1, 14) > (2, 9, 0), sort structured data (year, month, day), to sort events by timestamp, to use in data structures such as priority queues, and more. This lexicographical behavior is available in many other languages (Julia tuples, C++ with std::tuple, Rust tuples, etc.). I'm sure it's possible to live without it, but it would be good to have it IMHO.
quick design note - I want to draw a distinction between what I see as 3 different use cases:
> and <=, which I think should be for numbers only. I think it's a footgun if string1 < string2 compiles. It's really easy to guess incorrectly what that might do, whereas number1 < number2 is extremely well-defined. I would put tuple1 < tuple2 in that category, and I think an example of this is that the first sentence of the first response to this thread is "How would that work?" :smile:cc @Jonathan because you're working on #ideas > List sort builtins
so putting that together, I think:
is_gt and is_lt, so that < and >= intentionally don't work on tuplesis_gt and is_lt methods on them, that's up to those authors :smile: (I do think it's a lot clearer what version1 <= version2 means, or timestamp1 <= timestamp2, compared to what those would mean with plain tuples on either side of the operator!)This sounds good to me, especially if implementing comparison for a nominal type is as easy as: is_lt = tuple_lexicographical_compare (or whatever the name is).
So how about something like is_before and is_after to denote ordering. For numbers they can be redundant and defined to be is_lt etc, and then sorting functions defer to is_before instead, so that "less than" isn't semantically overloaded (to repeat what you said :smile: )
That's a fair amount more characters than is_lt though. is_bef/is_aft? Precedes/follows.
I think I remember reading that "is_before" and "is_eq" is sufficient for sorting algorithms in general
@Jonathan I don't know if it ever made it to a GitHub issue, but there was also this slightly updated sorting interface:
Ah good shout. I'm going to have another read through there again, but it seems like these are the key points worth pulling out. Lmk if I've missed something. Also keen not to re-litigate a 3 year old thread :smile:
Also
rec.compare() is over something like a.compare(b) (subject to whatever name is chosen, not necessarily "compare")I think there's two related interfaces into ordering. One is a function that compares and returns tags, and the other is your inline boolean comparison. The latter should be consistent with the tags, and though it's quite clear what a.is_before(b) means, I don't think M.is_before(a, b) is, unless the parallel convention for tags is FirstBeforeSecond et al.
Richard noted status quo as a good default when the decision isn't clear, but since ordering will now be decoupled from LT et al., I don't think there is much status quo to follow? So perhaps ordering should look like the following, pending the decisions at the end:
a.is_before(b)
# a.is_after(b) # not needed
a.is_equiv(b) # I like equivalent - but it seems long?
M.is_before(a, b) # less sure, but hoping static dispatch makes this uncommon
a.compare(b)
>> FstBeforeSnd | Equivalent | SndBeforeFst
# shortened these, but we could also have
# FirstBeforeSecond
# FirstThenSecond
# FstThenSnd
b.compare(a)
# Should the preposition or the order change? Ie:
>> SecondBeforeFirst
# or
>> FirstAfterSecond
If there's one thing I feel certain in this conversation, it's that I wouldn't want FirstAfterSecond to accompany FirstBeforeSecond. When I see that, I mentally pause, picture the First and the Second word, then I swap them, so that First comes After Second.
Just to check my understanding, if sorting is defined by a given type having some functions is_equiv and is_before (or whatever they are), doesn't that mean you can only have one sorting per type? And also that you can't provide new sortings for types you don't own? So you have to create a wrapper type just to do a new sorting. That seems like a bummer compared to just providing a single function that compares two elements, and then you pick the function that sorts as you want.
Ah, I neglected to include the actual sorting api, this is just comparison between two elements. (I've just realised compare is completely redundant as a method and can be removed).
The default List.sort requires that the list elements have is_before and is_equiv defined, but if you are sorting a type you don't own, or want to provide an alternative sort, you can either use sort_by or sort_with.
Oh okay, that's better at least. Though I'm concerned is_before and is_equiv are still poor interfaces:
is_equiv and is_before are function names that could easily blend with other functions. is_equiv reads like something that has to do with equivalence more than ordering for example.I'm wondering if we could just do without List.sort? Slightly controversial perhaps, but I'd much prefer always being explicit about what kind of sorting you're requesting, and List.sort leaves it implicit. When does List.sort even make sense? I guess for a list of numbers, there's a sensible default with ascending sorting, but other than that, I'm not sure there are any sensible defaults we want to provide. And at that point, why not just rename sort_with to sort, and always provide a function. Then you get my_list.sort(I64.ascending), which is much nicer for readability I think
I follow the reasoning but I dislike the impact on our weirdness budget
I kind of agree on point 2, but it seems to me like a general challenge with the ad-hoc interfaces that structural typing creates, where some method names have to be blessed or at least standardised. Since sorting no longer uses comparison operators, I do see less of an argument for standard ordering method names.
One problem I see with your suggestion is that if you write a function that internally sorts data as an implementation detail, what interface is required then? It would have to be
my_fun : List(a) where [a.ascending :...]
at which point ascending is the new standardised method name, which I suppose reduces the number of entrypoints into sorting from 2 to 1.
On the weirdness budget side of things, I think Go requires a sorting interface or function to be specified when sorting structs.
I quite like the idea of only having something like compare as a standard method name, returning FirstBeforeSecond et al., and getting rid of is_before and is_equiv. But removing it entirely as well as List.sort - do you think it's the case that there is no single obvious sorting behaviour for most data types? My gut feeling is that by the time you have created a new type, if it's sortable, there will be a clear main way to do it. Ready to be proven wrong :sweat_smile:
Something else comes to mind with sorting is its use in producing a canonical order, e.g., for tree based data structures or graphs. I think the specific sorting function used shouldn't matter, and imo it would be weird if you had to specify Graph.new(nodes, edges, Node.compare).
Jonathan said:
My gut feeling is that by the time you have created a new type, if it's sortable, there will be a clear main way to do it.
How should you sort strings?
I was thinking more types that have been created for an application and given a domain meaning, and that relying too much on primitives for these is often given as a code smell. It's a good example, but since a string is a primitive I don't think it's wrong either to define a default sort, e.g., lexicographic, for the purpose of a canonical order when needed.
In the case of List.sort, if the default ordering of strings doesn't match the use case, it could be fixed one-off with sort_by/_with, or the string wrapped in a type that defines its own compare, or even wrapped in a type that doesn't to ensure there is no default compare. Imo it just seems like a useful default, but I'd understand if that's not compelling.
Anton sagde:
I follow the reasoning but I dislike the impact on our weirdness budget
Which is fair, but I don’t think it’s that straight forward either. I personally find having both is_before, is_equiv, and compare functions to be a weirdness toll, because we now have two distinct ways of defining orderings, and I don’t recall seeing a pattern like is_before and is_equiv anywhere else previously. So although my suggestion of making List.sort always take a function may be a bit weird up front, I personally think it is more frugal with weirdness in the end, when there is one clear way to handle ordering
One important difference for me is that people are likely to try List.sort early in their exploration and evaluation of the language. is_before, is_equiv,... will be encountered later in their learning journey, by that time they are more likely to have made up their mind about the language.
Totally, which is also what I meant about the weirdness being up front or not. I do however wonder: which exact orderings would we provide as defaults? Integers as ascending is the only one that is sensible to me. Roc has explicitly let UTF8 sorting be dealt with in a library, so implementing some default ASCII string sorting that you probably shouldn’t use in production seems more like footgun than anything else. Convenient in tutorials maybe, but that’s about it.
Yeah, indeed, integers as ascending. There is a roc ascii package for sorting that clearly explains the trade-offs in the README.
Kasper Møller Andersen said:
I personally find having both
is_before,is_equiv, andcomparefunctions to be a weirdness toll
This can be reduced to just compare, given that is_before wouldn't be used in isolation outside of sorting, and is just a more convenient subset.
Jonathan sagde:
do you think it's the case that there is no single obvious sorting behaviour for most data types?
That’s my gut feeling yes. At a minimum, anything that is sorted for presentation purposes can be sorted in ascending or descending order. For something that’s not intended for displaying, I would not expect anyone to call List.sort on it at will. For any ordered collection, I think it would actually be nice that I am asked up front how I want the ordering to be. If the sorting is needed for internal purposes in the data structure, I don’t think it’s necessarily a good idea that the same interface that lets you call List.sort on with your type, is reused to make that data structure work.
Anton sagde:
Yeah, indeed, integers as ascending. There is a roc ascii package for sorting that clearly explains the trade-offs in the README.
So we agree that having a default non-UTF8 ordering for strings is a bad idea?
Yeah, I believe we intentionally did not support sorting for strings in the old compiler as well.
So integers default to ascending, but are there no others we want to provide as default? Because if not, that tells me that building a generic mechanism for using a default ordering is not that great and more likely to be used wrongly
Kasper Møller Andersen said:
If the sorting is needed for internal purposes in the data structure, I don’t think it’s necessarily a good idea that the same interface that lets you call
List.sorton with your type, is reused to make that data structure work.
I guess we have three use cases so far for comparison
I suppose I'm weighing the convenience of 2 quite highly. But if you were to remove a default mechanism you would also remove the possibility of sort_by (a key function sort) which I find incredibly convenient day to day.
I’m not quite following the importance of the data structure example, specifically because we’re talking about List.sort here. If you define some Tree type, users aren’t going to be calling List.sort on it. You can define a Tree to require is_before and is_equiv just fine
Or even better: is_before_in_tree
Now the name is specific to your data structure, so you don’t risk mixing up use cases.
Ah, I understood your position to be discouraging a standard .compare in general, or at least defaults for primitives, in addition to not having List.sort that presumes a default sort.
Kasper Møller Andersen said:
Or even better:
is_before_in_tree
Now the name is specific to your data structure, so you don’t risk mixing up use cases.
Do you mean as a constraint to using the API, ie
insert : Tree(a), a -> Tree(a) where [a.is_before_in_tree : a, a -> Bool]
or supplied as a function directly
insert : Tree(a), a, (a, a -> Bool) -> Tree(a)
Kasper Møller Andersen said:
You can define a
Treeto requireis_beforeandis_equivjust fine
This would also preclude using unwrapped primitives in the tree directly (which may be a feature :smile: ), so you would need to do something like
my_avl_tree.insert_with("Jonathan", age, Ascii.lexicographic_compare)
Kasper Møller Andersen said:
specifically because we’re talking about
List.sorthere
But anyhow, I think this extends beyond List.sort because not having a default order impacts other data structures and algorithms too.
I think my position is that I don’t like having defaults that are likely to get used wrongly, and in my experience, ALL the defaults are wrong a lot of the time when it comes to presentation at least. Though you’re right, if the primitives don’t expose some default ordering, they become harder to apply. But honestly, just taking some ordering function on initialization isn’t something I would be offended by in any way :sweat_smile:
Ahh ok, that makes sense to me. But there is a tradeoff to be made, otherwise we e.g. wouldn't want to derive hash because it isn't appropriate for passwords, or stability across versions of Roc. I don't work in frontend or anything similar, so this is probably a big blind spot for me.
When doing data structures that rely on sorting, is there a use case for switching orderings to e.g. tune performance? In that case, asking users to provide an ordering might be nice?
And likewise, I don’t do that many data structures these days :grinning_face_with_smiling_eyes:
Perhaps if an element being inserted into a tree-based map contains a (likely) unique user id, I suppose it could be better to order by that first, which would short circuit comparisons on other struct/tuple fields.
For every new module you make this would incur some boiler plate, without a default provided (unless there was an opt-in derive?)
I might just take a back seat on this topic for a bit anyhow :sweat_smile:
I get it, this is not a hill I’m dying on! At least I think my position has now been represented :smile:
Sorry if this is a dumb question from a newcomer, but I'm surprised by the suggestion that there's not a good default sort order for strings. Wouldn't it be lexicographic by unicode code point? (And then if you want a locale-aware sort, you'd have to explicitly specify that.)
There's no dumb question! :slight_smile: Lexicographic sort based on unicode code point is good for Jonathan's use case #2 (i.e., having a canonical way to decide on ordering), but it's not good for use case #1 (presentation) because sorting text depends on the locale (as you point out). Many people don't know about the fact that sorting depends on the locale (e.g., CH comes after H in Czech and Slovak), so providing a default order for Str is a footgun, imho.
Hmm, you guys have probably already hashed this out in detail — but do you have any sense of the fraction of calls to "sort" that are for presentation?
I would have expected that non-presentation sorts dominate, but I guess it depends on your use case. Like if you were using Roc for frontend dev, or for building GUIs (that need to be locale-aware) maybe you'd do a lot of presentation sorts?
But either way, I'm curious to understand the solution — will developers just be required to pass some comparator object to List.sort(), and then maybe they'd pass Str.lexicographic or Str.presentation(current_locale) or something like that?
Explicit is better than implicit, so I quite like the idea of names.sort_with(Unicode.compare_alphabetically(current_locale)) or names.sort_with(Unicode.compare_lexicograhically).
Perhaps List.sort could be based on is_lt but Str simply wouldn't have an is_lt function. In fact, very few types should have is_lt, such as numbers and versions. Types like tuples or records shouldn't have an is_lt function at all. To sort a list of tuples, you would write: vectors.sort_with(Tuple.compare_lexicographically) (not sure where to put this function).
So sorting lists of numbers would work very naturally, as beginners would expect, but sorting anything where the order is ambiguous would require being explicit.
Oh and there's also List.sort_by, which would be particularly useful for lists of records, for example: employees.sort_by(|person| person.age).
That said, this wouldn't work with person.last_name since Str has nois_lt. Maybe something like employee.sort_by(|person| person.last_name, Unicode.compare_alphabetically(current_locale)) would work?
Then there's the problem of multiple sorts. For example sorting by age then by name. Could be something like:
employees.sort_by_multiple(|person| (person.age, person.last_name), (U8.compare, Unicode.compare_alphabetically(current_locale)))
I just realized that sort_by_multiple would require language support for arbitrary length tuples, because users could return tuples of any length, and the first tuple should have the same length as the second. That's a fun challenge! :sweat_smile:
Aurélien Geron said:
Perhaps
List.sortcould be based onis_ltbutStrsimply wouldn't have anis_ltfunction. In fact, very few types should haveis_lt, such as numbers and versions. Types like tuples or records shouldn't have anis_ltfunction at all. To sort a list of tuples, you would write:vectors.sort_with(Tuple.compare_lexicographically)(not sure where to put this function).
This sounds maybe reasonable. Nice not to always have to pass a comparator.
There's a trade-off between ease of use and security+robustness. Python leans heavily towards ease of use, so you can sort lists of strings or tuples without a care in the world. This comes back to bite you sometimes. But to be honest, I wonder how often that really is. Are we making life harder for 99% of use cases just to avoid a sneaky issue for 1%? Maybe that's a good trade-off if it's only slightly harder and the sneaky issues have big consequences.
On string sorting, locale is only part of it. It’s also common that you want case insensitive matching, and often want natural sorting. Natural sorting treats numeric parts of strings as actual numbers, so you would get the ascending ordering [“5 Main Street”, “10 Main Street”] instead of the lexicographically correct [“10 Main Street”, “5 Main Street”].
And my personal conclusion is that there are just two opposing use cases for ordering, and there is no single ordering that satisfies both. I don’t know what the ratio of presentation to data structure sorting is, but I do know that I have written an elm-review rule that banishes sorting strings the default way, because we all kept messing it up at my job.
Maybe we can have two different orderings? Have the convention be that types can implement a default_computer_science_ordering and a default_presentation_ordering and that List.sort requires default_presentation_ordering, and then the problem is solved :smile:
(I actually really like those two function names for this particular interface, the more I think about :grinning_face_with_smiling_eyes: )
For strings in particular, perhaps you could use them as keys etc but only if you first do something like
ds.insert(name.as_bytes)
to explicitly signal that we are converting to List(U8)? Of course then List(a) would have to implement some kind of default compare if a does.
Aurélien Geron said:
Types like tuples or records shouldn't have an
is_ltfunction at all. To sort a list of tuples, you would write:vectors.sort_with(Tuple.compare_lexicographically)(not sure where to put this function).
I've come around to the argument about providing no default compare for strings, but that was because any default you use has a narrow window of appropriateness, and can be misused.
I don't think that applies for tuples. Acting as ad-hoc data structures I believe it is fine to just say "this is the way they compare", which provides significant utility if it aligns with your use case. Anyone writing even an introductory Point2D type will realise other sorts may make more sense and quickly provide their own wrapper (or no default compare at all).
As a beginner, I remember having to learn in other languages that tuples sort at all, which is distinct to strings where one knows they can sort, but would be surprised by the default.
In other words, what is the risk being mitigated by not providing defaults for tuples?
Just treating the string as bytes would actually be nice for the data structure case. And I don't think we need sorting on List(U8) then, because we could introduce a type Bytes that is just a thin wrapper around the List(U8), and then Bytes could implement sorting just fine.
So then to expand on that, integers (not floats?), Bytes, maybe tuples, could implement default_cmp, which would be a safe default and allow easy comparison without risking locale-ignorant string sorts. The theme seems to be "types that are decoupled from presentation or have a very clear default".
I understand the maximalist "no defaults at all" argument, but it seems to me like a lot more rigmarole to pass around as function handles, like desugared traits / interfaces / typeclasses.
I think the problem, once you get to a domain specific enough data type, you might want to sort/compare it differently in different parts of your codebase. I think, if there is a default, it should be explicit: sortWithDefault(T) and then sort(T, T.compare_of_choice).
I personally wouldn't expect us to have a default ordering for floats (because of the whole NaN business), but it depends on how much we want to try and pave that over. I don't have strong opinions on what is right and wrong in that case :slight_smile:
So, there's two different things happening here:
List.sort work on types that have such a default ordering (which is not that many types), or should List.sort be used for cases where an actual ordering is provided at the call site? I personally expect the latter will be the more common and correct approach in general, so it would be good to make that the nicest I think, and have some function a la List.sort_with_default for the few cases where that's what you want, as @Arya Elfren suggested :blush:Floats do have a total order, but it's expensive and probably not what most people expect.
So how about this as a summary/proposal:
[FirstBeforeSecond, Equivalent, SecondBeforeFirst], aliased here as Orddefault_cmp : a, a -> Ord methoddefault_cmp definedsort_with_default(List(a)) where [a.default_cmp : a, a -> Ord].default_cmp, you use sort_by(List(a), mapper_fn) where [mapper_fn : a -> b, b.default_cmp : b, b -> Ord].sort(List(a), comp_fn)Jonathan sagde:
- Sorting: If using the list sort api with a default comparison, the 'defaultness' of this is indicated by
sort_with_default(List(a)) where [a.default_cmp : b, b -> Ord].
I think you mean sort_with_default(List(a)) where [a.default_cmp : a, a -> Ord] with a instead of b? And there’s of course room for bikeshedding on names like sort_with_default, but I think this strikes a very nice balance :blush:
Jonathan said:
- Order: Comparison functions should have a return type of
[FirstBeforeSecond, Equivalent, SecondBeforeFirst], aliased here asOrd
Would anyone prefer something like [Ordered, Equivalent, Reversed] for brevity?
Or [Ordered, Tied, Reversed]?
It was suggested originally to make it completely obvious, where "less than" could mean, is the first less than the second, or the other way round? I guess it depends how obvious it is, let's see:
a.default_cmp(b)
>> Ordered
b.default_cmp(a)
>> Reversed
comparison_func(a, b)
>> Ordered
comparison_func(b, a)
>> Reversed
Kasper Møller Andersen said:
I think you mean
sort_with_default(List(a)) where [a.default_cmp : a, a -> Ord]withainstead ofb?
I did yeh, thanks - fixed!
@Eric Rogstad we had a ton of names in this thread way back when, including something similar to what you’re suggesting:
I think we’re better off not re-opening that particular discussion :sweat_smile:
I also find myself converting mentally that "ordered" means the first is before the second anyhow. Let's stick with FirstBeforeSecond et al. though because it generally had a good reception, despite its length
SecondBeforeFirst sounds like an oxymoron . How about LowerThan, Equal, HigherThan.
Which is basically the original API that got rejected previously. Here’s why:
On top of its similarity to the rejected "less", "lower" also assumes that you see "lower" as "before" which I think could be a confusing mix of prepositions.
Kasper Møller Andersen said:
Eric Rogstad we had a ton of names in this thread way back when, including something similar to what you’re suggesting:
I think we’re better off not re-opening that particular discussion :sweat_smile:
Wow, apparently I also participated in that discussion, in one of my few ever engagements with Roc Zulip.
Last updated: Jul 23 2026 at 13:15 UTC