Общий Лисп цикл аккумулятора: уменьшить в несколько значений-связать?


(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))
4   2   2013-11-27 22:52:59

4 ответа:

Боюсь, вам придется самому написать код:

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

Поскольку это проблема минимизации, вам нужно будет только один раз пройти по списку. Вы можете сделать это непосредственно с помощью 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 , также (car вызывается best несколько раз) , though it's not an issue withавтомобиль , sinceавтомобиль " не имеет никаких побочных эффектов. Например,
(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
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