list - LISP - 获取列表的最后一个列表

Question

我想弄清楚如何从另一个列表中获取last(非空)列表，或者如果没有这样的列表则返回nil(递归)。这是一项家庭作业，因此我正在寻找有关方法的帮助，不一定是它的代码。示例:

(lastele '(1 (2 3) 4 5))  ;=> (2 3)
(lastele '(1 (2 3) (4 5)) ;=> (4 5)
(lastele '(1 2 3 4 5))    ;=> NIL

我试图遍历列表，如果我遇到一个子列表，我会检查列表的其余部分是否包含更多非空子列表，如果有，继续将列表设置为那个，并重复直到我们有一个空列表。

(defun lastele2 (L)
  (if (null L)
    '()
    (if (hasMoreLists (rest L))
      (lastele2 (rest L))
      (first L))))

虽然我似乎无法让 hasMoreLists 工作。在其中返回 t 或 f 只是错误。这是解决此问题的最佳方法吗？

Answer 1

首先，请注意，您隐含地假设所有子列表都不是空列表；如果它们可能是空列表，那么 nil 是一个不明确的结果，因为您无法判断您的函数返回 nil 是因为没有子列表，还是因为有，最后一个是空的。例如，

(fn '(1 2 3 4 5))  ;=> nil because there are no sublists  
(fn '(1 2 3 () 5)) ;=> nil because there are sublists, and the last one is nil

因此，假设顶层列表中没有非空子列表，我们可以继续。

使用标准函数的非作业解决方案

你不需要写这个。你可以只使用 find-if使用谓词 listp并使用关键字参数 :from-end t:

指定您要从末尾开始搜索

CL-USER> (find-if 'listp '(1 (2 3) 4 5) :from-end t)
(2 3)
CL-USER> (find-if 'listp '(1 (2 3) (4 5)) :from-end t)
(4 5)
CL-USER> (find-if 'listp '(1 2 3 4 5) :from-end t)
NIL

自己写

如果你需要写这样的东西，你最好的选择是使用一个递归函数来搜索一个列表并跟踪你最近看到的列表元素作为结果(起始值是 nil)，当你最终到达列表的末尾时，你会返回那个结果。例如，

(defun last-list (list)
  (labels ((ll (list result)                 ; ll takes a list and a "current result"
             (if (endp list)                 ; if list is empty
                 result                      ; then return the result
                 (ll (cdr list)              ; else continue on the rest of list
                     (if (listp (car list))  ; but with a "current result" that is
                         (car list)          ; (car list) [if it's a list]
                         result)))))         ; and the same result if it's not
    (ll list nil)))                          ; start with list and nil

这里的局部函数 ll 是尾递归的，一些实现会将其优化为一个循环，但使用真正的循环结构会更符合惯用语。例如，对于 do，您可以这样写:

(defun last-list (list)
  (do ((result nil (if (listp (car list)) (car list) result))
       (list list (cdr list)))
      ((endp list) result)))

如果你不想使用标签，你可以将其定义为两个函数:

(defun ll (list result)
  (if (endp list)
      result
      (ll (cdr list)
          (if (listp (car list))
              (car list)
              result))))

(defun last-list (list)
  (ll list nil))

或者，您可以使 last-list 和 ll 成为相同的函数，方法是让 last-list 获取 result 作为可选参数:

(defun last-list (list &optional result)
  (if (endp list)
      result
      (last-list (cdr list)
                 (if (listp (car list))
                     (car list)
                     result))))

在所有这些情况下，您正在实现的算法本质上是迭代的。这是

Input: list
result ← nil
while ( list is not empty )
  if ( first element of list is a list )
    result ← first element of list
  end if
  list ← rest of list
end while
return result

基于问题中代码的东西

不过，我们仍然可以找到更接近您的原始方法的方法(这将使用更多堆栈空间)。首先，您的原始代码具有适当的缩进(和一些换行符，但那里的编码样式更灵活):

(defun lastele2 (L)
  (if (null L)
      '()
      (if (hasMoreLists (rest L))
          (lastele2 (rest L))
          (first L))))

您尝试使用的方法看起来是将列表 L 的最后一个子列表定义为:

• nil，如果L为空；
• 如果 (rest L) 有一些子列表，无论 (rest L) 的最后一个子列表是什么；和
• 如果 (rest L) 没有一些子列表，则 (first L)。

不过，最后一行不太正确。必须是

• 如果 (rest L) 没有一些子列表，那么 (first L) 如果 (first L) 是一个列表，否则为nil。

现在，您已经有了一种方法来检查 (rest L) 是否有任何(非空)子列表；您只需检查 (lastele2 (rest L)) 是否返回给您 nil 。如果它返回 nil，则它不包含任何(非空)子列表。否则它返回列表之一。这意味着你可以这样写:

(defun last-list (list)
  (if (endp list)                             ; if list is empty
      nil                                     ; then return nil
      (let ((result (last-list (rest list)))) ; otherwise, see what (last-list (rest list)) returns
        (if (not (null result))               ; if it's not null, then there were more sublists, and 
            result                            ; last-list returned the result that you wantso return it
            (if (listp (first list))          ; otherwise, if (first list) is a list
                (first list)                  ; return it  
                nil)))))                      ; otherwise return nil

这是在实现一个本质上是递归的算法；子问题的值被返回，然后 lastList 在检查后返回一个值，结果是:

Function: lastList(list)
if ( list is empty )
   return nil
else
   result ← lastList(list)
  if ( result is not nil )
     return result
  else if ( first element of list is a list )
     return first element of list
  else
     return nil
  end if
end if