SICPを読む(46) 2.2.1(2) append

appendがわかりにくい。

(define o `(1 3 5 7))
(define s `(1 4 9 16))

(define (append list1 list2)
  (if (null? list1)
      list2
      (cons (car list1) (append (cdr list1) list2))))

(append o s) ; (1 3 5 7 1 4 9 16)

展開してみる。

(cons (car o)
      (cons (car (cdr o))
            (cons (car (cdr (cdr o)))
                  (cons (car (cdr (cdr (cdr o))))
                        s))))

traceしてみる。

|(append (1 3 5 7) (1 4 9 16))
| (append (3 5 7) (1 4 9 16))
| |(append (5 7) (1 4 9 16))
| | (append (7) (1 4 9 16))
| | |(append () (1 4 9 16))
| | |(1 4 9 16)
| | (7 1 4 9 16)
| |(5 7 1 4 9 16)
| (3 5 7 1 4 9 16)
|(1 3 5 7 1 4 9 16)

list1が空になったらlist1の末尾からlist2の先頭に追加してるのか。

再帰的に考えると、

(cons 現在の結果 次の結果)
(cons 現在の結果 (cons 現在の結果 次の結果))
(cons 現在の結果 (cons 現在の結果 (cons 現在の結果 最後の結果)))

と、単純化出来る。

「次が何か」、「最後が何か」を定義すれば良い。

考え方は今までと変わらないことがわかった。

(cons (car list1) (append (cdr list1) list2))という表現は良く出てきそうなので、体に叩き込んでおこう。

まとめ

「cdrダウンしつつ、consアップ」