4

（编辑：我不会担心 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)
4

3 回答 3

6

(listp NIL)return T，(listp (car NIL))所以当你到达列表末尾并递归时NIL，循环就会发生。

您需要更改测试的顺序，(null lst)首先测试，以避免循环。最好为此重写它cond。更改测试的顺序更容易，使用cond.

然后您会注意到，由于某种原因，您永远只会展平参数列表中的第一个元素。(3 4)in((1 2) (3 4))等呢？我们真的应该以某种方式将扁平化的car结果与扁平化的结果结合起来cdr。

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

于 2013-02-26T20:19:29.860 回答
5

NIL由于实际和历史原因，在 Common Lisp 中有点“奇怪”。例如：

  • NIL是一个符号：(symbolp NIL) ==> T
  • NIL是一个列表：(listp NIL) ==> T
  • NIL不是缺点细胞：(consp NIL) ==> NIL
  • 但无论如何你都可以接受它car：和cdr(car NIL) ==> NIL(cdr NIL) ==> NIL

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

于 2013-02-26T21:04:46.110 回答
4

使用 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

*

现在检查您的源代码。

于 2013-02-26T20:32:16.460 回答