multiinsertRとmultiinsertL

multiinsertR

(multiinsertR new old lat) は lat の中のすべての old の右側に new を挿入する。

(define multiinsertR
  (lambda (new old lat)
    (cond
      ((null? lat) (quote ()))
      ((eq? (car lat) old)
        (cons old (cons new (multiinsertR new old (cdr lat)))))
      (else
        (cons (car lat) (multiinsertR new old (cdr lat)))))))

実行例：

gosh> (multiinsertR 'fried 'fish '(chips and fish or fish and chips))
(chips and fish fried or fish fried and chips)

multiinsertL

左側に挿入する multiinsertL。

(define multiinsertL
  (lambda (new old lat)
    (cond
      ((null? lat) (quote ()))
      ((eq? (car lat) old)
        (cons new (cons old (multiinsertL new old (cdr lat)))))
      (else
        (cons (car lat) (multiinsertL new old (cdr lat)))))))

実行例：

gosh> (multiinsertL 'fried 'fish '(chips and fish or fish and chips))
(chips and fried fish or fried fish and chips)

間違った再帰の例

ところで、本文には間違った再帰の例が載っている（p.58）。次の multiinsertL の定義は (eq? (car lat) old) のところの再帰の仕方が間違っている。10行目だ。

(define multiinsertL
  (lambda (new old lat)
    (cond
      ((null? lat) (quote ()))
      (else
        (cond
          ((eq? (car lat) old)
            (cons new
              (cons old
                (multiinsertL new old lat))))
          (else (cons (car lat)
            (multiinsertL new old (cdr lat)))))))))

正しくは lat じゃなくて (cdr lat) を使って再帰しなくちゃいけない。
試しに実行してみよう。

gosh> (multiinsertL 'fried 'fish '(chips and fish or fish and chips))
out of memory (32).  aborting...

メモリーエラーになった。lat で再帰していることで無限に再帰してしまっているのだな。

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