[cl-utilities-devel] Re: making EXTREMUM return multiple values -- and request for a function EXTREMA.

[Tobias C. Rittweiler]

Peter Scott <sketerpot at gmail.com> writes:

> On 11/15/05, Tobias C. Rittweiler <tcr at freebits.de> wrote:
> > I'd like to suggest making EXTREMUM return all /equivalent/ extrema as
> > multiple values, such that for instance:
> >
> >   CL-USER> (extremum '((A . 3) (B . 1) (C . 2) (D . 1)) #'< :key #'cdr)
> >   (D . 1)
> >   (B . 1)
>
> That makes a lot of sense from a semantics perspective, and you've
> given me a lot to think about. However, I believe that this would be a
> better way to do it:
>
> * The EXTREMUM function would behave the way it does now. This is
> efficient and its correctness is immediately obvious from the source
> code. Using EXTREMUM indicates that you want only one answer, and you
> aren't particularly concerned about duplicates. This should be
> explicitly spelled out in the documentation (which I should probably
> get around to finishing sometime soon...).
>
> * The EXTREMA function will return a list of all equivalent extrema
> (by your definition of equality). This name and return type emphasizes
> that it is returning all the extrema, and nothing that is not an
> extremum.
>
> * The N-MOST-EXTREME function will behave like your EXTREMA function:
> it will return the n most extreme values in a sequence.

I arrived to agreeing with this scheme. The main argument for me, that
you were certainly hinting at but didn't get spelled out as explicitely
as to make it immediately apparent (to me anyway), is that EXTREMUM will
invariantly return /one/ value and EXTREMA will invariantly return a
/list/ of values:

This way (ie. not having EXTREMUM return multiple values) a reader
doesn't need to mentally ask herself whether the very invocation of
EXTREMUM does deliberately ignore the possibility of multiple equivalent
extrema or whether the author was just being sloppy. Whereas with
EXTREMA returning a list, a writer will probably always map through that
list---making the case whether one extremum or several ones pretty much
equivalent.

> Here's my slightly less hackish code, based on yours:
>
> [...]
>
> The complexity of that code bothers me, though. I worry about complex
> code; it gives me feelings of looming bugs that are about to bite
> me---or worse, bite someone else. Perhaps I can find a cleaner way to
> write it if I put some more thought into it.

It were quite cool if the boilerplate for dealing with the right
subsequence &c could be *easily* hided like in the following way:

  (loop
     with smallest-elements = (list (elt sequence 0))
     with smallest-key      = (funcall key (elt sequence 0))
     for x across sequence from (1+ start) to end do
       (let ((x-key (funcall key x)))
         (cond ((funcall predicate x-key smallest-key)       ; x-key < smallest-key
                (setq smallest-elements (list x))
                (setq smallest-key x-key))
               ((not (funcall predicate smallest-key x-key)) ; x-key = smallest-key
                (push x smallest-elements))))
     finally (return smallest-elements))

Ah, well. :-)


> > Similiarly, I'd like to suggest a new function EXTREMA which returns the
> > N "topmost" extrema:
> >
> > [...]
> >
> >   CL-USER> (extrema 1 '((A . 3) (B . 1) (C . 2) (D . 1)) #'> :key #'cdr)
> >   ((A . 3))
> >   CL-USER> (extrema 2 '((A . 3) (B . 1) (C . 2) (D . 1)) #'< :key #'cdr)
> >   ((D . 1) (B . 1))
>
> Pretty good idea.
>
> > My version -- which can almost certainly be written many times
> > simpler -- is: [snip]
>
> As I was understanding this, I came up with a mental model: it simply
> returned the first n elements of the sequence sorted with a certain
> key and predicate. This immediately suggested a many times simpler
> version:
>
> (defun extrema (n sequence predicate &key (key #'identity))
>   (subseq (sort (copy-seq sequence) predicate :key key)
>           0 n))

Yes. Well, I initially had a (FIRST (SORT ...)) in my code, but then
needed all topmost equivalent elements, so I wrote something like:

  (let* ((list-with-long-name (foo ...))
         (sorted-list-with-long-name (sort list-with-long-name ...))
         (first-entry (first sorted-list-with-long-name)))
    (topmost-elements-if (lambda (x) (= x (compute-something first-entry)))
                         sorted-list-with-long-name
                         :key #'compute-something))

Which I considered to be so ugly that I went off and adapted your
EXTREMUM function to return all equivalent extrema as multiple
values. Well, then I found out that what I really needed is to always
get the N most extreme values, thus I wrote my version of EXTREMA and,
as you'll probably understand, my head was just immersed into how I
wrote EXTREMUM (which I wanted to evolutionize to fit my new needs),
such that I totally forgot my beginnings with (FIRST (SORT ...)) and
ended up with the code of my last mail.


> [...] My extrema function is stable in this case (by accident, since I
> didn't ask for a stable sort) and yours is unstable. This can
> sometimes be bad. I'll have to make -STABLE and regular versions.

I'd make that a keyword parameter :STABLE, maybe?


> I have been. And once I get my big load of homework and exams worked
> off, I'll inspire myself to actually make some changes to
> cl-utilities. You've been a big help, thanks.

I have to thank you. Keep up the work.


-t