Scheme手習い (3) リスト作り

第3章「偉大なるCons」では再帰しながらconsを使ってリストを作ることを学びます

リストから指定した要素を取り除く、rember という関数を題材にします
最初は間違った定義を与えられちゃったりします

(define rember
  (lambda (a lat)
    (cond
      ((null? lat) (quote ()))
      (else (cond ((eq? (car lat) a) (cdr lat))
                  (else (rember a (cdr lat))))))))

が、作者に敬意を表して素直に追いかけてみます

(rember 'and '(bacon lettuce and tomato))
(rember 'and '(lettuce and tomato))
(rember 'and '(and tomato))
'(tomato)

(eq? (car lat) a) が成り立ったところで (car lat) を捨てるのはいいんですが
それまでに出てきた要素を捨ててはいけませんのであらためてくっつける必要があります
どうやってくっつけるかというと

第2の戒律
リストを作るにはconsを用いるべし。

というわけで正しい値を返す定義です

(define rember
  (lambda (a lat)
    (cond
      ((null? lat) (quote ()))
      (else (cond
          ((eq? (car lat) a) (cdr lat))
          (else (cons (car lat) (rember a (cdr lat)))))))))

今度は再帰の様子が今までとすこーし違って、再帰から戻るときにそのまま値を返すだけでなく
ひと仕事してから戻っています
本の中でもかなりのボリュームを割いて追いかけてくれています
たぶん大事なところ

(rember 'and '(bacon lettuce and tomato))
(cons 'bacon (rember 'and '(lettuce and tomato)))
(cons 'bacon (cons 'lettuce (rember 'and '(and tomato)))
(cons 'bacon (cons 'lettuce '(tomato)))
(cons 'bacon '(lettuce tomato))
'(bacon lettuce tomato)

このremberの定義はcondが二重になっています
ひとつにまとめることも可能です

(define rember
  (lambda (a lat)
    (cond
      ((null? lat) (quote ()))
      ((eq? (car lat) a) (cdr lat))
      (else (cons (car lat) (rember a (cdr lat)))))))

当然結果は同じです
実行の様子も同じ

ではなぜすぐに簡単化しないのですか。

そのときに関数の構造が引数の構造と一致しないからです。

以下のふたつを分けて考えようぜ、ってことかと思われます

• 外側のcond
  carを取る前にはnullかどうか確認しなければならないというcarの掟や
  nullであるかまたは1個以上のアトムを持つというラットのデータ構造を反映
• 内側のcond
  ラットのデータ構造一般についてではない、rember独自の基準を反映

次はリストのリストを取り、各リストの先頭の要素のリストを返すfirstsという関数を作ります
イチから新しいリストを作る場合は()にconsしていきます

(define firsts
  (lambda (l)
    (cond
       ((null? l) (quote ()))
       (else (cons (car (car l)) (firsts (cdr l))))))

実行の様子は以下のとおり
再帰の形としてはremberと似ています

(firsts '((a b) (c d) (e f)))
(cons 'a (firsts '((c d) (e f))))
(cons 'a (cons 'c (firsts '((e f)))))
(cons 'a (cons 'c (cons 'e (firsts '())))))
(cons 'a (cons 'c (cons 'e '())))
(cons 'a (cons 'c '(e)))
(cons 'a '(c e))
'(a c e)

これからも(cons (car l) (f (cdr l)))の形は繰り返し現れます
これが第3の戒律

第3の戒律
リストを作らんとせしときは、最初の要素になるものを記述し、しかる後にそれを
自然なる再帰にconsすべし。

「自然なる再帰」はこの場合リストのcdrということです

このあと、insertR、insertL、subst、subst2、multirember、multiinsertR、
multiinsertL、multisubstと繰り返し同じパターンで再帰の練習をします
かなり慣れます

第4の戒律（仮）
再帰のときは、常に少なくとも１つの引数を変えるべし。必ず終わりへと近づくこと
間違いなし。変えた引数は最終条件で必ずテストすべし。すなわち、cdrを用いるときは、
null?でテストすべし。

2章、3章はひたすらcdrとnull?を使いました