deep-copy-list

今、Gauche本こと「プログラミングGauche」を読んでる。7章を読んでいるところ。

プログラミングGauche

実質、勉強っぽいのは6章からなので、The Little Schemer同様、相当時間かけてる＞＜
今回は、6章で取り上げられている、deep-copy-listを書いてみる。

deep-copy-listに先立ってcopy-listという関数が話題に上げられている。
copy-listは次のような関数。

(define copy-list
  (lambda (l)
    (if (pair? (cdr l))
        (cons (car l) (copy-list (cdr l)))
        l)))

つまり、引数で与えられたリストをコピーする関数ね。
ただ、cdr部でしか再帰していないので、入れ物だけ新しく用意してる感じ？
僕がこの関数で躓いたのは、再帰の終了条件が

(pair? (cdr l))

ってことかな。はじめ間違って

(if (null? l)
    l
    (cons (car l) (copy-list (cdr l))))

ってしてしまった。これじゃ、ドットリストに対応できないからね。

さて、こんなcopy-list関数のあとで、car部分もコピーするdeep-copy-listを作ってみよう、と。
The Little Schemerでいうと、5章に出てきそうな内容かな。

まず、どっかに

(cons (deep-copy-list (car l))
      (deep-copy-list (cdr l)))

みたいのが出てくるハズやなー、思って

(define deep-copy-list
  (lambda (l)
    (if (pair? (cdr l))
        (cons (deep-copy-list (car l))
              (deep-copy-list (cdr l)))
        l)))

って書いてみた。
でも、これじゃ

(deep-copy-list '(foo bar baz))

でソッコー死ぬのね。
具体的には、if式でアトムfooに対してdeep-copy-listを適用しようとして

(cdr 'foo)

で死んどるのね。つまり、

(deep-copy-list (car l))

するつもりなら、

(pair? (car l))

もチェックせざるを得ないわけね。

っちゅうことで、書き直したのがこれ。

(define deep-copy-list
  (lambda (l)
    (cons
      (if (pair? (car l))
          (deep-copy-list (car l))
          (car l))
      (if (pair? (cdr l))
          (deep-copy-list (cdr l))
          (cdr l)))))

でも、これ、なんかキモい。(直感的に。直感はあてにならないけど。）
2個あるif式の構造がおんなじなので、まとめることができるのは分かる。
けど、まとめたとしても、なんかキモい。自分でも何がキモいかわからんけど、なんとなくキモい。

ということで、とりあえず共通な部分をローカルな関数でまとめた結果を書いとく。

(define deep-copy-list
  (lambda (l)
    (define f (lambda (g l) (if (pair? l) (g l) l)))
    (cons (f deep-copy-list (car l)) (f deep-copy-list (cdr l)))))