blerner
commented
1 year ago Under the hood, tables convert themselves to lists, and then use lists' sort-by method, which uses a quicksort-like algorithm...which is written to be exactly unstable when it comes to ties.
There are several options here, and I'm curious about @jpolitz and @shriram 's opinions here. We don't have a general-purpose sorting function on raw arrays (only on arrays of numbers), so converting to an array and using JS's sorting isn't going to suffice. We could rewrite the existing sort-by, to make the ties be handled in stable order. We could add a stable-sort-by method. Or we could add a method to tables to flip them upside down, and then you could call the existing order-by method.
I dunno which of these is "best"...
shriram
schanzer
Bootstrap:DS switched from method syntax to function syntax, and we're already seeing huge gains from teachers. Coupled with the Circles of Evaluation, they are immediately more comfortable composing operations. One of the most common cases is composing sorting operations, for example "sort animals alphabetically by species, then by age".
Our
order-bymethod makes no guarantees about stability, of course, so teachers have been consistently surprised by the results!What's fascinating is that this hasn't been an issue for the past 7 years with method syntax -- even though it's the exact same behavior. That suggests that methods were either hard enough that teachers weren't composing them, or that they were mysterious enough that teachers didn't have any confidence their own expectations of how they should work.
Anyway, this has now bubbled up to the point where it's become a sticking point, so I'm wondering what our options are here. Pyret appears to walk the table from the bottom up when sorting, presumably for performance/memory reasons. Is that consistent enough that I could invert the process in the function that wraps the call to
.order-by? Or would this require a change in the runtime itself?