Lisp中的倒车清单

妮莉

我试图在Lisp中反转列表,但出现错误:“错误:异常C0000005 [flags 0] at 20303FF3 {Offset 25 inside#} eax 108 ebx 200925CA ecx 200 edx 2EFDD4D esp 2EFDCC8 ebp 2EFDCE0 esi 628 edi 628 ”

我的代码如下:

(defun rev (l)
    (cond
        ((null l) '())
        (T (append (rev (cdr l)) (list (car l)))))) 

谁能告诉我我在做什么错?提前致谢!

约书亚·泰勒(Joshua Taylor)

您编写的代码在逻辑上是正确的,并且会产生想要的结果:

CL-USER> (defun rev (l)
           (cond
             ((null l) '())
             (T (append (rev (cdr l)) (list (car l)))))) 
REV
CL-USER> (rev '(1 2 3 4))
(4 3 2 1)
CL-USER> (rev '())
NIL
CL-USER> (rev '(1 2))
(2 1)

也就是说,在性能方面存在一些问题。附加功能产生的所有副本,但其最终的说法。例如,当您执行(追加'(1 2)'(ab)'(3 4))时,您将创建四个新的con单元格,它们的汽车分别为1,2,a和b。最后一个的cdr是现有列表(3 4)。这是因为append的实现是这样的:

(defun append (l1 l2)
  (if (null l1)
      l2
      (cons (first l1)
            (append (rest l1)
                    l2))))

那不是Common Lisp的append,因为Common Lisp的append可以接受两个以上的参数。它足够接近,足以说明为什么复制除最后一个列表以外的所有列表。现在来看一下对rev的实现意味着什么

(defun rev (l)
  (cond
    ((null l) '())
    (T (append (rev (cdr l)) (list (car l)))))) 

这意味着当您反转(1 2 3 4)之类的列表时,就好像您在:

(append '(4 3 2) '(1))              ; as a result of    (1)
(append (append '(4 3) '(2)) '(1))  ; and so on...      (2)

现在,在第(2)行中,您正在复制列表(4 3)。在第一行中,您正在复制列表(4 3 2),其中包括(4 3)的副本。也就是说,您正在复制一个副本那是对内存的非常浪费的使用。

一种更常见的方法是使用累加器变量和辅助函数。(请注意,我使用endprestfirstlist *而不是nullcdrcarcons,因为它使我们更清楚地知道我们正在使用列表,而不是任意的cons树。它们几乎是相同(但有一些区别)。

(defun rev-helper (list reversed)
  "A helper function for reversing a list.  Returns a new list
containing the elements of LIST in reverse order, followed by the
elements in REVERSED.  (So, when REVERSED is the empty list, returns
exactly a reversed copy of LIST.)"
  (if (endp list)
      reversed
      (rev-helper (rest list)
                  (list* (first list)
                         reversed))))
CL-USER> (rev-helper '(1 2 3) '(4 5))
(3 2 1 4 5)
CL-USER> (rev-helper '(1 2 3) '())
(3 2 1)

使用此辅助函数,可以轻松定义rev

(defun rev (list)
  "Returns a new list containing the elements of LIST in reverse
order."
  (rev-helper list '()))
CL-USER> (rev '(1 2 3))
(3 2 1)

也就是说,与其使用外部帮助器功能,不如使用标签来定义本地帮助器功能,这可能更常见

(defun rev (list)
  (labels ((rev-helper (list reversed)
             #| ... |#))
    (rev-helper list '())))

或者,由于不能保证Common Lisp可以优化尾调用,因此do循环在这里也很干净:

(defun rev (list)
  (do ((list list (rest list))
       (reversed '() (list* (first list) reversed)))
      ((endp list) reversed)))

本文收集自互联网,转载请注明来源。

如有侵权,请联系[email protected] 删除。

编辑于
0

我来说两句

0条评论
登录后参与评论

相关文章