lisp - Common Lisp 中最大的子列表

Question

我正在尝试使用 Common Lisp 从列表中获取最大的子列表。

(defun maxlist (list)
(setq maxlen (loop for x in list maximize (list-length x)))
(loop for x in list (when (equalp maxlen (list-length x)) (return-from maxlist x)))
)

想法是遍历列表两次:第一个循环获取最大子列表的大小，第二个循环检索所需的列表。但出于某种原因，我一直在 return-from 行中收到错误。我错过了什么？

Answer 1

循环的主要问题

这里有一些问题。首先，您可以编写如下循环。 Common Lisp 中有return-from 和while 形式，但是loop定义了它自己的也能识别 while 和 return 的小语言，所以你可以只使用它们:

(loop for x in list
      when (equalp maxlen (list-length x))
      return x)

虽然这样的循环实际上可以用 find 写得更简洁。只是

(find maxlen list :key list-length :test 'equalp)

但是请注意，list-length 应该始终返回一个数字或 nil，因此 equalp 有点矫枉过正。您可以只使用 eql，这是 find 的默认设置，因此您甚至可以编写

(find maxlen list :key list-length)

list-length 和maximize

list-length 很像length，除了如果列表有循环结构，它返回nil，而这是一个错误使用不正确的列表调用 length。但是如果你使用 (loop ... maximize ...)，你不能有 nil 值，所以唯一的情况是 list-length 处理 length 不会是一个仍然会给你一个错误的。例如，

CL-USER> (loop for x in '(4 3 nil) maximize x)
; Evaluation aborted on #<TYPE-ERROR expected-type: REAL datum: NIL>.

(实际上，length 也适用于其他类型的序列，因此如果您传递向量，list-length 会出错，但是 length不会。)所以，如果你知道它们都是正确的列表，你可以

(loop for x in list
      maximizing (length x))

如果它们不一定都是正确的列表(因此您确实需要 list-length)，那么您需要像这样保护:

(loop for x in list
      for len = (list-length x)
      unless (null len) maximize len)

更高效的argmax

但是，现在您要遍历列表两次，并且要计算每个子列表的长度两次。一次是计算最大长度，另一次是寻找最大值。如果一次性执行此操作，您将节省时间。 argmax 没有明显的优雅解决方案，但这里有基于reduce、loop 和do* 的实现>.

(defun argmax (fn list &key (predicate '>) (key 'identity))
  (destructuring-bind (first &rest rest) list
    (car (reduce (lambda (maxxv x)
                   (destructuring-bind (maxx . maxv) maxxv
                     (declare (ignore maxx))
                     (let ((v (funcall fn (funcall key x))))
                       (if (funcall predicate v maxv)
                           (cons x v)
                           maxxv))))
                 rest
                 :initial-value (cons first (funcall fn (funcall key first)))))))

(defun argmax (function list &key (predicate '>) (key 'identity))
  (loop
     for x in list
     for v = (funcall function (funcall key x))
     for maxx = x then maxx
     for maxv = v then maxv
     when (funcall predicate v maxv)
     do (setq maxx x
              maxv v)
     finally (return maxx)))

(defun argmax (function list &key (predicate '>) (key 'identity))
  (do* ((x (pop list)
           (pop list))
        (v (funcall function (funcall key x))
           (funcall function (funcall key x)))
        (maxx x)
        (maxv v))
       ((endp list) maxx)
    (when (funcall predicate v maxv)
      (setq maxx x
            maxv v))))

它们产生相同的结果:

CL-USER> (argmax 'length '((1 2 3) (4 5) (6 7 8 9)))
(6 7 8 9)
CL-USER> (argmax 'length '((1 2 3) (6 7 8 9) (4 5)))
(6 7 8 9)
CL-USER> (argmax 'length '((6 7 8 9) (1 2 3) (4 5)))
(6 7 8 9)