Common Lisp循环累加器：使用multiple-value-bind最小化？

Question

(defvar x '((5 . a) (3 . b) (1 . c) (9 . d)))
> X
(loop for i in x minimize (car i))
> 1

我希望得到C，而不是1。我尝试使用values，因为它仍将使用最小化的第一个返回值，但我不知道在这种情况下是否有一种使用multiple-value-bind的方法？

(loop for i in x
      minimize (values (car i) (cdr i)) into ans
      finally (return ans))

- mck

Answer 1

恐怕您需要自己编写代码：

(let ((best ()))
  (dolist (pair x (cdr best))
    (when (or (null best) (< (car x) (car best)))
      (setq best pair))))

这个程序只扫描了一次列表。

然而下面的程序中，键（car）被多次调用（在注释中提到）。

可以进行优化：

(defun find-best (list &key (key #'identity) (test #'<))
  (when list
    (let* ((best (first list))
           (best-key (funcall key best)))
      (dolist (o (rest list) best)
        (let ((k (funcall key o)))
          (when (funcall test k best-key)
            (setq best o best-key k)))))))

- sds

---

当key只是car时，情况并不太重要，但这会在最佳值上多次调用关键函数（在此情况下为car）。如果key具有任何副作用或计算成本高昂，则减少这种情况可能是值得的。（当然，并非所有CL函数都是这样。例如，对于sort的文档表示“不能保证将调用key的次数”。） - Joshua Taylor

Answer 2

(defvar x '((5 . a) (3 . b) (1 . c) (9 . d)))

(loop for (num . sym) in x
      with min-num = nil
      with min-sym = nil
      do (when (or (null min-num)
                   (< num min-num))
           (setf min-num num
                 min-sym sym))
      finally (return (values min-sym min-num)))
;=> C, 1

;; see. http://common-lisp.net/project/iterate/doc/Finders.html#Finders
(ql:quickload :iterate)
(use-package :iterate)
(iter (for (num . sym) in x)
      (finding sym minimizing num))
;=> C

- anon

---

感谢anon指出iterate包；我以前没有使用过它，看起来非常不错--又是工具箱中的另一个工具 :) - mck

Answer 3

CL-USER 15 > (defparameter *x* '((5 . a) (3 . b) (1 . c) (2 . d) (9 . e)))
*X*

CL-USER 16 > (loop with (min-n . min-v) = (first *x*)
                   for (n . v) in (rest *x*)
                   if (< n min-n) do (setf min-n n min-v v)
                   finally (return min-v))
C

作为一个函数：

(defun minimize (list &key (pred #'<) (key #'identity))
  "returns values: the minimum value and if there was one"
  (if (null list)
      (values nil nil)
    (values (loop with min-e = (first list)
                  with min-v = (funcall key min-e)
                  initially (pop list)
                  for e in list 
                  for v = (funcall key e)
                  if (funcall pred v min-v) do (setf min-e e min-v v)
                  finally (return min-e))
            t)))


CL-USER 35 > (minimize '((5 . a) (3 . b) (1 . c) (2 . d) (9 . e)) :key #'car)
(1 . C)
T

- Rainer Joswig

---

; 简化并修正 cadr/cdar 的拼写错误（循环 以 x = '((5 . a) (3 . b) (1 . c) (9 . d)) 开始 以 (min-n . min-v) = (first x) 开始 对于 (n . v) 在 (rest x) 中 如果 (< n min-n)，则执行 (setf min-v v) 最后返回 min-v - Devon

把 (setf min-v v) 改成 (setf min-n n min-v v)。 - Devon

@devon：没错，我已经在函数中修改了。同时也在循环中进行了更改。 - Rainer Joswig

Answer 4

由于这是一个最小化问题，您只需要遍历列表一次。您可以直接使用loop、dotimes或其他迭代结构来实现。如果您想要更多的函数式方法，您可以使用类似以下的代码：

(defun keyed-predicate (predicate key)
  (lambda (x y)
    (if (funcall predicate
                 (funcall key x)
                 (funcall key y))
        x
        y)))

(cdr (reduce (keyed-predicate '< 'car) '((5 . a) (3 . b) (1 . c) (9 . d))))
;=> C

这样做的问题在于，它会多次调用关键函数，对于某些时刻是“当前最佳值”的元素。这也发生在sds's answer中（car 在 best 上被多次调用），尽管这不是 car 的问题，因为 car 没有任何副作用。例如，

(cdr (reduce (keyed-predicate '< (lambda (x) 
                                   (format t "visiting ~a~%" x)
                                   (car x)))
             '((5 . a) (3 . b) (1 . c) (9 . d))))
; visiting (3 . B)
; visiting (3 . B) ; repeat
; visiting (1 . C)
; visiting (1 . C) ; repeat
; visiting (9 . D)
;=> C

确保每个元素的关键函数只被调用一次是很好的，这在迭代实现中更容易实现。例如，

(defun optimum (predicate list &key key)
  (flet ((key (x) 
           (if (null key) x
               (funcall key x))))
    (if (endp list)
        (funcall predicate)
        (let* ((best (first list))
               (best-key (key best)))
          (dolist (item (rest list) best)
            (let ((item-key (key item)))
              (when (funcall predicate item-key best-key)
                (setf best item
                      best-key item-key))))))))

(cdr (optimum '< '((5 . a) (3 . b) (1 . c) (9 . d)) :key 'car))
;=> C

在这里，关键字仅在每个项目中被调用一次：

(cdr (optimum '< '((5 . a) (3 . b) (1 . c) (9 . d)) 
              :key (lambda (x) 
                     (format t "visiting ~a~%" x)
                     (car x))))
; visiting (5 . A)
; visiting (3 . B)
; visiting (1 . C)
; visiting (9 . D)
;=> C

- Joshua Taylor