LISP - 获取列表的最后列表

Question

我试图找出如何从另一个列表中获取最后一个(非空)列表,或者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))))

在所有这些情况下,您实现的算法基本上是迭代的.它的

输入: 列表
结果 ← nil
而(列表不为空)
  if(列表的第一个元素是列表)
    结果 ← 列表的第一个元素
  如果
  列表 ←其余的列表
结束而
返回 结果

基于问题中代码的东西

但是,我们仍然可以找到更接近原始方法的东西(它将使用更多的堆栈空间).首先,你的原始代码有适当的缩进(和一些换行,但那里的编码风格更灵活):

(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) if (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在检查结果后返回一个值:

功能: lastList(名单)
如果(列表为空),
   回零
别的
   结果 ← lastList(名单)
  如果(结果不是零)
     返回 结果
  否则,如果(的第一要素列表是一个列表)
     返回的第一个元素列表
  否则
     返回nil
  结束如果
结束