Largest sublist in Common Lisp

问题:

I'm trying to get the largest sublist from a list using 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)))
)

The idea is to iterate through the list twice: the first loop gets the size of the largest sublist and the second one retrieves the required list. But for some reason I keep getting an error in the return-from line. What am I missing?

回答1:

Main problem with loop

There are a few problems here. First, you can write the loop as the following. There are return-from and while forms in Common Lisp, but loop defines its own little language that also recognizes while and return, so you can just use those:

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

A loop like this can actually be written more concisely with find though. It's just

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

Note, however, that list-length should always return a number or nil, so equalp is overkill. You can just use eql, and that's the default for find, so you can even write

(find maxlen list :key list-length)

list-length and maximize

list-length is a lot like length, except that if a list has circular structure, it returns nil, whereas it's an error to call length with an improper list. But if you're using (loop ... maximize ...), you can't have nil values, so the only case that list-length handles that length wouldn't is one that will still give you an error. E.g.,

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

(Actually, length works with other types of sequences too, so list-length would error if you passed a vector, but length wouldn't.) So, if you know that they're all proper lists, you can just

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

If they're not all necessarily proper lists (so that you do need list-length), then you need to guard like:

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

A more efficient argmax

However, right now you're making two passes over the list, and you're computing the length of each sublist twice. Once is when you compute the maximum length, and the other is when you go to find one with the maximum value. If you do this in one pass, you'll save time. argmax doesn't have an obvious elegant solution, but here are implementations based on reduce, loop, and 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))))

They produce the same results:

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)

回答2:

Short variant

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's most

Please, consider also Paul Graham's most function:

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

This is the result of test (it also returns value that's returned by supplied function for the 'best' element):

CL-USER> (most #'length *test*)
(6 7 8 9)
4

extreme utility

After a while I came up with idea of extreme utility, partly based on Paul Graham's functions. It's efficient and pretty universal:

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

It takes comparison predicate fn, list of elements and (optionally) key parameter. Object with the extreme value of specified quality can be easily found:

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

Note that this thing is called extremum in alexandria. It can work with sequences too.

回答3:

Using recursion:

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

The max-list internal function gets the longest of two list. maxim-list is getting the longest of the first list and the maxim-list of the rest.