为什么这个函数处于无限循环中 - 学习lisp

Question

(编辑:我还不会担心TCO)

我(终于到处)学习Lisp.我正在尝试编写自己的(naive-ish)函数来压缩列表.我从较简单的情况开始,如果它不起作用,它将构建它以处理更复杂的情况.不幸的是,现在,我得到了一个无限循环,无法弄清楚原因.

我也不知道如何在lisp中使用任何调试方法,所以如果你能指出我的方向,我也会很感激.

(defun flattenizer (lst)
  (if (listp (car lst))
    (flattenizer (car lst))
    (if (null lst)
      nil
      (cons (car lst) (flattenizer (cdr lst))))))

最终代码:

(defun flattenizer (lst)
  (cond
    ((null lst) nil)
    ( (consp (car lst)) 
        (nconc (flattenizer (car lst)) (flattenizer (cdr lst)) ))
    (T (cons (car lst) (flattenizer (cdr lst))))))

测试:

* (flattenizer '((1 2) (3 4)))

(1 2 3 4)
* (flattenizer '(1 (2 3) (4 5)))

(1 2 3 4 5)
* (flattenizer '((1 2) 3 (4 5) 6))

(1 2 3 4 5 6)
* (flattenizer '(1 2 3 4))

(1 2 3 4)

Answer 1

(listp NIL)返回T,等等(listp (car NIL)),所以当你点击列表末尾并递归时NIL,就会发生循环.

您需要更改测试的顺序,测试第(null lst)一个,以避免循环.最好用它cond来重写它.更改测试的顺序更容易cond.

然后你会注意到,由于某种原因,你只会在参数列表中展平第一个元素.怎么样(3 4)在((1 2) (3 4))等？我们真的应该以某种方式结合扁平化的结果car与扁平化的结果cdr.

如果将列表展平的结果是列表,那么我们将需要组合两个结果列表.此外,由于我们将组合列表,如果我们遇到一个原子,我们将不得不产生一个列表,作为扁平化原子的结果.

Answer 2

NIL由于实际和历史原因的混合,Common Lisp中有些"奇怪".例如:

• NIL 是一个符号: (symbolp NIL) ==> T
• NIL 是一个清单: (listp NIL) ==> T
• NIL是不是一个cons单元:(consp NIL) ==> NIL
• 但你可以采取car/ cdr也无妨:(car NIL) ==> NIL和(cdr NIL) ==> NIL

在你的代码中递归调用(car x)何时(listp (car x))导致无限递归,因为它NIL是一个列表,它car本身就是.