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)を返しますT。また、を返します。したがって(listp (car NIL))、リストの最後に到達してを繰り返すとNIL、ループが発生します。

(null lst)ループを回避するには、テストの順序を変更して、最初のテストを行う必要があります。そのためにそれを書き直したほうがいいcondです。を使用すると、テストの順序を簡単に変更できcondます。

次に、何らかの理由で、引数リストの最初の要素のみをフラット化することに気付くでしょう。(3 4)で((1 2) (3 4))などはどうですか？carを平坦化した結果とを平坦化した結果をどうにかして組み合わせる必要がありcdrます。

リストをフラット化した結果がリストである場合、結果の2つのリストを組み合わせる必要があります。また、リストを結合するため、アトムに遭遇した場合、そのアトムをフラット化した結果としてリストを作成する必要があります。

于 2013-02-26T20:19:29.860 に答える
5

NILCommon 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))NILcar

于 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 に答える