立ち戻る

The Little Schemer

さて、length*関数が出てくるまでのやりとりについて振り返ってみる。
何か見えてくるかもしれん、との淡い期待を込めて。

  • L

じゃぁ、この関数を見てみて。

(define align
  (lambda (pora)
    (cond
     ((atom? pora) pora)
     ((a-pair? (first pora)) (align (shift pora)))
     (else (build (first pora) (align (second pora)))))))

keep-looking関数との共通点は何か分かる？
（keep-looking関数やら、align関数で使われている関数の定義は後ほど...）

  • R

どっちの関数も再帰呼び出しの際の引数として用いるため、自分の引数を変更するよね。
だけどどっちの関数も、引数を変更することで再帰の終了条件へ近づいているとは限らない、ってことが共通点かな。

  • L

align関数が終わらないかもしれないってのは、なして？

  • R

condの2つ目のケースでshiftの関数値がalignの引数になってるけど、それは元の引数の一部分ではないからね。

  • L

ってのは、どの掟を破っているのかな？
（掟ってのは、The Little Schemerで述べられている「10の掟」を指しています。）

  • R

掟、其の七だね。

  • L

新しい引数は少なくとも元の引数よりも小さくなっていると言えるかな？

  • R

そうとも言えないね。

  • L

それはナゼ？

  • R

shift関数は引数のペア（後に示しているa-pair?関数を#tにするようなリスト。以下でも便宜的に「ペア」と呼ぶ。）の並べ替えしか行わないからね。

  • L

ってことはどういうこと？

  • R

関数の値と引数は、同じ個数のアトムを持つってことさ。

といった前置きがあり、id:yagiey:20080319に続いていくわけだ。
...やっぱりわからん。
アトムの個数を数えるという点において、length*関数は完全に正しいと思うのだが。


では、weight*関数がどんな値を返すかという点から、論理を推測出来まいか。
weight*関数の定義は以下。

(define weight*
  (lambda (pora)
    (cond
     ((atom? pora) 1)
     (else (+ (* 2 (weight* (first pora)))
	      (weight* (second pora)))))))

うむ、ペアがもつアトムの個数が等しくても、ペアの先頭にあるか末尾にあるかで数え方が違うのね。

gosh> (weight* '((a b) c)))
7
gosh> (weight* '(a (b c)))
5

ってなわけだ。
この実行例で、1番目の評価に使った引数を引数にshiftを評価すると、2番目の評価に使った引数と同じものになるよな。
つまり、

gosh> (shift '((a b) c))
(a (b c))

ってこと。
ここから何か推測出来ないか...。

　　 　 　 　 　 　 　 /|:::::::::::::::::::::ヽ.:.:.:.:､:.:.:.:､:.:.:.､.:.､.:.:.:.:.:.::｀゛＞
　　　　　　　　　　 /{::|:＼:::::::＼.:.:.:＼.:.:.ヽ::.::.ヽ:.:.ヽ::::::::::.:.｀゛ｰ- ..,__
：　何　：　　　　／:|::',:ﾄ､::::::ヽ､:.＼:.:.:.＼:.:.ヽ:.:.:＼.:.:.:.:.:::.:.:.:.:::.::::_;:-'´　　 ：　：　：
：　が　：　　　//:/:::|::',|::'､:::::::::＼:.:＼.:.:.ヽ:.:.:＼:.:..＼::::::::::::＼､::::＼　 　 ：　：　：
：　何　：　　/!::|::l::::/|:::l:ヽ:＼::ヽ:.:＼:.:＼.:::ヽ:.:.:ヽ:.:.:.:＼::::::::::::＼￣　　　：　：　：
：　だ　：　　 |/l::|::|::|:ﾄ､:::::::::､､:ヽ､:.:.:.:::::::::::::::ヽ::::.:ヽ:.:.:.:.＼:.:.:.ヽ:::＼.　　 ：　：　：
：　か　：　　 |::|::/l::|::|r‐ヽ:::::ヽ(ヽー,―＼::::::､::::::::::ヽ::.:.::::::.:::::::ヾ.￣　　 ：　：　：
：　　 　：　　 }//l::|:::|{（:::）ヾ､:::ヽ ＼!（:::） ヽ,:::ヽ:::::::::::::::::::::::::::::::::::ヾ、 　 ：　：　：
：　わ　：.　　|/l::|::|:::|ヽ==''" ＼:ヽ、ヽ=＝'" |:::::::::::::::::::::::::::::::::::ヽ､::::＼
　　か 　 　 /　',|::|:::|　　　/　　 ｀゛　　 　 　 |!::::::::::::::::::::::::::::ﾄ､::ﾄ､_｀ ゛`
　　ら　　　　　　l::!::::ﾄ、 　'､　_　　　　　　 　 ||::::::::::::::::::::::::ﾄ:ヽヾ|　|￣￣￣｀ヽ、
　　な　　 　 r'"´||',::::',　　　　 　 　 　 　 　 　 |:::::/l:::::|＼:::ﾄ､ヾ |　| 　 　 ／　/ ＼
　　い　　　/ 　　ll　',::', 、 ｰこﾆ=-　　　　 　 /!::/ ヽ:::|　 ヾ､ 　ﾉ ﾉ　　／ 　,ｲ　　　ヽ、
　　　　 　 ,'　　　 | 　'､:, ＼　--　　 　 　 ,. '´　|;'　 l ヾ､. 　 ／／　　　　　/ |　　　　l: l
　　　　　　|　　　|!　　ヽ; 　ヽ 　 　 　 ／.:　 　 i! 　/ 　 ゛／／　|l　 　 　 /　|　 　 　 | |

...だめだ。
まったく分からん。
length*がダメな理由とweight*が何のためにひきあいに出されているのか。


だれかトラバでもコメントでも良いんで、ヒント教えてくれないかな。
さっさととばして先に進んでいいものか。
いやだなぁ。
これじゃあ、いつまでたってもSeasonedに進めない。
SICPにたどりつくのはいつになる事やら...。


最後に、align関数で使われている関数、keep-looking関数の定義は以下に書いておこう。

(define shift
  (lambda (pair)
    (build
     (first (first pair))
     (build (second (first pair)) (second pair)))))

(define align
  (lambda (pora)
    (cond
     ((atom? pora) pora)
     ((a-pair? (first pora)) (align (shift pora)))
     (else (build (first pora) (align (second pora)))))))

(define a-pair?
  (lambda (x)
    (cond
     ((atom? x) #f)
     ((null? x) #f)
     ((null? (cdr x)) #f)
     ((null? (cdr (cdr x))) #t)
     (else #f))))

;; atomかどうか判断
(define atom?
  (lambda (s)
    (and (not (pair? s)) (not (null? s)))))

;; 1つ目のS式を取得
(define first
  (lambda (l)
    (car l)))

;; 2つ目のS式を取得
(define second
  (lambda (l)
    (car (cdr l))))

;; 2個のS式からリストを作成
(define build
  (lambda (e1 e2)
    (cons e1 (cons e2 '()))))

(define keep-looking
  (lambda (a sorn lat)
    (cond
     ((number? sorn) (keep-looking a (pick sorn lat) lat))
     (else (eq? sorn a)))))

(define pick
  (lambda (n lat)
    (cond
     ((= n 1) (car lat))
     (else (pick (- n 1) (cdr lat))))))