我正在尝试使用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行出现错误。我错过了什么?
loop的主要问题
这里有几个问题。首先，可以像下面这样编写循环。在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)
短变型
CL-USER> (defparameter *test* '((1 2 3) (4 5) (6 7 8 9)))
*TEST*
CL-USER> (car (sort *test* '> :key #'length))
(6 7 8 9)
Paul Graham的most
请考虑Paul Graham的most函数:
(defun most (fn lst)
(if (null lst)
(values nil nil)
(let* ((wins (car lst))
(max (funcall fn wins)))
(dolist (obj (cdr lst))
(let ((score (funcall fn obj)))
(when (> score max)
(setq wins obj
max score))))
(values wins max))))
这是测试的结果(它也返回由提供的函数为'best'元素返回的值):
CL-USER> (most #'length *test*)
(6 7 8 9)
4
extreme utility
过了一会儿，我想到了extreme实用程序的想法，部分基于Paul Graham的函数。这是有效的和相当普遍的:
(declaim (inline use-key))
(defun use-key (key arg)
(if key (funcall key arg) arg))
(defun extreme (fn lst &key key)
(let* ((win (car lst))
(rec (use-key key win)))
(dolist (obj (cdr lst))
(let ((test (use-key key obj)))
(when (funcall fn test rec)
(setq win obj rec test))))
(values win rec)))
它接受比较谓词fn、元素列表和(可选的)key参数。很容易找到具有指定质量极值的对象:
CL-USER> (extreme #'> '(4 9 2 1 5 6))
9
9
CL-USER> (extreme #'< '(4 9 2 1 5 6))
1
1
CL-USER> (extreme #'> '((1 2 3) (4 5) (6 7 8 9)) :key #'length)
(6 7 8 9)
4
CL-USER> (extreme #'> '((1 2 3) (4 5) (6 7 8 9)) :key #'cadr)
(6 7 8 9)
7
注意这个东西在亚历山大被称为extremum。
使用递归:
(defun maxim-list (l)
(flet ((max-list (a b) (if (> (length a) (length b)) a b)))
(if (null l)
nil
(max-list (car l) (maxim-list (cdr l))))))
max-list内部函数获取两个列表中最长的一个。maxim-list是第一个列表中最长的，maxim-list是其余列表中最长的。