第７章 座標構造 - プログラミング原論／Elements of Programming Wiki

概要

  　前章は、一連のイテレータコンセプトを紹介しました。
  この章では、さらに複雑な形状を持つ座標構造を扱います。
  分岐座標を紹介し、木走査に繰り返しを扱うマシンを用い、二分木に対するアルゴリズムを実装します。
  最後に、同型、同値性、順序に対するアルゴリズムで締めくくります。
  

7.1 分岐座標

   　前章では、iteratorを使用して全ての位置で1つだけのsuccessorをもつ線形構造の走査を行いました
   本章では、全ての位置で左右の2つのsuccessorをもつ重要なデータ構造を学習します。

   　述語emptyが真の場合、たの述語未定義です。
   無閉路有向グラフ(DAG)の中でも、xの子孫の全てのy,z二体してzがyから左到達可能でも右到達可能でもない、木(tree)を形成します。
   

7.2 双方向分岐座標

   　再帰走査は木の高さに比例したスタックを必要とし、高さは最悪の場合、重さと同じになります。

   　木に、ある座標とその前の座標のスタックを組み合わせることで、
   プレディセサー(predecessor)を得るための追加の変換操作をもつ新たな座標型を得ることができます。

       x0       #=> (x0,  )
      /  \
     y1   y2    #=> (y2, (x0,  ) )
    /  \    \
   z3   z4   z5 #=> (z5, (y2, (x0,  ) ) )

7.3 座標構造

   　個別のコンセプトを定義して、各コンセプトは手続きの集まりとそれらの意味論である。
   コンセプトの集まりに共通な特性を記述する方法であるコンセプトスキーマを定義することも有用である。

   　線形走査を記述している、イテレータコンセプトと
   二分木の走査を記述している、分岐座標コンセプトを定義しました。
   これら任意のデータ構造内での走査を可能とするために、座標構造コンセプトスキーマを導入します。
   

補題及び演習

補題7.1

   heightとwightの関数の戻り値より、 successor(l+r)  successor(max(l,r)) 

補題7.2

   BidirectionalBifurcateCoordinateのコンセプト
   predecessor(right_successor(i))=>は定義されて、iに等しい
   から自明

演習7.1

   矛盾しない

補題7.3

   reachable()が真を返す場合を確認する
   

演習7.2

   変更する

演習7.3

   循環していないか
   

課題7.1

課題7.2