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

主要问题 loop

这里有一些问题.首先,您可以按如下方式编写循环.有return-from和whileCommon Lisp中的形式,而是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)