#198 user-defined sorting order via key instead of predicate

[Robert Dodier]

As an alternative to a user-defined sorting order induced by a predicate (Boolean function of two arguments), we could define a sorting order by a key (general function of one argument), which would be applied to elements of the list to be sorted, and then a predicate would be applied. This would be simpler for the user when extracting the bits relevant for sorting is the more complex part, and not comparing the extracted bits.

E.g. to sort a list of lists of numbers by the second and third in each list, one would define the key function as lambda([l], [l[2], l[3]]).

I am thinking this would-be feature would be in addition to the existing sort predicate.

I suppose for completeness we would have to allow both a key function and a predicate.

At least one widely-used language implements sorting key functions, namely Python.

[Stavros Macrakis]

Today, we have sort(list) and sort(list,predicate fun). What if we allow sort(list,key) where key can be a number or a list of numbers which specify the keys? Fully compatible, although it does violate the principle that static analysis should tell you the meaning. For example, sort(...,f) could mean sort by a function or sort by a key specification, depending on the value of f.

We could compatibly also add sort(list,predicate fun,keyfun), maybe using false to specify the default predicate.

[Robert Dodier]

I'm not sure I would want to have 3 positional arguments, some of which might be false, although there is precedent for that elsewhere in Maxima if I recall correctly. Another possibility is a keyword argument key = ... which is not much used in Maxima, although much used in other systems such as Python.

Yet another possibility is to distinguish the key from the order predicate is to inspect the supplied functions for the number of arguments, and look for one argument for the key versus two for the predicate. For Maxima named functions and lambda expressions, this is easy. For Lisp functions, there is no way in Common Lisp to inspect the argument list, although it appears most, maybe all, extant implementations have an implementation-dependent way to do it.

I think the key has to be a function as opposed to an integer or list of integers, since the items being sorted aren't necessarily lists.

I don't have strong opinions about any of these options, except I'm pretty sure key has to be a function.