在不使用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)))

&optionallambda列表中的关键字具有的效果是,最初调用(ncdr 2 '(a b c))so时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!