kb84tkhrのブログ

何を書こうか考え中です

Scheme修行(1) はじめに & 第11章

はじめに

「訳者まえがき」や「はじめに」はだいたいScheme手習いと似たようなことが書いてあるので
さらっといきます

継続(continuation)と代入(set!)という新たな概念を使用してプログラミングの幅を広げている

継続はともかくとして、代入なんて、と思ってると足元をすくわれそうな予感がします

リストはLispの心臓であるが、関数は魂

心臓と魂とではどっちが重要なんでしょうね

この本の目的は、読者に計算の性質について考えることを教えることにある

手習いでは「この本の目的は、読者に再帰的に考えることを教えることにある」と書いてありました
「計算の性質」とはなんでしょうか

この本を5回未満で読み切ろうとしないこと

手習いでは「この本を2回以下で読み切ろうとしないこと」
最後まで読むのを5回繰り返せと言っているんでしょうか
4回挫折してもいいから5回目まであきらめずに読め、って言っているんでしょうか

前の本からの繰り返しになるが、多くの例に食べ物が現れる。

そうですね

食べ物がちょっとした気晴らしになって、この本を一度にあまりたくさん読まないで済むことを願っている。

ちょっとずつ読んだほうがいいようです

第11章 おかえりなさい、ようこそショーへ

Scheme手習いが10章で終わっているので続きということですね

two-in-a-row?

ラットの中に同じ要素が続けて2回出てきたら#tを返す、two-in-a-row?を作ります

(define two-in-a-row?
  (lambda (lat)
    (cond ((null? lat) #f)
          ((is-first? (car lat) (cdr lat)) #t)
          (else (two-in-a-row? (cdr lat))))))

(define is-first?
  (lambda (a lat)
    (cond ((null? lat) #f)
          ((eq? (car lat) a) #t)
          (else #f))))

is-first?alatの先頭にあるかどうかを返す関数です
たぶんこれが、素直に書くとこうなるよねっていう例なのかと思われます

(is-first?)#fと答える場合が2通りあるのは本当ですか。
はい。latが空の時、または、リストの最初の要素がaではないときに#fを返します。

(null? lat)two-in-a-row?is-firstの両方で行われています
(cdr lat)null?でないことを確認した後、
(two-in-a-row? (cdr lat))の中でまた(cdr lat)null?でないことを
確認しますのでもったいないですね

(cdr lat)を2回やってるのももったいないです

テキストにはまずこういう修正版が出てきます

(define two-in-a-row?
  (lambda (lat)
    (cond ((null? lat) #f)
          (else (is-first-b? (car lat) (cdr lat))))))

(define is-first-b?
  (lambda (a lat)
    (cond ((null? lat) #f)
          (else (or (eq? (car lat) a)
                    (two-in-a-row? lat))))))

is-first-b?の意味合いが変わってしまいました
alatの先頭にあるかどうかだけでなく
こんどはtwo-in-a-row?を呼び出してlatの中にaが続けて現れるかも判定しています
ちょっと継続呼び出しみたいな雰囲気も漂わせます

これも動きますがlatが空であるというチェックは相変わらず重複しています
two-in-a-row?is-firstが相互に再帰するようになったというところが
ちょっとおもしろいところではありますが、具体的に何かよくなったのかというと
そんな気はしません

ただの中間生成物なんでしょうか

is-first-btwo-in-a-row?を呼んだ後two-in-a-row?が何をするかといえば
無駄にlatが空かどうかをチェックしてis-first-bを呼んでいるだけです
ということは、is-first-b自身がis-first-bを呼べばいいんですね

(define two-in-a-row?
  (lambda (lat)
    (cond ((null? lat) #f)
          (else (is-first-b? (car lat) (cdr lat))))))

(define is-first-b?
  (lambda (a lat)
    (cond ((null? lat) #f)
          (else (or (eq? (car lat) a)
                    (is-first-b? (car lat) (cdr lat)))))))

しかしここで
is-first-b?がもはやis-first?よりもtwo-in-a-rowに近いことに気がついたので
名前を変えることにします

(define two-in-a-row?
  (lambda (lat)
    (cond ((null? lat) #f)
          (else (two-in-a-row-b? (car lat) (cdr lat))))))

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

無駄なnull?cdrがなくなりました
構造も最初の要素だけ特別扱いだよ、っていうことが素直にあらわれた感じです

two-in-a-row-b?の自然な再帰は何ですか。
自然な再帰(two-in-a-row-b? (car lat) (cdr lat))です。
ちょっと変わっていますね。
はい。関数では第2の引数についてのみ質問しているのに、両方の引数が変わりますから。

あんまり意識してませんでしたが言われてみるとそういうのはなかったかもしれません

sum-of-prefixes

タップを引数に取り、タップの各要素までの和をリストにして返す関数sum-of-prefixesを作ります

(define sum-of-prefixes
  (lambda (tup)
    (cond ((null? tup) (quote ()))
          (else (sum-of-prefixes-b 0 tup)))))

;+はあることにする
(define sum-of-prefixes-b
  (lambda (sonssf tup)
    (cond ((null? tup) (quote ()))
          (else (cons (+ sonssf (car tup))
                      (sum-of-prefixes-b (+ sonssf (car tup))
                                         (cdr tup)))))))

どうやらこの章のテーマは過去の情報を引数で渡すということのようです
それは大事な概念なんでしょうか?
何かの前振り?

第11の戒律
ある関数が、その関数に対する他の引数がいかなるものか知る必要があるときは、付加的な引数を用いるべし。

おお、なるほど!という感じはあまりしません
理解が足りないんでしょうか
5回読んだらおおなるほどってなる?
訳がこなれてない感じもします
名訳だったらなるほどかっていうとそんな気もしませんが

scramble

次はscarambleという関数を作ります
自分では説明できないので引用します

関数scrambleは、どの数も自分の位置を示す番号より大きくない空でないタップを取って、同じ長さのタップを返します。
引数の中のそれぞれの数は、自分を起点としてタップを逆方向にさかのぼる数として扱われます。
各位置の結果は、その数のぶんだけ現在の位置から逆向きにたどることで見つけられます。

これはコード見たほうがわかりやすいかも・・・

(define scramble
  (lambda (tup)
    (scramble-b tup (quote ()))))

(define scramble-b
  (lambda (tup rev-pre)
    (cond ((null? tup) (quote ()))
          (else (cons (pick (car tup) (cons (car tup) rev-pre))
                      (scramble-b (cdr tup)
                                  (cons (car tup) rev-pre)))))))

戒律通りですね、という以外にあまり書くことがありません・・・

この章で著者は何を伝えたかったんでしょうか
「計算の性質」は出てきたんでしょうか
ちょっと変わった自然な再帰つまり第11の戒律のことを言えれば満足なのでしょうか
大事な技だとは思いますが

わかりません
タイトルを付けることができません