Function EXTREMUM
Syntax:
extremum sequence predicate &key key (start 0) end => morally-smallest-element
Arguments and Values:
sequence---a proper sequence.
predicate---a designator for a function of two arguments that returns a generalized boolean.
key---a designator for a function of one argument, or nil.
start, end---bounding index designators of sequence. The defaults for start and end are 0 and nil, respectively.
morally-smallest-element---the element of sequence that would appear first if the sequence were ordered according to sort using predicate and key
Description:
extremum returns the element of sequence that would appear first if the subsequence of sequence specified by start and end were ordered according to sort using predicate and key.
extremum determines the relationship between two elements by giving keys extracted from the elements to the predicate. The first argument to the predicate function is the part of one element of sequence extracted by the key function (if supplied); the second argument is the part of another element of sequence extracted by the key function (if supplied). Predicate should return true if and only if the first argument is strictly less than the second (in some appropriate sense). If the first argument is greater than or equal to the second (in the appropriate sense), then the predicate should return false.
The argument to the key function is the sequence element. The return value of the key function becomes an argument to predicate. If key is not supplied or nil, the sequence element itself is used. There is no guarantee on the number of times the key will be called.
If the key and predicate always return, then the operation will always terminate. This is guaranteed even if the predicate does not really consistently represent a total order (in which case the answer may be wrong). If the key consistently returns meaningful keys, and the predicate does reflect some total ordering criterion on those keys, then the answer will be right.
The predicate is assumed to consider two elements x and y to be equal if (funcall predicate x y) and (funcall predicate y x) are both false.
The return value of (extremum predicate sequence :key key) can be defined as (elt (sort predicate (subseq sequence start end) :key key) 0), but may use faster (less asymptotically complex) algorithms to find this answer.
Exceptional situations:
If sequence is empty, then the error no-extremum is signalled. Invoking the continue restart will cause extremum to return NIL.
Should be prepared to signal an error of type type-error if sequence is not a proper sequence.
[AK] I'd like a function that returns the n most extreme values. Also I'd like this function to exist in both consing and destructive versions, or maybe a destructive version is enough.
[Christophe] What would you like the destructive thing to do? Note that EXTREMUM, unlike SORT, in the non-destructive version needs only one storage location. I'm confused. As for the n most extreme values idea, it's fine by me, but I think that we do actually need more discussion in a public forum on this one.
[AK] The comment about a destructive version referred to the n most extreme values idea.
Rainer Joswig points out that you can do this using REDUCE. I thought there was some reason I'd considered and rejected REDUCE already, but have no idea what. Anyone?
[Rahul Jain] Maybe because it doesn't work with vectors?
[Christophe] No. REDUCE works with vectors; however, (reduce 'max '(1 2 3) :key '-) will return -1, not 1; this isn't so much of a problem with an invertible key function, but consider (reduce 'min list-of-expensive-things :key 'price).
[Tim Moore] You can do this using REDUCE, but you start venturing into the territory of functions which are a pain to write every time you need them and which may have more efficient implementations than using the high level functions:
[Dan Knapp] Of course, the obvious way around this is:
Though if you're going to do it with higher-order functions in this way, you'd probably just want (comparator), since (extremum) isn't adding anything at all.
[A N Other] An efficient implementation of extremum would call the key function less often.
[Anonymous Coward] This specification does not (unless I misread it) properly cover the case where multiple elements have equal keys (according to predicate). In such a case, a consistent order is imposed, but it is not total, so the specification explicitly allows the answer to be wrong. That is weird; it would be reasonable to expect one of the minimal elements to be returned. Also, "the element that would appear first if the sequence were ordered according to sort" is a weak description because (a) that element is not uniquely determined (if sort is not stable) and (b) it makes it impossible to implement extremum portably without actually invoking sort (it requires that extremum makes the same decision sort would make). Maybe we need two variants, extremum and stable-extremum.
[Anonymous Coward] What happens if sequence is empty? I think an error should be signalled. Maybe we should take an initial-value argument like reduce does.
[Anonymous Non-Coward] I am very confused here. Why should this not be a new keyword for reduce instead of a completely new function? I view extremum as merely a stopgap until it is possible to overload reduce to accept the new keyword or until the standard allows reduce to accept it. reduce is the first thing anybody is going to think of for this. So maybe we should call it reduce-new or something.