1 
(define (square-list items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things)
              (cons (square (car things))
                    answer))))
  (iter items nil))

入ると

(square-list (list 1 2 3 4))

それは (16 9 4 1) を返します - なぜこれは逆なのでしょうか?

4

4 に答える 4

4

末尾再帰を使用して出力リストを作成し、そのために、リストの先頭answerに追加することで累積します。当然、逆にリストが作成されます。これを修正するためのいくつかのオプションがあります。1つは末尾再帰を捨てることです。

(define (square-list items)
  (if (null? items)
      nil
      (cons (square (car items))
            (square-list (cdr items)))))

その他、リストを処理する前にリストを逆にします。

(define (square-list items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things)
              (cons (square (car things))
                    answer))))
  (iter (reverse items) nil))

さらに別のオプション：要素をまとめるのではなく、最後に追加します。

(define (square-list items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things)
              (append answer
                      (list (square (car things)))))))
  (iter items nil))

ただし、各オプションには独自のトレードオフがあります。

  • 最初のオプションは末尾再帰ではありません（ただし、末尾再帰のモジュロ短所です）
  • 2番目のオプションでは、1つの追加のトラバーサルと1つの追加のリストが必要です（これは、リストが逆になっている場合に発生します）
  • 3番目のオプションは2次式です。これは、各追加操作がリストをトラバースして、最後に要素を追加するためです。

すべてを考慮すると、最良の末尾再帰オプションは2番目のオプションです。

于 2013-02-28T01:29:16.560 に答える
1

2つの要素の単純なケースを見てください。

(square-list '(2 3))

これにより、次のようになります。

(iter '(3)
      (cons (square 2) nil))

==

(iter '(3) '(4))

次に、再帰呼び出しは次のことを行います。

(iter '()
      (cons (square 3) '(4))

==

(iter '() '(9 4))

これにより、の基本ケースが呼び出され、 。iterが返されますanswer。

つまり、リストを順方向にステップ実行しますが、各要素が処理されると、正方形がリストの前面に配置さanswerれるため、結果は逆方向に作成されます。

簡単な修正は次のように変更(cons (square (car things)) answer)することです。

(append answer (list (square (car things))))

これにより、新しい結果が最初ではなく最後に配置されます。ただし、これは、O（n）要素をコピーして毎回結果リストを再構築する必要があるため、一般的に不適切なアプローチと見なされます。

于 2013-02-28T01:30:40.877 に答える
1

問題はあなたのcons発言です。順序を次のように切り替える場合:

(cons (square (car things)) answer)

に：

(cons answer (square (car things)))

あなたのリストはあなたが望む順序で出てきます。

私はいつも次のように書く方がずっと簡単だと思っています：

(define (square-list2 items)
  (square-list-helper items '())
)

(define (square-list-helper items squares)
  (cond
    [(empty? items) squares]
    [else (append 
             squares 
             (square-list-helper (cdr items) (list (square (car items)))))]
    )
 )
于 2013-02-28T01:20:15.733 に答える
0

間違った順序で考えています。最初にリストの残りの部分を再帰的に処理し、次に現在の要素を処理した結果です。それはそれがそれを処理すると同時にあなたのリストを逆転させるでしょう。代わりにこれを試してください：

(define (square-list items)
  (define (iter things answer)
    (if (null? things)
      answer
      (iter (cdr things)
            (append answer (list (square (car things)))))))
(iter items (list)))
于 2013-02-28T01:30:45.920 に答える