不使用 nthcdr 获取列表的第 n 个 cdr

Question

我是一名 Common Lisp 初学者，正在为我的一项任务而苦苦挣扎...

我的 CS 作业之一是创建一个函数，该函数基本上用作 clisp 的内置 nthcdr 函数。

我们称它为 ncdr:

(ncdr n L) => n 是我们要输出的 cdr，L 是列表

示例：

(ncdr 2 '(a b c)) => (c)
(ncdr 0 '(a b c)) => (a b c)
(ncdr -1 '(a b c)) => nil
(ncdr 5 '(a b c)) => nil

所以我的方法是设置一个计数器并将其与 n

以下是我想到的条件：

if n < 0 -> nil 
if counter < n -> + 1 counter and (ncdr (cdr list)
if counter = n -> output list
if counter > n -> nil

这就是我想出的...不过我认为这不是最有效的方法，而且目前还行不通。

(defun ncdr (n L &aux counter)
   (setq counter 0)
   (cond
      ((atom L) nil)
      ((< n 0) nil)
      ((< counter n) (+ 1 counter (ncdr n (cdr L))))
      ((eq counter n) L)
      ((> counter n) nil) ))

从我对函数的每一行 cond 进行试验的时间来看，我知道这条线没有按预期工作

((< counter n) (+ 1 counter (ncdr n (cdr L))))

我得到一个错误：nil 不是一个数字

我觉得我缺少解决这个问题的关键。

Answer 1

首先，错误。在：

(+ 1 counter (ncdr n (cdr L))))

您实际上是在对三个值求和：1、变量的值 counter 以及应用于两个参数的函数 ncdr 的结果，当 nil，产生错误（例如，您正在求和，(+ 1 0 nil) 和 nil 不是数字）。

然后，让我们来看看你的程序逻辑。

你的条件基本上是正确的，尽管它们导致了一个可以改进的程序，我们稍后会看到。

但是，你在他们的实现中犯了一个逻辑错误：counter 应该在函数的每次递归调用时改变，增加 1，而对于每次调用，你在函数开始时将它重置为零函数体的执行。这是因为增量，即使正确完成，也会被赋值 (setq counter 0).

取消

我们怎样才能正确地增加这样一个变量？通过向函数添加一个新参数 counter，并避免每次都将其重置为零，而仅在开始时将其分配为零，即在初始调用中。

如何在 Common Lisp 中做到这一点？使用可选参数，而不是辅助变量，这样：

(defun ncdr (n L &optional (counter 0))
  (cond ((atom L) nil)
        ((< n 0) nil)
        ((< counter n) (+ 1 counter (ncdr n (cdr L))))  ; <- Wrong!!! To be corrected
        ((eq counter n) L)
        ((> counter n) nil)))

所以，让我们修改条件的递归分支，以在递归调用中正确传递新值（并进行一些小的调整）：

(defun ncdr (n L &optional (counter 0))
  (cond ((atom L) nil)
        ((< n 0) nil)
        ((< counter n) (ncdr n (cdr L) (+ 1 counter)))  ; or (1+ counter)
        ((= counter n) L)                               ; use = for numbers
        ((> counter n) nil)))

lambda 列表中的 &optional 关键字具有最初调用 (ncdr 2 '(a b c)) 的效果，因此 counter 被分配给 0，而在其余调用中，当前值被传递, 递增 1，因此在递归结束时它将等于 n.

效率

不需要使用另一个变量，counter，因为你已经有一个适合递归的变量：n。事实上，您可以这样重新表述您的条件：

if the list is empty, return nil
if n is less then 0, return nil
if n is 0, return the list
if n is greater than 0, recur on n-1 and on the cdr of the list

产生具有以下结构的程序：

(defun ncdr (n L)
  (cond ((null L) nil)
        ((< n 0) nil)
        ((= n 0) L)
        (t (ncdr ...))  ; <- recursive call - to be completed as exercise!

Answer 2

对于 VisualLisp (AutoCAD)：

   (defun ncdr (n L)
     (if (< n 0)
       (setq L L)
       (repeat (+ n 1) (setq L (cdr L)))
       )
     )

这是一个循环，将列表L的第一个元素切割n+1次。从 0 开始。

示例：

(setq L (list 0 1 2 3 4)); -->(0 1 2 3 4)

(ncdr 0 L); -->    (1 2 3 4)
(ncdr 1 L); -->    (2 3 4)
(ncdr 2 L); -->    (3 4)
(ncdr 3 L); -->    (4)
(ncdr 4 L); -->    nil

不使用 nthcdr 获取列表的第 n 个 cdr

Get nth cdr of a list without using nthcdr

lisp

common-lisp

cdr