kb84tkhrのブログ

何を書こうか考え中です

Scheme修行(2) 第12章

multirember

第12章「避難しましょう」ではまずmultiremberを題材にします

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

multiremberlatを横断すると、aは変わりますか。

いいえ、aはいつもtunaを表しています。

それなら、aがずっとtunaを表していることを、自然な再帰のたびにmultiremberに思い出させる必要はないですよね。

はい。このような関数を読むときは、そのほうがとても助かります。

一理あると思いますが、助かるっていうのは人間が助かる話なんでしょうか
それともCPUが助かる?

Yを使って書くとこのようになります

(define multirember
  (lambda (a lat)
    ((Y
      (lambda (mr)
        (lambda (lat)
          (cond ((null? lat) (quote ()))
                ((eq? (car lat) a) (mr (cdr lat)))
                (else (cons (car lat) (mr (cdr lat))))))))
     lat)))

これを以下のように書くことができます

(define multirember-r
  (lambda (a lat)
    ((letrec
         ((mr (lambda (lat)
                (cond ((null? lat) (quote ()))
                      ((eq? (car lat) a) (mr (cdr lat)))
                      (else (cons (car lat) (mr (cdr lat))))))))
       mr)
     lat)))

(letrec ((mr ...)) mr)はmrという名前の再帰関数を定義して、その再帰関数を返しています
なんとなく冗長なことをやってる気がしないでもないですが
mrの定義の中でmr自身を呼べてしかもYと同等のことがわかりやすく書けます、といったところ

でも、欲しいのが再帰関数mrなら、なぜこうしないのですか。

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

(define multirember-d
  (lambda (a lat) (mr lat)))

まあ普通にダメって感覚なんですが
聞きかじりの知識からすると、動的スコープな言語ならこれでも動いたりするんでしたっけ
Schemeは静的スコープの言語だから、ってことを言おうとしている?

こういう書き方もできます

(define multirember-r2
  (lambda (a lat)
    (letrec
        ((mr (lambda (lat)
               (cond ((null? lat) (quote ()))
                     ((eq? (car lat) a) (mr (cdr lat)))
                     (else (cons (car lat) (mr (cdr lat))))))))
      (mr lat))))

Scheme修行には出てこない書き方ですがこう書くこともできます

(define multirember-d
  (lambda (a lat)
    (define mr
      (lambda (lat)
        (cond ((null? lat) (quote ()))
              ((eq? a (car lat)) (mr (cdr lat)))
              (else (cons (car lat) (mr (cdr lat)))))))
    (mr lat)))

ほとんど同じなんですが
こちらではなくてletrecを使っているのは
コンピュータサイエンス的にletrecのほうが由緒正しい書き方とか?

Yよりはましです。

はげしく同意です

第12の戒律
再帰を適用している間に変化せぬ引数を除くにはletrecを用いるべし。

確かにaを渡さなくて済むようになりましたが、カッコが増えました
ムダが減っていることは確かなんですが、読みやすくなったんでしょうか?
戒律は、「変化せぬ引数を除け」とは言ってないので、読みやすくなるときだけ除けばいい?

これも「計算の性質」なのかなあ?

さらにmultirember

同一性判定の関数を引数に取るmultiremberを作ります

(define multirember-f
  (lambda (test?)
    (lambda (a l)
      (cond ((null? l) (quote ()))
            ((test? (car l) a) ((multirember-f test?) a (cdr l)))
            (else (cons (car l) ((multirember-f test?) a (cdr l))))))))

(multirember-f test?)の値は繰り返しの間変化しないので、letrecを使います

(define multirember-f2
  (lambda (test?)
    (letrec
        ((m-f
          (lambda (a l)
            (cond ((null? l) (quote ()))
                  ((test? (car l) a) (m-f a (cdr l)))
                  (else (cons (car l) (m-f a (cdr l))))))))
      m-f)))

multirember-f2eq?を渡してやります

(define multirember-f3
  (letrec
      ((mr (lambda (a lat)
             (cond ((null? lat) (quote ()))
                   ((eq? (car lat) a) (mr a (cdr lat)))
                   (else (cons (car lat) (mr a (cdr lat))))))))
    mr))

さらにmrmultiremberに変えます
いったい何をやっているんでしょうか

(define multirember-f4
  (letrec
      ((multirember
        (lambda (a lat)
          (cond ((null? lat) (quote ()))
                ((eq? (car lat) a) (multirember a (cdr lat)))
                (else (cons (car lat) (multirember a (cdr lat))))))))
    multirember))

