2

我必须反转一个简单（一维）列表的元素。我知道有一个内置的反向功能，但我不能为此使用它。

这是我的尝试：

(defun LISTREVERSE (LISTR)
    (cond
        ((< (length LISTR) 2) LISTR) ; listr is 1 atom or smaller
        (t (cons (LISTREVERSE (cdr LISTR)) (car LISTR))) ; move first to the end
    )
)

输出非常接近，但是是错误的。

[88]> (LISTREVERSE '(0 1 2 3)) 
((((3) . 2) . 1) . 0)

所以我尝试使用append而不是cons：

(t (append (LISTREVERSE (cdr LISTR)) (car LISTR)))

但是得到了这个错误：

*** - APPEND: A proper list must not end with 2

有什么帮助吗？

4

4 回答 4

6

我可以给你一些建议，因为这看起来像家庭作业：

  • 递归的基本情况是当列表为空（null）时，而不是当列表中的元素少于两个时
  • 考虑定义一个带有额外参数的辅助函数，一个在空列表中初始化的“累加器”。对于原始列表中的每个元素，cons它位于累加器的头部。当输入列表为空时，返回累加器

As an aside note, the above solution is tail-recursive.

于 2012-04-19T03:09:15.280 回答
3

As a follow-up to Óscar López (and fighting the temptation to just write a different solution down):

  • Using both append and length makes the posted solution just about the least efficient way of reversing a list. Check out the documentation on cons and null for some better ideas on how to implement this.
  • Please, please indent properly.
  • Tail recursion really is both more efficient and reasonably simple in this case. Try it if you haven't already. labels is the form you want to use to define local recursive functions.
  • It may be worth your while to flip through The Little Schemer. It'll give you a better feel for recursion in general.
于 2012-04-19T14:05:31.490 回答
0

It's ok what you did. You only missed the composition of the result list.

Think about it: You have to append the 1-element list of the CAR to the end of the list of the reversed CDR:

(defun LISTREVERSE (LISTR)
    (cons
        ((< (length LISTR) 2) LISTR) ; listr is 1 atom or smaller
        (t (append (LISTREVERSE (cdr LISTR)) (list (car  LISTR))))))
于 2012-04-20T20:11:42.417 回答
0 
(defun listreverse (list)
  (let (result)
    (dolist (item list result)
      (push item result))))
  • Don't use recursion in Common Lisp when there is a simple iterative way to reach the same goal. Common Lisp does not make any guarantees about tail recursion, and your tail recursive function invocation may not be optimized to a jump at the discretion of the compiler.
  • push prepends the item to the result
  • dolist has an optional third argument which is the value returned. It is evaluated when the loop is exited.
于 2013-03-17T19:33:05.580 回答