Standard MLで二分木を扱う際、各ノードの値を変換するmap関数は基本的な再帰処理としてよく利用されます。一方で、左の子・右の子・親の順番で処理するpost-order走査のfold関数を使ってmapを表現できるかどうかは、木構造の再帰処理を理解する上で重要なテーマです。この記事では、foldPostの考え方と、二分木のmapを実現するための方針について詳しく解説します。
二分木のmapとfoldPostの役割の違い
二分木に対するmap関数は、各ノードが持つ値に関数を適用し、元の構造を保ったまま新しい二分木を作成する処理です。
例えば、整数を持つ二分木に対して全ての値を2倍するmapを考えると、NODE(左部分木,値,右部分木)という構造を維持しながら、値だけを変換した新しいNODEを返します。
一方、foldPostは木を走査しながら最終的に1つの値へ畳み込むための関数です。型を見ると、foldPost : ('a * 'b -> 'b) -> 'b -> 'a tree -> 'bとなっており、返り値は木ではなく単一の値になります。
foldPostだけで通常のmapを作る場合の問題点
foldPostの型を確認すると、入力として二分木を受け取りますが、結果として返せるものは型変数’bの値です。
つまり、'bに'a treeを設定すれば木を返すことは可能です。しかし、その場合は畳み込み処理の途中で子の結果を利用して新しいNODEを組み立てる必要があります。
post-orderでは左の子、右の子、親の順番で処理されるため、親を処理するときには左右の子についてすでに変換済みの結果を利用できます。この点ではmapとの相性は悪くありません。
foldPostでmapを表現するための考え方
foldPostを使ってmapを作る場合のポイントは、foldの累積値として「変換済みの部分木」を持たせることです。
例えば、以下のような流れになります。
- 左の部分木をfoldPostで処理する
- 右の部分木をfoldPostで処理する
- 最後に親の値へ関数を適用し、NODEとして再構築する
post-orderでは親を処理する時点で左右の子の処理結果が存在するため、mapのような構造保存型の処理を実装できます。
実装時に必要になる型の工夫
標準的なfoldPostの型では、処理関数は'a * 'b -> 'bとなっています。しかし、二分木のmapでは左右の子の結果を両方利用する必要があります。
そのため、実際には単純な値だけではなく、左右の結果を保持できるような型を’bとして設計する必要があります。
例えば、以下のように累積値を二分木そのものにする考え方があります。
foldPost (fn (x, t) => NODE(変換済み左木, f x, 変換済み右木)) NIL treeただし、提示されたfoldPostの型だけでは、左右の子の結果を同時に渡す仕組みが見えないため、そのままではmapを書くには情報が不足する場合があります。
foldPostの定義によって可能性が変わる理由
同じ名前のfoldPostでも、実装方法によって保持できる情報量が変わります。
例えば、処理関数に「左の結果」「右の結果」「現在のノード値」の3つを渡す形式なら、mapは自然に実装できます。
しかし、現在の型である('a * 'b -> 'b)では、ノードの値と1つの累積結果しか受け取らないため、左右両方の変換結果を直接利用することができません。
mapを実装するなら通常の再帰の方が自然
二分木のmapは、実際にはfoldよりも直接再帰で書く方が分かりやすい処理です。
例えば、以下のような考え方になります。
- NILならNILを返す
- NODEなら左右の子を再帰的にmapする
- 親の値だけ関数適用する
この処理では木構造そのものを自然にたどることができるため、末尾再帰化などの最適化を考えない限り、可読性も高くなります。
まとめ：foldPostでmapは条件付きで実現可能
post-order走査は、左の子・右の子・親の順番で処理するため、理論上は二分木のmapを実現することが可能です。
ただし、提示された('a * 'b -> 'b)というfoldPostの型では、左右両方の子の結果を利用する情報が不足するため、そのままでは実装が難しくなります。
foldPost側の定義を変更して左右の結果を渡せるようにするか、累積値として木全体を扱う設計にすれば実装できます。一方で、単純なmapなら通常の再帰関数として書く方がStandard MLでは自然な方法です。
コメント