このletrecは定義した関数をそのまま返しているだけですので取り除くことができます

(define multirember-f5
  (lambda (a lat)
    (cond ((null? lat) (quote ()))
          ((eq? (car lat) a) (multirember-f5 a (cdr lat)))
          (else (cons (car lat) (multirember-f5 a (cdr lat)))))))

おなじみのmultiremberに戻るでしょう。

multirember-feq?を渡すとmultiremberになることを論証してたということ?

rember-eq?は本当にremberですか。
そうです。でもちょっと待って下さい。あとでもう少し考えます。

の答えだった?
multiremberになってますが

union

unionをいじります
これが原型

(define member?
  (lambda (a lat)
    (cond ((null? lat) #f)
          ((eq? (car lat) a) #t)
          (else (member? a (cdr lat))))))

(define union
  (lambda (set1 set2)
    (cond ((null? set1) set2)
          ((member? (car set1) set2) (union (cdr set1) set2))
          (else (cons (car set1) (union (cdr set1) set2))))))

繰り返しの間set2は変化しないのでletrecに入れます

(define union-r
  (lambda (set1 set2)
    (letrec
        ((U (lambda (set)
              (cond ((null? set) set2)
                    ((member? (car set) set2) (U (cdr set)))
                    (else (cons (car set) (U (cdr set))))))))
      (U set1))))

もしかしてmember?を誰かが変にいじってしまっても動くように、
自前でmember?を持つことにします
そんなの気にしないとか言わない

(define union-m
  (lambda (set1 set2)
    (letrec
        ((U (lambda (set)
              (cond ((null? set) set2)
                    ((M? (car set) set2) (U (cdr set)))
                    (else (cons (car set) (U (cdr set)))))))
         (M? (lambda (a lat)
               (cond ((null? lat) #f)
                     ((eq? (car lat) a) #t)
                     (else (M? a (cdr lat)))))))
      (U set1))))

これで終わりではありません
M?が変化しない引数を持っているので、letrecに入れてやります

(define union-m2
  (lambda (set1 set2)
    (letrec
        ((U (lambda (set)
              (cond ((null? set) set2)
                    ((M? (car set) set2) (U (cdr set)))
                    (else (cons (car set) (U (cdr set)))))))
         (M? (lambda (a lat)
               (letrec
                   ((N? (lambda (lat)
                          (cond ((null? lat) #f)
                                ((eq? (car lat) a) #t)
                                (else (N? (cdr lat)))))))
                 (N? lat)))))
      (U set1))))

ここまでやるかなあ?という気もしますが・・・
原型の方が読みやすい気がするし
チームで書くなら原型くらいにしておくかな、という気分
戒律が共有できていればいいですけど

DRY原則を崩してる気がするのもちょっと

第13の戒律
関数を隠し、守るには、(letrec ...)を用いるべし。

その関数からしか呼ばれない関数は隠すようにします
member?みたいなのは標準のライブラリ関数みたいなものなので
やっぱり別扱いなんだろうなあ

two-in-a-row?

さっきまでの調子でletrecを使うとこのようになります

(define two-in-a-row-r?
  (lambda (lat)
    (letrec
        ((W (lambda (a lat)
              (cond ((null? lat) #f)
                    (else (or (eq? (car lat) a)
                              (W (car lat) (cdr lat))))))))
      (cond ((null? lat) #f)
            (else (W (car lat) (cdr lat)))))))

しかし、よく見るとtwo-in-a-row-r?の変数をWで共有する必要はありません
ということでこうも書けます

(define two-in-a-row-r2?
  (letrec
      ((W (lambda (a lat)
            (cond ((null? lat) #f)
                  (else (or (eq? (car lat) a)
                            (W (car lat) (cdr lat))))))))
    (lambda (lat)
      (cond ((null? lat) #f)
            (else (W (car lat) (cdr lat)))))))

不必要に変数が見えないので、こっちのほうがよりよい書き方なんでしょうね

もうあとのsum-of-prefixscrambleはただの練習です

(define scramble-r
  (letrec
      ((P (lambda (tup rp)
            (cond ((null? tup) (quote ()))
                  (else (cons (pick (car tup)
                                    (cons (car tup) rp))
                              (P (cdr tup)
                                 (cons (car tup) rp))))))))
    (lambda (tup)
      (P tup (quote ())))))

12章のまとめ

  • 繰り返しの間変わらない変数はローカルな関数を定義して渡さないようにすることを覚えました
  • ローカルに関数を定義し、外部から隠すことを覚えました
  • 「避難しましょう」って何?