lisp - clip正数创始人

Question

我正在尝试使用 clisp 从函数参数列表中返回一个包含非负数的列表。

(defun recursive (L)
    (setq ret (list)) 
    (setq first (car L))
    (setq rest (cdr L))
    (if (null L) 
        0 
        (if (>= first 0) 
            (nconc ret (first)) 
            (recursive rest))))

(setq mylist (list 1 2 3 -1 0 -3))
(write (recursive mylist))

我写了这个并期望输出为 (1 2 3 0)

这段代码有什么问题？

Answer 1

让filter 成为您要实现的功能。然后 (filter nil) 应该返回 nil。在一般情况下，您递归地完成 (filter (number . tail)) 。假设 filter 计算列表中的正数列表，您可以解决 tail 的问题，并调用 (filter tail)。为了解决您当前的问题，您必须考虑 number 是否为正数，并相应地将元素添加到递归结果中。

(defun filter (list)
  (etypecase list
    (null nil)
    (cons (destructuring-bind (number . tail) list
            (if (plusp number)
                (cons number (filter tail))
                (filter tail))))))

我正在使用 ETYPECASE , PLUSP , DESTRUCTURING-BIND , 但你可以用不同的方式表达同样的意思。请注意，您使用了 NCONC这需要遍历整个列表，这不是必需的，并且会使您的整个方法在时间上呈二次方。

上述函数有一个缺陷，因为调用堆栈的大小会随着输入列表的大小线性增长。每次调用过滤器时，都会在堆栈上分配一个新帧，可以很容易地用 TRACE 查看。 :

CL-USER> (trace filter)
(FILTER)
CL-USER> (filter '(0 1 -2 3 -4 -5 6 7 -8 9))

0: (FILTER (0 1 -2 3 -4 -5 6 7 -8 9))
  1: (FILTER (1 -2 3 -4 -5 6 7 -8 9))
    2: (FILTER (-2 3 -4 -5 6 7 -8 9))
      3: (FILTER (3 -4 -5 6 7 -8 9))
        4: (FILTER (-4 -5 6 7 -8 9))
          5: (FILTER (-5 6 7 -8 9))
            6: (FILTER (6 7 -8 9))
              7: (FILTER (7 -8 9))
                8: (FILTER (-8 9))
                  9: (FILTER (9))
                    10: (FILTER NIL)
                    10: FILTER returned NIL
                  9: FILTER returned (9)
                8: FILTER returned (9)
              7: FILTER returned (7 9)
            6: FILTER returned (6 7 9)
          5: FILTER returned (6 7 9)
        4: FILTER returned (6 7 9)
      3: FILTER returned (3 6 7 9)
    2: FILTER returned (3 6 7 9)
  1: FILTER returned (1 3 6 7 9)
0: FILTER returned (1 3 6 7 9)

发生这种情况是因为您需要记住递归调用中 number 的每个中间值，以便使用递归结果cons它们。如果您可以在进入递归调用之前完成所有工作，那么就不需要保留中间值，并且该函数将是递归终端并且可以受制于所谓的尾调用优化。为此，您必须在通过累加器调用递归调用之前构建结果列表:

(defun filter (list accumulator)
  (etypecase list
    (null accumulator)
    (cons (destructuring-bind (head . tail) list
            (if (plusp head)
                (filter tail (cons head accumulator))
                (filter tail accumulator))))))

注意重复，可以重构为:

(filter tail (if (plusp head) (cons head accumulator) accumulator))

在上面，我们添加了一个accumulator，用于保存新列表。最初，您应该传递一个空列表。当您到达输入列表的末尾时，您返回累加器。否则，您在递归调用 filter 之前将数字添加到累加器。不同之处在于您不需要在调用堆栈中存储中间值。跟踪宏产生这个:

0: (FILTER (0 1 -2 3 -4 -5 6 7 -8 9) NIL)
  1: (FILTER (1 -2 3 -4 -5 6 7 -8 9) NIL)
    2: (FILTER (-2 3 -4 -5 6 7 -8 9) (1))
      3: (FILTER (3 -4 -5 6 7 -8 9) (1))
        4: (FILTER (-4 -5 6 7 -8 9) (3 1))
          5: (FILTER (-5 6 7 -8 9) (3 1))
            6: (FILTER (6 7 -8 9) (3 1))
              7: (FILTER (7 -8 9) (6 3 1))
                8: (FILTER (-8 9) (7 6 3 1))
                  9: (FILTER (9) (7 6 3 1))
                    10: (FILTER NIL (9 7 6 3 1))
                    10: FILTER returned (9 7 6 3 1)
                  9: FILTER returned (9 7 6 3 1)
                8: FILTER returned (9 7 6 3 1)
              7: FILTER returned (9 7 6 3 1)
            6: FILTER returned (9 7 6 3 1)
          5: FILTER returned (9 7 6 3 1)
        4: FILTER returned (9 7 6 3 1)
      3: FILTER returned (9 7 6 3 1)
    2: FILTER returned (9 7 6 3 1)
  1: FILTER returned (9 7 6 3 1)
0: FILTER returned (9 7 6 3 1)

请注意，该函数是尾递归的，但看起来并没有被优化掉，因为有一个箭头形的轨迹。然而，跟踪并不是了解函数是否是尾递归的可靠方法，因为跟踪更改帽的行为实际上已经完成。或者，也许 debug 质量太高以至于尾调用优化没有应用。这取决于您的实现。请注意，跟踪清楚地显示了中间列表是如何构建的，以及结果如何从深层传递到更高层次。另请参阅列表是反向构建的，因为我们一直使用累加器调用 cons(这很高效，与 nconc 相反)。由于您没有指定是否希望列表的元素与输入列表保持相同的顺序，因此我认为这不是必需的。

但是，您也可以调用 NREVERSE在结果列表上破坏性地反转它(即就地，不分配内存)。如果在这里，这没关系，因为您拥有正在构建的新列表，因此您可以在将其提供给调用者之前安全地修改它。这最好通过将实现细节包装在本地函数中来完成:

(defun filter (list)
  (labels ((filter (list accumulator)
             (etypecase list
               (null accumulator)
               (cons (destructuring-bind (head . tail) list
                       (filter tail (if (plusp head)
                                        (cons head accumulator)
                                        accumulator)))))))
    (nreverse (filter list nil))))

请注意，filter 在词法上绑定(bind)到全局 filter 函数内的局部函数。另见 LABELS .

但是，与编写递归函数来执行循环相比，您可以更好地花费时间。 Common Lisp 提供迭代构造，这意味着您可以简单地这样做:

(defun filter (list)
  (loop for number in list
        when (plusp number)
          collect number))

请注意，使用 REMOVE-IF-NOT 也可以轻松地从列表中删除元素。 .