Is there a general way to find the minimum or maximum element of a
list that's for more than numbers? I've been apropos'ing for this and
can't seem to find it.
Kind of like min, but taking a list and a predicate, and an optional
key. I wrote my own, but it seems like it's basic enough that maybe
there's a standard function somewhere for this:
(defun find-best (list test &key (key nil key-supplied-p))
(when (not (null list))
(let ((best (first list)))
(if (not key-supplied-p)
(loop for i in (rest list)
when (funcall test i best)
do (setq best i))
(loop for i in (rest list)
when (funcall test
(funcall key i)
(funcall key best))
do (setq best i)))
best)))
thus spoke Kyle McGivney <·······@gmail.com>:
> Is there a general way to find the minimum or maximum element of a
> list that's for more than numbers? I've been apropos'ing for this and
> can't seem to find it.
> Kind of like min, but taking a list and a predicate, and an optional
> key. I wrote my own, but it seems like it's basic enough that maybe
> there's a standard function somewhere for this:
(defun find-best (list fn &key (key #'identity))
(cond ((null list))
((null (cdr list))
(car list))
(t
(reduce (lambda (x y)
(if (funcall fn x y)
x
y))
list :key key))))
FANDANGO> (find-best '(5 6 42 8 666 9 69 -42)
#'>)
666
FANDANGO> (find-best '(5 6 42 8 666 9 69 -42)
#'<)
-42
Simple enough, i guess.
HTH
--
Nawet świnka wejdzie na drzewo kiedy ją chwalą.
Kyle McGivney <·······@gmail.com> writes:
> Is there a general way to find the minimum or maximum element of a
> list that's for more than numbers? I've been apropos'ing for this and
> can't seem to find it.
>
> Kind of like min, but taking a list and a predicate, and an optional
> key. I wrote my own, but it seems like it's basic enough that maybe
> there's a standard function somewhere for this:
(loop :for x :in list
:maximizing (f x) :into max
:minimizing (g x) :into min
:finally (return (values max min)))
--
__Pascal Bourguignon__
···@informatimago.com (Pascal J. Bourguignon) writes:
> Kyle McGivney <·······@gmail.com> writes:
>
> > Is there a general way to find the minimum or maximum element of a
> > list that's for more than numbers? I've been apropos'ing for this and
> > can't seem to find it.
> >
> > Kind of like min, but taking a list and a predicate, and an optional
> > key. I wrote my own, but it seems like it's basic enough that maybe
> > there's a standard function somewhere for this:
>
> (loop :for x :in list
> :maximizing (f x) :into max
> :minimizing (g x) :into min
> :finally (return (values max min)))
This only returns (f x) and (g x), rather than X itself.
--
Thomas A. Russ, USC/Information Sciences Institute
On Mar 12, 1:41 pm, ····@sevak.isi.edu (Thomas A. Russ) wrote:
> ····@informatimago.com (Pascal J. Bourguignon) writes:
>
> > Kyle McGivney <·······@gmail.com> writes:
>
> > > Is there a general way to find the minimum or maximum element of a
> > > list that's for more than numbers? I've been apropos'ing for this and
> > > can't seem to find it.
>
> > > Kind of like min, but taking a list and a predicate, and an optional
> > > key. I wrote my own, but it seems like it's basic enough that maybe
> > > there's a standard function somewhere for this:
>
> > (loop :for x :in list
> > :maximizing (f x) :into max
> > :minimizing (g x) :into min
> > :finally (return (values max min)))
>
> This only returns (f x) and (g x), rather than X itself.
>
> --
> Thomas A. Russ, USC/Information Sciences Institute
There's also no specifying what the comparison predicate is.
Kyle McGivney <·······@gmail.com> writes:
> On Mar 12, 1:41 pm, ····@sevak.isi.edu (Thomas A. Russ) wrote:
>> ····@informatimago.com (Pascal J. Bourguignon) writes:
>>
>> > Kyle McGivney <·······@gmail.com> writes:
>>
>> > > Is there a general way to find the minimum or maximum element of a
>> > > list that's for more than numbers? I've been apropos'ing for this and
>> > > can't seem to find it.
>>
>> > > Kind of like min, but taking a list and a predicate, and an optional
>> > > key. I wrote my own, but it seems like it's basic enough that maybe
>> > > there's a standard function somewhere for this:
>>
>> > (loop :for x :in list
>> > :maximizing (f x) :into max
>> > :minimizing (g x) :into min
>> > :finally (return (values max min)))
>>
>> This only returns (f x) and (g x), rather than X itself.
>>
>> --
>> Thomas A. Russ, USC/Information Sciences Institute
>
> There's also no specifying what the comparison predicate is.
Right.
We may use the standard function REDUCE, but we have to write it
ourselves some utilities:
(defun minimum (lessp &key (key (function identity)))
(lambda (a b) (if (funcall lessp (funcall key a) (funcall key b)) a b)))
(defun maximum (lessp &key (key (function identity)))
(lambda (a b) (if (funcall lessp (funcall key a) (funcall key b)) b a)))
(defun extremum (lessp &key (key (function identity)))
(lambda (min&max new-item)
(cond
((funcall lessp (funcall key new-item) (funcall key (car min&max)))
(cons new-item (cdr min&max)))
((funcall lessp (funcall key (cdr min&max)) (funcall key new-item))
(cons (car min&max) new-item))
(t min&max))))
(defun string-length (string-designator)
(length (string string-designator)))
(let ((words '(There is an extremely small but nonzero chance that
through a process known as "tunneling" this product
may spontaneously disappear from its present location
and reappear at any random place in the universe
including your neighbor\'s domicile The manufacturer
will not be responsible for any damages or
inconveniences that may result)))
(values (reduce (minimum (function <) :key (function string-length)) words)
(reduce (maximum (function <) :key (function string-length)) words)
(reduce (extremum (function <) :key (function string-length))
words :initial-value (cons (first words)(first words)))))
--> A ;
INCONVENIENCES ;
(A . INCONVENIENCES)
--
__Pascal Bourguignon__ http://www.informatimago.com/
ADVISORY: There is an extremely small but nonzero chance that,
through a process known as "tunneling," this product may
spontaneously disappear from its present location and reappear at
any random place in the universe, including your neighbor's
domicile. The manufacturer will not be responsible for any damages
or inconveniences that may result.
From: Tobias C. Rittweiler
Subject: Re: finding the min or max element of a list
Date:
Message-ID: <87fxuwkl94.fsf@freebits.de>
Kyle McGivney <·······@gmail.com> writes:
> Is there a general way to find the minimum or maximum element of a
> list that's for more than numbers? I've been apropos'ing for this and
> can't seem to find it.
See EXTREMUM in cl-utilities.
-T.
On Mar 12, 11:36 am, "Tobias C. Rittweiler" <····@freebits.invalid.de>
wrote:
> Kyle McGivney <·······@gmail.com> writes:
> > Is there a general way to find the minimum or maximum element of a
> > list that's for more than numbers? I've been apropos'ing for this and
> > can't seem to find it.
>
> See EXTREMUM in cl-utilities.
>
> -T.
Yes! Thank you.
Kyle McGivney wrote:
> Is there a general way to find the minimum or maximum element of a
> list that's for more than numbers? I've been apropos'ing for this and
> can't seem to find it.
>
> Kind of like min, but taking a list and a predicate, and an optional
> key. I wrote my own, but it seems like it's basic enough that maybe
> there's a standard function somewhere for this:
>
> (defun find-best (list test &key (key nil key-supplied-p))
> (when (not (null list))
> (let ((best (first list)))
> (if (not key-supplied-p)
> (loop for i in (rest list)
> when (funcall test i best)
> do (setq best i))
> (loop for i in (rest list)
> when (funcall test
> (funcall key i)
> (funcall key best))
> do (setq best i)))
> best)))
Let's say you want to find the string whose length is
the greatest.
In Arc, use "best":
(prn
(best (fn (a b) (> len.a len.b))
'("so" "a" "grab" "but")))
The definition of best is short:
(def best (f seq)
(if (no seq)
nil
(let wins (car seq)
(each elt (cdr seq)
(if (f elt wins) (= wins elt)))
wins)))
Ruby:
puts %w(so a grab but).sort_by{|s| s.size}.last
Another way:
puts %w(so a grab but).inject{|a,b| a.size > b.size ? a : b}
Another way:
puts %w(so a grab but).map{|s| [s.size,s]}.max.last
On Mar 13, 2:04 am, William James <·········@yahoo.com> wrote:
> Kyle McGivney wrote:
> > Is there a general way to find the minimum or maximum element of a
> > list that's for more than numbers? I've been apropos'ing for this and
> > can't seem to find it.
>
> > Kind of like min, but taking a list and a predicate, and an optional
> > key. I wrote my own, but it seems like it's basic enough that maybe
> > there's a standard function somewhere for this:
>
> > (defun find-best (list test &key (key nil key-supplied-p))
> > (when (not (null list))
> > (let ((best (first list)))
> > (if (not key-supplied-p)
> > (loop for i in (rest list)
> > when (funcall test i best)
> > do (setq best i))
> > (loop for i in (rest list)
> > when (funcall test
> > (funcall key i)
> > (funcall key best))
> > do (setq best i)))
> > best)))
>
> Let's say you want to find the string whose length is
> the greatest.
>
> In Arc, use "best":
>
> (prn
> (best (fn (a b) (> len.a len.b))
> '("so" "a" "grab" "but")))
>
> The definition of best is short:
>
> (def best (f seq)
> (if (no seq)
> nil
> (let wins (car seq)
> (each elt (cdr seq)
> (if (f elt wins) (= wins elt)))
> wins)))
Note: "best" is built in to Arc; the definition from arc.arc
was shown for your information.
On Mar 13, 3:04 am, William James <·········@yahoo.com> wrote:
> Kyle McGivney wrote:
> > Is there a general way to find the minimum or maximum element of a
> > list that's for more than numbers? I've been apropos'ing for this and
> > can't seem to find it.
>
> > Kind of like min, but taking a list and a predicate, and an optional
> > key. I wrote my own, but it seems like it's basic enough that maybe
> > there's a standard function somewhere for this:
>
> > (defun find-best (list test &key (key nil key-supplied-p))
> > (when (not (null list))
> > (let ((best (first list)))
> > (if (not key-supplied-p)
> > (loop for i in (rest list)
> > when (funcall test i best)
> > do (setq best i))
> > (loop for i in (rest list)
> > when (funcall test
> > (funcall key i)
> In Arc, use "best":
>
> (prn
> (best (fn (a b) (> len.a len.b))
> '("so" "a" "grab" "but")))
>
> The definition of best is short:
>
> (def best (f seq)
> (if (no seq)
> nil
> (let wins (car seq)
> (each elt (cdr seq)
> (if (f elt wins) (= wins elt)))
> wins)))
>
Indeed! And in CL, too:
(defun best (lst cmp)
(loop with rtn = (car lst)
for x in (cdr lst)
when (funcall cmp x rtn)
do (setq rtn x)
finally (return rtn)))
CL-USER> (best '(3 0 2 1 4) #'<)
0
CL-USER> (best '(3 0 2 1 4) #'>)
4
CL-USER> (best '(3) #'>)
3
CL-USER> (best '() #'>)
NIL
On Mar 13, 9:21 pm, Gene <············@gmail.com> wrote:
> On Mar 13, 3:04 am, William James <·········@yahoo.com> wrote:
>
> (defun best (lst cmp)
> (loop with rtn = (car lst)
> for x in (cdr lst)
> when (funcall cmp x rtn)
> do (setq rtn x)
> finally (return rtn)))
Oops, forgot the optional key function:
(defun best (lst cmp &key (key #'identity))
(loop with rtn = (car lst)
for x in (cdr lst)
when (funcall cmp (funcall key x) (funcall key rtn))
do (setq rtn x)
finally (return rtn)))
On Mar 14, 2:38 am, Gene <············@gmail.com> wrote:
> On Mar 13, 9:21 pm, Gene <············@gmail.com> wrote:
>
> > On Mar 13, 3:04 am, William James <·········@yahoo.com> wrote:
>
> > (defun best (lst cmp)
> > (loop with rtn = (car lst)
> > for x in (cdr lst)
> > when (funcall cmp x rtn)
> > do (setq rtn x)
> > finally (return rtn)))
>
> Oops, forgot the optional key function:
>
> (defun best (lst cmp &key (key #'identity))
> (loop with rtn = (car lst)
> for x in (cdr lst)
> when (funcall cmp (funcall key x) (funcall key rtn))
> do (setq rtn x)
> finally (return rtn)))
You forgot to make it work on vectors as well. :)
(defun best (seq cmp &key (key #'identity) (start 0) end)
(let ((end (or end (length seq))))
(loop with result = (elt seq start)
for i from start below end
for x = (elt seq i)
when (funcall cmp (funcall key x) (funcall key result))
do (setf result x)
finally (return result)))
error checking missing and dispatching on sequence subtype missing as
well.
Cheers
--
Marco
From: Kent M Pitman
Subject: Re: finding the min or max element of a list
Date:
Message-ID: <u1w6dp6vu.fsf@nhplace.com>
Marco Antoniotti <·······@gmail.com> writes:
> On Mar 14, 2:38�am, Gene <············@gmail.com> wrote:
> [...]
> > Oops, forgot the optional key function:
> >
> > (defun best (lst cmp &key (key #'identity))
> > � (loop with rtn = (car lst)
> > � � � � for x in (cdr lst)
> > � � � � when (funcall cmp (funcall key x) (funcall key rtn))
> > � � � � do (setq rtn x)
> > � � � � finally (return rtn)))
>
> You forgot to make it work on vectors as well. :)
>
> (defun best (seq cmp &key (key #'identity) (start 0) end)
> (let ((end (or end (length seq))))
> (loop with result = (elt seq start)
> for i from start below end
> for x = (elt seq i)
> when (funcall cmp (funcall key x) (funcall key result))
> do (setf result x)
> finally (return result)))
This is O(n^2), of course. Calling ELT in a loop means that when it
is NOT an array it will have to seek the element every time. Better
to use an early decision to eitehr work on a list or work on an array
and not use ELT. IMO, we should never have put ELT into the language
because of this trap. I've never found useful uses for it other than
debugging or light demonstration. Ok, well, except for the one
idiomatic use, which is kind of a special case, where the index is a
constant value; that's O(1), and (ELT x 0) is "especially O(1)", if
there can be said to be such a thing.... probably FIRST, SECOND,
etc. should just work on sequences. I'm not sure that (ELT x 100) in
a loop would make me feel good about its O(1)-ness.
There is a version with REDUCE that finesses this, since REDUCE
presumably triages the list/vector thing efficiently...
(defun best (sequence comparison &key (key #'identity)) ;UNTESTED
(reduce (lambda (x y)
(if (funcall comparison (funcall key x) (funcall key y))
x y))
sequence
:initial-value (elt sequence 0)))
or some such thing. I didn't test it heavily so there may be rough
edges. Caveat emptor, and all that.