Re: Am I missing something about (loop ... maximizing ...) ?

Showing 1-4 of 4 messages
Re: Am I missing something about (loop ... maximizing ...) ? WJ 2/6/13 12:52 PM
Rob Warnock wrote:

> <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

Racket:

(define (find-maximizing-item items [func values] #:key [test <])
  (for/fold
    ([best-item (first items)]
     [best-val  (func (first items))]
     [index 0])
    ([item (rest items)]
     [i (in-naturals 1)])
    (define value (func item))
    (if (test best-val value)
      (values item value i)
      (values best-item best-val index))))

  > (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


Clojure:

(defn find-maximizing-item
  [items & {:keys [func test] :or {func identity, test <}}]
  (loop [items (rest items)
         i 1
         best-item (first items)
         best-val (func (first items))
         best-i 0]
    (if (empty? items)
      (list best-item best-val best-i)
      (let [value (func (first items))]
        (if (test best-val value)
          (recur (rest items) (inc i) (first items) value i)
          (recur (rest items) (inc i) best-item best-val best-i))))))

user=> (find-maximizing-item '(3 -4 2 5 -7 1 2))
(5 5 3)
user=> (find-maximizing-item '(3 -4 2 5 -7 1 2) :func #(* % %))
(-7 49 4)
Re: Am I missing something about (loop ... maximizing ...) ? WJ 11/23/14 1:02 AM
Gauche Scheme:

(use gauche.collection)
(find-max '(3 -4 2 5 -7 1 2) :key (^x (* x x)))
 ===>
-7
Re: Am I missing something about (loop ... maximizing ...) ? WJ 1/13/15 1:13 AM
Portable Standard Lisp:

(de find-maximizing-item (lst fun)
  (for (in item lst)
       (maximal item (funcall fun item))))

(find-maximizing-item '(0 -9 3) 'abs)
 ===>
-9

(find-maximizing-item '(3 -4 2 5 -7 1 2) '(lambda (x) (* x x)))
 ===>
-7


To simply find the maximal value:

(for (in item '(0 -9 3)) (maximize (abs item)))
 ===>
9
Re: Am I missing something about (loop ... maximizing ...) ? Xiaogang Liu 1/13/15 4:45 PM
If 'loop' macro is preferred, looping over cons cells probably fits the needs better. Here's my solution.

(setf lst (loop repeat 50 collect (random 100)))

(defun find-maximizing-item (lst fun &optional (lessp #'<))
 (loop with max-cell = lst
       with max-val = (if lst (funcall fun (car lst)) nil)
       for c on lst ; Loop over cons cells of lst
       for val = (funcall fun (car c))
       do (when (funcall lessp max-val val)
                     (setf max-val val max-cell c))
       finally (return max-cell)))

(find-maximizing-item lst #'identity)

Here's a similar version using mapl.

(defun find-maximizing-item (lst fun &optional (lessp #'<))
  (let ((max-cell lst)
        (max-val (if lst (funcall fun (car lst)) nil)))
    (mapl #'(lambda (c)
                 (let ((val (funcall fun (car c))))
                   (when (funcall lessp max-val val)
                     (setf max-val val max-cell c))))
             lst)
    max-cell))