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

Question

（编辑：我现在还不担心TCO呢）

我是（终于开始学习）Lisp。我试图写我自己的（天真的）函数来压扁列表。我从更简单的案例开始，如果它不起作用，将构建它来处理更复杂的案例。不幸的是，现在，我陷入了无限循环，无法弄清楚为什么。

我也不知道如何在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

使用SBCL进行调试。

告诉SBCL你想调试：

* (proclaim '(optimize (debug 3))) 

您的代码：

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

FLATTENIZER 

与STEP

* (step (flattenizer '(1 (2 3) 4))) 
; Evaluating call: 
; (FLATTENIZER '(1 (2 3) 4)) 
; With arguments: 
; (1 (2 3) 4) 

下一步步进它

1] step 
; Evaluating call: 
; (FLATTENIZER (CDR LST)) 
; With arguments: 
; ((2 3) 4) 

下一步

1] step 
; Evaluating call: 
; (FLATTENIZER (CAR LST)) 
; With arguments: 
; (2 3) 

下一步

1] step 
; Evaluating call: 
; (FLATTENIZER (CDR LST)) 
; With arguments: 
; (3) 

下一步

1] step 
; Evaluating call: 
; (FLATTENIZER (CDR LST)) 
; With arguments: 
; NIL 

下一步

1] step 
; Evaluating call: 
; (FLATTENIZER (CAR LST)) 
; With arguments: 
; NIL 

下一步

1] step 
; Evaluating call: 
; (FLATTENIZER (CAR LST)) 
; With arguments: 
; NIL 

看起来你现在处于循环状态。

回到顶层。

1] top 

* 

现在检查你的源代码。

Answer 3

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本身。