2

Common Lisp 関数のみを使用して、s 式に含まれる s 式の数をカウントする関数を作成しようとしています。例えば：

((x = y)(z = 1)) ;; returns 2

と

((x - y)) ;; returns 1

ネストされた式が可能です:

((if x then (x = y)(z = w))) ;; returns 3

長さを見つける関数を書きましたが、ネストされた式がない場合に機能します。それは：

(define (length exp)
  (cond
    ((null? exp) 0)
    (#t (+ 1 (length (cdr exp))))))

ネストされた式を次のようにサポートするために、これを変更しました。

(define (length exp)
  (cond
    ((null? exp) 0)
    ((list? (car exp)) (+ 1 (length (cdr exp))))
    (#t (length (cdr exp)))))

これは、ネストのない式で機能しますが、ネストされた式の答えより常に 1 少なくなります。これは、上記の例の を例にとると((if x then (x = y)(z = w)))、これは最初に を見てif、3 番目の条件を満たし、cdr (式の残りの部分をリストとして) を に返すためlengthです。(x=y) に達するまで同じことが起こり、その時点で a+1が返されます。これは、式(if x then .... )がカウントされていないことを意味します。

どのような方法でそれを説明できますか? 追加+2すると、ネストされていない式が過大にカウントされます。

ネストはどこでも発生する可能性があるため、1 つの関数でこれを機能させる必要があります。

((x = y) (if y then (z = w)))
4

1 に答える 1

2

一見すると、あなたのコードは右 (cdr 側) にのみ再帰し、左 (車側) には再帰しないので、間違いなくそこに問題があります。

よく見ると、コンスを正確に数えているわけではないため、これはそれよりも少しトリッキーです。コンスが適切なリストを開始する場合と、リストの cdr である場合を区別する必要があります。car と cdr に再帰すると、その情報は失われます。SEXP を適切なリストとして反復処理する必要があります。

(defun count-proper-list (sexp)
  (cond ((atom sexp) 0)
        (t (1+ (reduce #'+ (mapcar #'count-proper-list sexp))))))

ただし、これはトップレベルのリストもカウントするため、必要と思われるものよりも常に 1 つ多く返されます。おそらく、

(defun count-proper-sublist (sexp)
  (1- (count-proper-list sexp)))
于 2012-11-28T03:54:53.273 に答える