Scheme手習い 第９章 ……もう一度、もう一度、もう一度、……（その２）

明確に書いていないので分かりにくいが、ここでは二分木の操作が紹介されます。

ノート：

shift

shiftが何をしているのか、言葉の説明を見てもリストの形式で見ても何が起きているのか分かりにくい。

挙げられた例を模式図にすると：*1

  .
 / ＼
 .   c
/ ＼
a  b

が

 .
/ ＼
a   .
   / ＼
   b  c

となり、また

   .
  / ＼
 .   .
/ ＼ / ＼
a  b c  d

が

 .
/ ＼
a  .
  / ＼
  b  .
    / ＼
    c  d

となる。
つまり

1. 葉の左右の順番は保存したまま
2. 木構造のルートの位置を左の枝の先に移動させる

結果として、ルートの右の枝の先には元の左の枝の右の葉と元のルートの右の枝の先が繋がる。

実際に評価してみる。

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

align

言葉にすると

1. アトムであれば、そのアトム
2. 左のノードが葉でなければ、現在のルートを左に移動させて更にalignを適用した木
3. 左のノードが葉であれば、左の葉と右のノードにalignを適用した物を繋いだ木

alignは毎回新しい木構造を作るのでbuildでノードを作る必要がある。
どのノードを取っても左のノードが葉になるまで再帰するので、結果として、ノードの左が全て葉となり右側に広がる二分木と定義出来る。

全ての右のノードが葉となっている二分木にalignを適用すると：

> (align '(((((a b) c) d) e) f))
(a (b (c (d (e f)))))
> 

二分木をイメージすると確実にゴールとなる形があり、そこに近づいている事が分かるが、それを値として示す事は単純ではない。

length*

length*は二分木を走査してアトム（葉）に出会う度に１と数えるので、全体として二分木に含まれている葉の数を数える。

> (length* '(((a b) (c d)) (d e)))
6
> 

length*の値ではalignが再帰する毎にその値が変わる事はないのでゴールに近づいている事を示す事は出来ない。

weight*

weight*はノードの左にある葉の数を２倍に計算する。

> (weight* '((a b) c))
7
> (weight* '(a (b c)))
5
> (weight* '(((((a b) c) d) e) f))
63
> (weight* (align '(((((a b) c) d) e) f)))
11
> 

全てがalignされて、各枝の左には葉しか無い状態になれば、weight*の値は（葉の数×２−１）となり、その値はweight*の最小の値となりそう。

再帰によって引数のデータ構造そのものが小さくならなくても、何らかの適切な尺度で測った時に再帰の度に小さくなっていれば再帰は収束すると言えそう。

shuffle

shuffleの定義はalignと同じ構造だがshiftではなく左右の葉を入れ替えるrevpairを呼ぶ。葉の値に注目する訳でもなく左のノードが木（ペア）か否かだけで判断している。あるノードの左右が木（ペア）の場合revpairで入れ替えた所で左右が木（ペア）である事には変わらず、それをまたshuffleに渡してしまってはこのループは終わらない。

> (let ((x '(a (b c))))
    (shuffle x))
(a (b c))
> (let ((x '(a b)))
    (shuffle x))
(a b)
> (let ((x '((a b) (c d))))
    (shuffle x))
. . user break

左右が木となるノードが含まれている木では関数値が決まらないので全関数ではない。

*1:pre記法の中では\がどうしても￥になってしまうので全角（懐かしい言葉）の＼で何とか凌ぐ