TeX での「代数的データ型」の扱い (3)

（前回の続き）

前回までで、「代数的データ型の扱い」の例として「Cons 対によるリスト」を扱った。しかしやはりリストでこの表現を使うのは（TeX では）少し大袈裟な感じがすることは否めない。そこで「代数的データ型の例」としてリストの次に必ず出てくる「二分木」を同じ手法で扱うことにし、その上で 2011-08-31 の問題 の「問題 4」を解いてみる。

二分木の表現

二分木の構築子は以下の通り。

• \xx@Node{<左>}{<右>} ： 内部接点
• \xx@Leaf{<ラベル>} ： 葉

これに即して「問題 4」の例にある木を「変数」 \TestTree に代入してみる。

% plain TeX / TeX on LaTeX 共用
\catcode64=11 %-------------------------
% \xx@freeze@Tree : 構築子を凍結する。
\def\xx@freeze@Tree{%
  \let\xx@Node\relax \let\xx@Leaf\relax}
% テストデータ
\xx@freeze@Tree
\edef\TestTree{% これは \def で間に合うのだが
  \xx@Node
   {\xx@Node
     {\xx@Node{\xx@Leaf{9}}{\xx@Leaf{2}}}%
     {\xx@Leaf{6}}}%
   {\xx@Node
     {\xx@Leaf{4}}%
     {\xx@Node
       {\xx@Leaf{15}}
       {\xx@Node{\xx@Leaf{2}}{\xx@Leaf{4}}}}}%
}%

\catcode64=12 %-------------------------

この表現の下で、各小問の \sumLeaves、\treeDepth、\sumLeavesWithin の動作をするマクロは以下のように実装できる。今回は、木の表現についての文字列形式と構築子形式の間の変換については省略する。（興味のある人は自分で実装してみてほしい。）

% plain TeX / TeX on LaTeX 共用 (前掲のコードへの追加部分)
\catcode64=11 %-------------------------
%% 整数レジスタの定義
\newcount\countResult

%-------- \sumLeaves に相当するマクロ
%% \xx@tr@do@sum@leaves{<木>} : ラベルの総和.
\def\xx@tr@do@sum@leaves#1{%
  \countResult=0
  \let\xx@Node\xx@tr@sum@leaves@@Node
  \let\xx@Leaf\xx@tr@sum@leaves@@Leaf
  #1}
\def\xx@tr@sum@leaves@@Node#1#2{%
  #1#2}
\def\xx@tr@sum@leaves@@Leaf#1{%
  \advance\countResult#1\relax}

%-------- \treeDepth に相当するマクロ
%% \xx@tr@do@tree@depth{<木>} : 深さ.
\def\xx@tr@do@tree@depth#1{%
  \countResult=0
  \let\xx@Node\xx@tr@tree@depth@@Node
  \let\xx@Leaf\xx@tr@tree@depth@@Leaf
  #1}
\def\xx@tr@tree@depth@@Node#1#2{%
  % max(#1の深さ,#2の深さ) + 1 を求める
  \begingroup
    % 再帰呼出があるので \xx@tr@depth@l/r (レジスタ節約の為
    % 整数値マクロとしている) をローカルとしている
    #1\edef\xx@tr@depth@l{\the\countResult}%
    #2\edef\xx@tr@depth@r{\the\countResult}%
    \xdef\xx@tr@gtempa{% max(\xx@tr@depth@l,\xx@tr@depth@r)
      \ifnum\xx@tr@depth@l>\xx@tr@depth@r\space
            \xx@tr@depth@l
      \else \xx@tr@depth@r \fi}%
  \endgroup % この段階で touch-and-go して外に出る
  \countResult=\xx@tr@gtempa
  \advance\countResult1\relax}
\def\xx@tr@tree@depth@@Leaf#1{%
  \countResult=0\relax}

%-------- \sumLeavesWithin に相当するマクロ
%% \xx@tr@do@sum@leaves@within{<木>} : ラベルの総和.
\newcount\xx@tr@level
\def\xx@tr@do@sum@leaves@within#1#2{%
  \countResult=0
  \xx@tr@level=#2\relax
  \let\xx@Node\xx@tr@sum@leaves@within@@Node
  \let\xx@Leaf\xx@tr@sum@leaves@within@@Leaf
  #1}
\def\xx@tr@sum@leaves@within@@Node#1#2{%
  \ifnum\xx@tr@level>0
    \begingroup
      \advance\xx@tr@level-1
      #1#2%
      \xdef\xx@tr@gtempa{\the\countResult}%
    \endgroup
    \countResult=\xx@tr@gtempa\relax
  \fi}
\def\xx@tr@sum@leaves@within@@Leaf#1{%
  \advance\countResult#1\relax}

%% テスト
\xx@tr@do@sum@leaves\TestTree
\showthe\countResult %=> 42
\xx@tr@do@sum@leaves@within\TestTree{2}
\showthe\countResult %=> 4
\xx@tr@do@sum@leaves@within\TestTree{2}
\showthe\countResult %=> 10
\catcode64=12 %-------------------------

リストのソートの場合と同じく、構築子形式の表現を用いると展開制御のほとんどが不要になる。ただし、小問 (2) 以降で必要になる「再帰呼出の際の変数のローカル化」（再帰呼出をグループに入って行う）については、データ構造の表現形式とは無関係の問題だから、ここでも必要である。

（まだ続く）