さて、先のように木を作っても使えなくてはしようがないので、作った木に対して何か処理や操作をする手段が必要です。そのためにMLではパターンマッチングという仕組みを用います。
たとえば、int_treeの葉の値を合計する関数int_tree_sumは、以下のように定義できます。
# let rec int_tree_sum t =
match t with
Leaf i -> i
|
Node(l, r) -> int_tree_sum l + int_tree_sum r ;;
val int_tree_sum : int_tree -> int = <fun>
# int_tree_sum (Node(Node(Leaf 3, Leaf 5), Leaf 7)) ;;
- : int = 15
まず、関数int_tree_sumは引数tを受け取ります。その次のmatch ... with ...という式がパターンマッチングです。そもそも「int_treeはLeafまたはNodeである」と定義したので、int_tree について調べたかったら、まずLeafなのかNodeなのか場合わけして、もしLeafだったら中身の整数を、Nodeだったら左の枝と右の枝を調べることになります。上の例では、tがLeaf だったら中身の整数iを返し、Nodeだったら左の枝lと右の枝rのそれぞれについて、関数int_tree_sumを呼び出して再帰を行っています。make_random_treeの場合と同様に、再帰データ構造である木に対する処理が、再帰関数によって非常に自然に記述できることがわかります。
なお、このような関数の定義ではlet f x = match x with ...という形がよく出てくるので、省略することが可能になっています。たとえば
# let rec int_tree_sum = function
Leaf i -> i
|
Node(l, r) -> int_tree_sum l + int_tree_sum r ;;
val int_tree_sum : int_tree -> int = <fun>
という具合です。一般にfun x -> match x with ...というパターンマッチング関数を、function ...のように省略することが可能です。