日: 2014年1月30日

shuffle

今度はわかるぞ。
shuffle は align と似ているけど、7章で出てきた revpair を使う。

(use mymodule)

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

(define shuffle
  (lambda (pora)
    (cond
      ((atom? pora) pora)
      ((a-pair? (first pora)) (shuffle (revpair pora)))
      (else (build (first pora) (shuffle (second pora)))))))

(print (shuffle '(a (b c))))
(print (shuffle '(a b)))
^o^ > gosh -I. shuffle.scm
(a (b c))
(a b)

うまく動いているようだ。ということは全関数なんだろうか。
ここで、(shuffle '((a b) (c d))) の値を求めてみる。引数の第1要素がペアなので、cond の2番目に当たる。すると (shuffle (revpair '((a b) (c d)))) と再帰してこれは (shuffle '((c d) (a b))) に同じ。さらに進めるとまた cond の2番目にあたり、(shuffle (revpair '((c d) (a b)))) となり、これは (shuffle '((a b) (c d))) と同じになる。つまり、最初と同じになってしまう。
というわけで、shuffle は引数によっては停止しない部分関数ということになる。

align

うーん、問答についていけなくなった。

順を追っていこう。
まずは関数 shift。これは、ペアのペアを引数にとって、ペアの第1要素の第2要素を、ペアの第2要素に移し変える（ややこしいな）。

(use mymodule)

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

(print (shift '((a b) c)))
(print (shift '((a b) (c d))))
^o^ > gosh -I. shift.scm
(a (b c))
(a (b (c d)))

うん、ここまではOK。
次、align。この関数は、

  1. 引数がアトムならそのまま返す。
  2. 引数の第1要素がペアなら、shift して再帰する。
  3. そうでなければ、第1要素と、第2要素について再帰したものでペアを作る。
(use mymodule)

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

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

(print (align 'a))
(print (align '(a (b c d))))
(print (align '((a b) (c d))))
(print (align '((a b c) (d e f))))
^o^ > gosh -I. align.scm
a
(a (b c))
(a (b (c d)))
((a b c) (d e))

まだ大丈夫、これもわかる。
この align は前回のエントリに出てきた keep-looking と共通するところがあって、それはどちらの関数も引数を変更して再帰するけど、その変更によってゴールに近づいている保証がないことだそう。
ここで問答は aling の cond の2つ目の行に注目する。(arign (shift para)) というふうに再帰しているけど、その引数はもとの引数の一部ではなく、第7の戒律に反しているという。確かに shift はペアの要素を並べ替えるだけなので、一部ではない。言い換えると新たな引数にはもとの引数と同じ数のアトムが含まれている。

(use mymodule)

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

(define length*
  (lambda (para)
    (cond
      ((atom? para) 1)
      (else (o+ (length* (first para)) (length* (second para)))))))

(print (length* '((a b) c)))
(print (length* (shift '((a b) c))))
^o^ > gosh -I. length_star.scm
3
3

まあ、確かめるまでもなく同じになる。

さて、わからなくなるのはここからだ。align を再帰する際に、ペアの第1要素はより簡単になっているけど第2要素はより複雑になっているという。確かに shift によってそうなっている。だけど、「引数の長さを決めるのに length* は間違った関数ではないでしょうか。」「もっとよい関数では、第1要素にもっと注意を払わなければいけません。」とはどういうことだろう。「少なくとも２ばいは必要です。」とは？
もっとよい関数として weight* が出てくる。

(use mymodule)

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

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

(print (weight* '((a b) c)))
(print (weight* (shift '((a b) c))))
^o^ > gosh -I. weight_star.scm
7
5

weight* の動作自体はわかる。第1要素の数に2を書けることによって重み付けをしている。結果、shift するとアトムが第1要素から第2要素に移動する分だけ値が小さくなるわけだ。
で、これがなぜ次の問答につながるのかがわからない。
「align は部分関数ですか。」「いいえ。すべての引数に対して値を持ちます。」

うーん、誰か解説してほしい･･････