TSS rember1*

ネストした cond とか読みづらいですねー。

読みづらい、どころの問題じゃないです(苦笑)。
問題のコードはこれなんですけど。中でも「一番マシ」なのをピックアップしました。

; The Seasoned Schemer letrec, let
(define rember1*
  (lambda (a l)
    (letrec
        ((R (lambda (l)
              (cond
               ((null? l)(quote ()))
               ((atom? (car l))
                (cond
                 ((eq? (car l) a)(cdr l))
                 (else (cons (car l)
                             (R (cdr l))))))
               (else (let ((av (R (car l))))
                       (cond
                        ((eqlist? (car l) av)
                         (cons (car l)(R (cdr l))))
                        (else (cons av (cdr l))))))))))
      (R l))))
 
(rember1* 'salad '((Swedish rye)
                   (French (mustard salad turkey))
                   salad))
; -> ((Swedish rye) (French (mustard turkey)) salad)

もうあったまクラクラしてきますね(笑)。Schemeにある程度慣れていてもクラクラしてくるコードです。
The Little SchemerやThe Seasoned Schemerは「名著」の誉れが高いんですが「ホンマか?」と頭の中が疑念の嵐です、しょーじきなトコロ。ひっどいコードの垂れ流しとしか見えません。
僕は両書とも持ってないんで、意図がどこにあるのか、あるいは何か目的があってそこへ誘おうとしてるのか分からないんですが、いずれにせよ、このコードを見る以上「酷いコードが書かれてあるテキスト」だとしか思えません。

「リファクタリングせねば!」

とか思ったんですが、これがなかなか(苦笑)。一筋縄ではいかない。
valvallowさんが記述している通り、

ネストした list 内から最初に見つかったものを一つだけ取り除くって、一つだけって逆に難しいですね。

なんです。全くです(苦笑)。

しかしながら、テキストを鵜呑みにするんじゃなくって

「何とかリファクタリングして短いコードが書けないか?」

と考えるのは良い練習だと思います。
と言うのも、Schemeで実用的なプログラムを書くのは難しいですし、もしある目的を達成するコードが「短く書けない」のなら、そもそもSchemeなんて勉強する必要なんて無いんです。

コードを極限まで短くする方法を考える

のがSchemeの学習の唯一の価値です。ホントですよ。
(大体、短く書けなきゃSchemeはやたら括弧が多い妙ちきりんな言語なだけ、です。)

まず、例示のコードを見て気になるのは、letrecを用いている意味が全くない、って辺りです。
と言うのも、このコードは全く末尾再帰してないので、ローカル手続きを使ってる意味が無いんです。従って、まずはletrecを消去しちゃいましょう。ここは無駄な部分です。

