I would like to find the entry in a list that maximizes a function. I
started out with this:
(defun find-maximizing-item (lst fun)
(loop for item in lst
maximizing (funcall fun item)))
but that returns only the maximum value of the function and nothing
about what entry in the list made that maximum value happen. Is there
some other idiom I should be using instead? Is there a way to add more
keywords to LOOP so that I can add a "which-maximizes" accumulator?
(I'm currently using CLISP 2.35 but I'm interested in how any CL makes
this work.)
-- Jon
<·······@gmail.com> wrote:
+---------------
| I would like to find the entry in a list that maximizes a function.
| I started out with this:
| (defun find-maximizing-item (lst fun)
| (loop for item in lst
| maximizing (funcall fun item)))
| but that returns only the maximum value of the function and nothing
| about what entry in the list made that maximum value happen.
| Is there some other idiom I should be using instead?
+---------------
I don't know of one. AFAIK, one has to do it "manually", e.g.:
(defun find-maximizing-item (list &optional (function #'identity)
&key (test #'<))
(let ((max-item (first list))
(max-value (funcall function (first list)))
(max-position 0))
(loop for item in (rest list)
and position from 1
for value = (funcall function item)
when (funcall test max-value value)
do (setf max-item item
max-value value
max-position position))
(values max-item max-value max-position)))
I added MAX-POSITION 'cuz it might be useful sometimes
[but made it be the last value in the result, in case
you don't care]; uncrunched the Schemish variable names;
made the FUNCTION optional; added TEST [just for fun];
and unrolled the loop once to avoid calling FUNCTION
twice on the first item. Testing:
> (find-maximizing-item '(3 -4 2 5 -7 1 2))
5
5
3
> (find-maximizing-item '(3 -4 2 5 -7 1 2) (lambda (x) (* x x)))
-7
49
4
>
To make it more like other CL functions, you might want to make
the calling sequence use keyword KEY instead of a positional FUNCTION,
that is:
(defun find-maximizing-item (list &key (key #'identity) (test #'<))
(let ((max-item (first list))
(max-value (funcall key (first list)))
(max-position 0))
(loop for item in (rest list)
and position from 1
for value = (funcall key item)
when (funcall test max-value value)
do (setf max-item item
max-value value
max-position position))
(values max-item max-value max-position)))
> (find-maximizing-item '(3 -4 2 5 -7 1 2) :key (lambda (x) (* x x)))
-7
49
4
>
-Rob
p.s. I used #'< as the default :TEST [even though MAX-VALUE isn't an
input constant], because CLHS 17.2.1 "Satisfying a Two-Argument Test"
requires the list item being scanned to be the second argument of the
:TEST function.
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Rob Warnock wrote:
> ... uncrunched the Schemish variable names;
Yep, you caught me.
Thanks for the code, and for the mini-lesson in CL style! I'll try to
put them to good use.
-- Jon
On 2006-03-21 23:27:45 -0500, ····@rpw3.org (Rob Warnock) said:
> To make it more like other CL functions, you might want to make
> the calling sequence use keyword KEY instead of a positional FUNCTION,
> that is:
>
> (defun find-maximizing-item (list &key (key #'identity) (test #'<))
> (let ((max-item (first list))
> (max-value (funcall key (first list)))
> (max-position 0))
> (loop for item in (rest list)
> and position from 1
> for value = (funcall key item)
> when (funcall test max-value value)
> do (setf max-item item
> max-value value
> max-position position))
> (values max-item max-value max-position)))
Or you could use an association list which I find a bit more loopy:
(defun find-maximizing-item (list &key (key #'identity))
(loop with alist = (loop for item in list collecting (cons item
(funcall key item)))
with max-value = (loop for (item . value) in alist maximizing value)
return (let ((entry (rassoc max-value alist)))
(values (car entry) (cdr entry) (position entry alist)))))
CL-USER 22 : 2 > (find-maximizing-item (list "one" "two" "three" "four"
"five") :key #'length)
"three"
5
2
Of course your approach has the merit of allowing a user specified test
while the alist version just uses loop's standard maximizing, and the
alist version is slower since it does much more list traversal than
yours.
From: Carl Shapiro
Subject: Re: Am I missing something about (loop ... maximizing ...) ?
Date:
Message-ID: <ouymzfihp3g.fsf@panix3.panix.com>
·······@gmail.com writes:
> Is there a way to add more keywords to LOOP so that I can add a
> "which-maximizes" accumulator? (I'm currently using CLISP 2.35 but
> I'm interested in how any CL makes this work.)
With enough loop keywords you can do anything.
(defun find-maximizing-item (fn list)
(loop with which-element
for element in list
as previous = nil then maximum
maximizing (funcall fn element) into maximum
when previous when (> maximum previous)
do (setq which-element element)
finally (return (values which-element maximum))))
From: Carl Shapiro
Subject: Re: Am I missing something about (loop ... maximizing ...) ?
Date:
Message-ID: <ouyirq6hood.fsf@panix3.panix.com>
Make the obvious change for this to work in the 1 element case.
On 2006-03-22 03:15:47 -0500, Carl Shapiro <········@panix.com> said:
> With enough loop keywords you can do anything.
>
> (defun find-maximizing-item (fn list)
> (loop with which-element
> for element in list
> as previous = nil then maximum
> maximizing (funcall fn element) into maximum
> when previous when (> maximum previous) do (setq which-element element)
> finally (return (values which-element maximum))))
Indeed. Here's rob Warnock's version with the full boat of loop
keywords using triplets instead of an association list:
CL-USER 22 > (defun find-maximizing-item (list &key (key #'identity)
(test #'<))
(loop for item in list
for value = (funcall key item)
and position from 0
for current-triplet = (list item value position)
as max-triplet = current-triplet
then (if (funcall test (second max-triplet)
(second current-triplet))
current-triplet
max-triplet)
finally return
(values (first max-triplet) (second max-triplet)
(third max-triplet))))
FIND-MAXIMIZING-ITEM
CL-USER 28 > (find-maximizing-item (list "one" "two" "three" "fifteen"
"four" "five") :key #'length)
"fifteen"
7
3
From: Christophe Rhodes
Subject: Re: Am I missing something about (loop ... maximizing ...) ?
Date:
Message-ID: <sqodzz6jfc.fsf@cam.ac.uk>
·······@gmail.com writes:
> I would like to find the entry in a list that maximizes a function. I
> started out with this:
>
> (defun find-maximizing-item (lst fun)
> (loop for item in lst
> maximizing (funcall fun item)))
>
> but that returns only the maximum value of the function and nothing
> about what entry in the list made that maximum value happen. Is there
> some other idiom I should be using instead? Is there a way to add more
> keywords to LOOP so that I can add a "which-maximizes" accumulator?
> (I'm currently using CLISP 2.35 but I'm interested in how any CL makes
> this work.)
There's some discussion of this on <http://www.cliki.net/EXTREMUM>.
Christophe
<·······@gmail.com> wrote
>
>I would like to find the entry in a list that maximizes a function. I
> started out with this:
>
> (defun find-maximizing-item (lst fun)
> (loop for item in lst
> maximizing (funcall fun item)))
>
> but that returns only the maximum value of the function and nothing
> about what entry in the list made that maximum value happen. Is there
> some other idiom I should be using instead? Is there a way to add more
> keywords to LOOP so that I can add a "which-maximizes" accumulator?
You can use ITERATE instead of LOOP.
(http://www.cl-user.net/asp/libs/iterate)
(defun find-maximizing-item (list fn)
(iterate (for x in list)
(finding x maximizing (funcall fn x))))
> (find-maximizing-item '(1 2 -3 -2) #'abs)
-3
Marc
·······@gmail.com writes:
> I would like to find the entry in a list that maximizes a function. I
> started out with this:
>
> (defun find-maximizing-item (lst fun)
> (loop for item in lst
> maximizing (funcall fun item)))
>
> but that returns only the maximum value of the function and nothing
> about what entry in the list made that maximum value happen. Is there
> some other idiom I should be using instead? Is there a way to add more
> keywords to LOOP so that I can add a "which-maximizes" accumulator?
> (I'm currently using CLISP 2.35 but I'm interested in how any CL makes
> this work.)
>
> -- Jon
I like this non-loop approach. It needs a couple of little
utility functions:
(defun best-cons (a b)
(if (> (car a)
(car b))
a
b))
(defun value-and-arg (function)
(lambda(x)
(cons (funcall function x) x)))
Then you get the maximum and the argument that gives it
using reduce:
CL-USER> (reduce #'best-cons
'(1 2 3 4 5 6)
:key (value-and-arg #'sin))
(0.9092974 . 2)
CL-USER> (reduce #'best-cons
'(1 2 3 4 5 6 7 8 9 10)
:key (value-and-arg #'sin))
(0.98935825 . 8)
Alan Crowe
Edinburgh
Scotland
I came right back here when I realized that
(defun find-maximizing-item (list fun)
(reduce #'max list :key fun))
was what I was originally looking for, but I see you beat me to it.
-- Jon
jonrock <·······@gmail.com> wrote:
+---------------
| I came right back here when I realized that
| (defun find-maximizing-item (list fun)
| (reduce #'max list :key fun))
| was what I was originally looking for, but I see you beat me to it.
+---------------
Except that only tells you what the maximum function value was,
not which item produced it! [...which is what I thought the original
question was.] That is, with this version:
> (find-maximizing-item '(3 -4 2 5 -7 1 2) (lambda (x) (* x x)))
49
>
doesn't tell you it was the "-7" that caused this result.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Phooey! That'll teach me to post without actually trying it!
Fortunately, your code which captures the entire triplet (item, value,
position) is what I'm really using, so no harm done.
-- Jon
From: Wade Humeniuk
Subject: Re: Am I missing something about (loop ... maximizing ...) ?
Date:
Message-ID: <8wyUf.5583$%H.391@clgrps13>
Rob Warnock wrote:
> jonrock <·······@gmail.com> wrote:
> +---------------
> | I came right back here when I realized that
> | (defun find-maximizing-item (list fun)
> | (reduce #'max list :key fun))
> | was what I was originally looking for, but I see you beat me to it.
> +---------------
>
> Except that only tells you what the maximum function value was,
> not which item produced it! [...which is what I thought the original
> question was.] That is, with this version:
>
> > (find-maximizing-item '(3 -4 2 5 -7 1 2) (lambda (x) (* x x)))
>
> 49
> >
>
> doesn't tell you it was the "-7" that caused this result.
>
Which is remedied by,
(defun find-maximizing-item (list fun)
(values-list (reduce (lambda (e1 e2)
(if (> (car e1) (car e2)) e1 e2))
list :key (lambda (elt) (list (funcall fun elt) elt)))))
CL-USER 4 > (find-maximizing-item '(3 -4 2 5 -7 1 2) (lambda (x) (* x x)))
49
-7
CL-USER 5 >