(define (rember1* a l)
  (cond
   ((null? l) '())
   ;; atom? は標準手続きじゃないので、not pair? に置き換える。
   ((not (pair? (car l)))
    (cond
     ((eq? (car l) a) (cdr l))
     (else (cons (car l) (rember1* a (cdr l))))))
   (else (let ((av (rember1* a (car l))))
    (cond
     ;; eqlist?も標準手続きではない。
     ;; リスト同士の等価判定はequal?で充分。
     ((equal? (car l) av)
      (cons (car l) (rember1* a (cdr l))))
     (else (cons av (cdr l))))))))

それで、このコードを扱ってる章では、valvallowさんの記述によると、

letを使って局所変数を纏めよう

と言うのが狙いのようなんですが、だったらどうしてこんなに中途半端なのか。コード中に現れる(car l)や(cdr l)こそ局所変数で纏めるべきなんですよ。これが素のままで記述されているので、ネストだらけになって見づらいんです。

(define (rember1* a l)
  (if (null? l)
      '()
      (let ((x (car l)) (y (cdr l)))
 (if (not (pair? x))
     (if (eq? x a)
  y
  (cons x (rember1* a y)))
     (let ((av (rember1* a x)))
       (if (equal? x av)
    (cons x (rember1* a y))
    (cons av y)))))))

valvallowさんが仰ってる通り、

分岐が2つなら if 使おうよ。

って事なんで、condも全部ifに置き換えます。
ちょっとは見通し良くなったかな?

次は個人的趣味なんですが、あんまnot～ってのは好きじゃないんですよね。元々分岐が二つである以上、論理的には「pair?であるか、そうじゃないか」ってだけです。つまり、分岐二つの枝の順序は取り替えて良い。

(define (rember1* a l)
  (if (null? l)
      '()
      (let ((x (car l)) (y (cdr l)))
 (if (pair? x)
     (let ((av (rember1* a x)))
       (if (equal? x av)
    (cons x (rember1* a y))
    (cons av y)))
     (if (eq? x a)
  y
  (cons x (rember1* a y)))))))

だいぶ整理されて見やすくなっては来ました。だけど依然としてifのネストはウザいです。ウザいですね。
一つの考え方ですが、例えば(pair? x)以降のifのカタマリに着目してみましょうか。
Lisp系言語の素晴らしいトコは、文がないと言う辺りです。実際文がある言語ではif～then～elseは制御構文なんで、基本的に手続きの引数につっこめません。必ず手続きの外側に置く必然性が出てきます。
一方、全てが式であるLispではその辺融通無碍です。
どう言う事かと言うと、この部分ではどっちにせよ動作は

(cons 何とか1 何とか2)

が求められてるんですね。フォーマットとしては特に差異がないんです。
つまり、次のように書き換えてしまう事が可能です。

(define (rember1* a l)
  (if (null? l)
      '()
      (let ((x (car l)) (y (cdr l)))
 (if (pair? x)
     (let ((av (rember1* a x)))
       ;; 述語の判定結果を it に束縛してしまう。
       (let ((it (equal? x av)))
  ;; it を利用して cons の引数を交換してしまう。
  (cons (if it x av) (if it (rember1* a y) y))))
     (if (eq? x a)
  y
  (cons x (rember1* a y)))))))

これは荒技に見えるかもしれませんが、結構Lisp系ではオーソドックスな手だと思います。これでネストが減ったように見えて(実際見えるだけ、ですが)若干コードがフラットになった印象を受けます。
そして、

(cons 何とか1 何とか2)

が(let ((x (car l)) (y (cdr l)))...以下の主作業であり、また「引数交換」だけで書けるのなら、最後の枝も纏めてしまえるのでは、と言う野望が生まれますね。そして恐らくそれは正しいんです。
ちょっと整理してみましょうか。

1. (eq? x a)が成り立った時点で、xは(Schemeの仕様上そう言う定義は無いが)アトムである事が決定している。-> つまりこれは独立して括り出せる。


2. 残りはpair? => #tかアトムであるけどeq? => #fじゃないか、の二つの枝である。


3. (cons 何とか1 何とか2)の中身が部分的に重複しているパターンが多い

の3点が分かりますね。実際そうなんです。
1番目を考慮すると、コードは取りあえず次のように書けば良いのが分かります。

(define (rember1* a l)
  (if (null? l)
      '()
      (let ((x (car l)) (y (cdr l)))
 (if (eq? x a)
     y
     ...)

これで1番目は綺麗に処理されます。あとはpair?の中身のパターンわけをどうするのか、って事なんですけど……。並べて見てみますか。

(cons (if it x av) (if it (rember1* a y) y))
(cons x (rember1* a y))

第一引数に着目します。候補の引数の中身はxかavの二種類の可能性しかない、って事がお分かりでしょう。当たり前ですよね。
そして、もう一つ重要なのは、xがpair? => #t「だからこそ」再帰でrember1*を噛ます必要性があるのであって、そうじゃなければそんな事する必要がない、のです。そして、再帰噛ました結果とxが等価であるかどうかは第一引数に付いてはロジック上丸っきり関係がありません。その判定が必要なのは第二引数の方なのです。
従って、第一引数は一つのシンボルavで表現して、avはSchemeの有難いif式を利用して束縛します。

(define (rember1* a l)
  (if (null? l)
      '()
      (let ((x (car l)) (y (cdr l)))
 (if (eq? x a)
     y
     ;; av を次のような条件式で束縛する。
     (let ((av (if (pair? x) (rember1* a x) x)))
       ...)

これでxがpair? => #tだったらavは(rember1* a x)に束縛されるし、そうじゃなかったらxに束縛されます。
これにより、ここのletの本体は

(cons av ...)

と書ける事が決定しました。他に何も必要がないのです。こう言う大技が繰り出せるのも、Schemeが文を持たないお陰です。有難や有難や。
ではconsの第二引数はどうなんでしょうか?これは(equal? x av) => #fの「時だけ」yである必要があり、デフォルトでは(rember1* a y)である、ってのが条件なんです。
従って、完成コードは、

(define (rember1* a l)
  (if (null? l)
      '()
      (let ((x (car l)) (y (cdr l)))
 (if (eq? x a)
     y
     (let ((av (if (pair? x) (rember1* a x) x)))
       (cons av (if (equal? x av) (rember1* a y) y)))))))

となりました。随分とスッキリしたでしょ?ネストが減ったように見えて、結構フラットな印象になったと思います。また、コードの「意味」も追いやすくなったんじゃないかな、と思います。