前々回はモジュールとシグネチャについて説明し、前回は簡単な例題として有理数を扱うモジュール Ratio を作成しました。OCaml のモジュール機能はこれだけではありません。もう一つ重要な機能に「ファンクタ (functor)」があります。ファンクタは引数にモジュールを受け取り、それを使って新しいモジュールを生成する機能です。ファンクタはモジュールを生成するモジュールと考えてください。今回は「二分探索木 (binary search tree)」を例題にファンクタを説明します。
あるデータの中から特定のデータを探す場合、データ数が少なければ力任せに探索してもなんとかなりますが、データ数が多くなると探索に時間がかかるようになります。このような場合、あらかじめデータを整理整頓しておくことで、特定のデータを高速に見つけることができるようになります。この代表的なアルゴリズムが「ハッシュ法」と「二分探索木」です。二分探索木はその名が示すように「木構造」の一種です。まずは木構造から説明しましょう。
「木構造 (tree structer)」は「木 (tree)」とも呼ばれるデータ構造で、「節 (ノード)」と呼ばれる要素に対して、階層的な関係を表したものです。身近な例では、ディレクトリの階層構造が木にあたります。ディレクトリに「ルートディレクトリ」があるように、木にも「根 (ルート)」と呼ばれる節が存在します。
(root)
Ａ ──────── レベル０
／｜＼ ↑
／ ｜ ＼
Ｂ Ｃ Ｄ 木 レベル１
／｜＼ ｜＼ の
／ ｜ ＼ ｜ ＼ 高
Ｅ Ｆ Ｇ Ｈ Ｉ さ レベル２
／ ＼
／ ＼ ↓
Ｊ Ｋ ───── レベル３
図 1 : 一般的な木構造の一例
木を図示する場合、階層関係がはっきりわかるように、根を上にして、同じ階層にある節を並べて書きます。根からレベル 0、レベル 1 と階層を数えていき、最下層の節までの階層数を「木の高さ」といいます。木は、ある節から下の部分を切り出したものも、木としての性質を持っています。これを「部分木」といいます。
木は、ある節からほかの節に至る「経路」を考えることができます。たとえば、A から J には、A - B - G - J という経路がありますね。これは、ディレクトリやファイルを指定するときのパスと同じです。
ある節から根の方向にさかのぼるとき、途中で通っていく節を「先祖」といい、直接繋がっている節を「親」といます。これは、逆から見ると「子孫」と「子」という関係になります。子を持たない節をとくに「葉」と呼ぶことがあります。上図でいうと、G は J と K の親で、J は G の子になります。J は子を持っていないので葉となります。
子は、「左 < 右」の順番で節に格納するのが一般的です。これを「順序木」といいます。また、順番がない木を「無順序木」と呼びます。節が持っている子の数を「次数」といいます。上図の場合、A は 3 つの子 B, C, D を持っているので、A の次数は 3 となります。すべての節の次数を n に揃えた順序木を「 n 分木」と呼びます。
とくに、次数が 2 の二分木は、プログラムでよく使われるデータ構造です。
(root)
18
／ ＼
／ ＼
／ ＼
／ ＼
／ ＼
14 22
／ ＼ ／ ＼
／ ＼ ／ ＼
12 16 20 24
／ ＼ ／ ＼ ／ ＼ ／ ＼
11 13 15 17 19 21 23 25
図 2 : 二分木の一例
上図に二分木の例を示します。二分木では、節にひとつのデータを格納します。そして、その節の左側の子には小さいデータを、右側の子には大きいデータが配置されるように木を構成します。
この二分木をデータの探索に使うアルゴリズムが「二分探索木」です。二分探索木はデータの探索・挿入を高速に行うことができます。たとえば、上図の木から 19 を探してみましょう。まず root の 18 と比較します。18 < 19 ですから、右側の子をたどり 22 と比較します。今度は 19 < 22 なので左側の子をたどります。次は 20 と比較し 19 < 20 なので左側の子をたどり、ここで 19 を見つけることができます。
二分探索木の探索は「二分探索 (binary search)」と同じ原理です。左右どちらかの子をたどるたびに、探索するデータ数は半分になります。上図の場合でも、探索するデータ数が 15, 7, 3, 1 となり、最後に見つけることができました。
データ数を N とすると、単純な線形探索では平均で N / 2 回の比較が必要になりますが、二分探索木を使うと log 2 N 程度の回数で収まります。たとえば、データが 100個ある場合、線形探索では 50 回データを比較しなければいけないのに、二分探索木では 7 回程度の比較で済むわけです。ただし、これは左右の部分木のバランスがとれている理想的な状態での話です。バランスが崩れると二分探索木の性能は劣化し、最悪の場合は線形探索と同じになってしまいます。
そこで、左右のバランスを一定の範囲に収める「平衡木」が考案されています。有名なところでは AVL 木、2-3 木、B 木、B* 木などがあります。また、Ｃ++の標準ライブラリである STL (Standard Template Library) では、「2 色木（赤黒木）」というアルゴリズムが使われているそうです。今回は OCaml の勉強ということで、単純な二分探索木をプログラムすることにします。なお、本稿では二分探索木のことを単に「二分木」と書くことにします。
それでは、OCaml で二分木を作ってみましょう。まずはモジュールを使わずにプログラムします。最初に type で二分木を定義します。
リスト 1 : 二分木の定義 type 'a tree = Nil | Node of 'a * 'a tree * 'a tree
二分木のデータ型は 'a tree とし、節は組で表します。もちろん、レコードを使ってもかまいません。Nil が空の木を表し、Node が節を表します。組の第 1 要素が二分木に格納するデータ、第 2 要素が左部分木、第 3 要素が右部分木を表します。簡単な例を示します。
12
／ ＼ ==> Node(12, Node(11, Nil, Nil), Node(13, Nil, Nil))
11 13
これを図で表すと次のようになります。
┌─┬─┬─┐
│12│・│・│
└─┴┼┴┼┘
│ │
┌──────┘ └─┐
↓ ↓
┌─┬─┬─┐ ┌─┬─┬─┐
│11│／│／│ │13│／│／│
└─┴─┴─┘ └─┴─┴─┘
┌─┬─┬─┐
節：│Ｄ│Ｌ│Ｒ│
└─┴─┴─┘
Ｄ：data, Ｌ：left, Ｒ：right, ／：Nil
図 3 : 二分木の構造
それでは、データを探索する関数から作ってみましょう。この処理はデータを比較して左右の部分木をたどっていくだけです。
リスト 2 : データの探索 let rec search x = function Nil -> false | Node (y, _, _) when x = y -> true | Node (y, left, _) when x < y -> search x left | Node (_, _, right) -> search x right
関数 search の第 1 引数 x が探索するデータ、第 2 引数が二分木です。二分木が Nil であれば、これ以上探索することはできません。データは見つからなかったので false を返します。そうでなければ、引数 x と節のデータを比較します。節のデータはパターンマッチングで取り出すことができます。y がデータ、left が左部分木、right が右部分木です。x = y ならばデータが見つかったので true を返します。x < y ならば search を再帰呼び出しして左部分木をたどります。そうでなければ x > y なので右部分木をたどります。
次は、データを挿入する関数を作りましょう。探索と同様に、データを比較して木をたどっていき、木がなくなった所に新しいデータを挿入します。
リスト 3 : データの挿入 let rec insert x = function Nil -> Node (x, Nil, Nil) | (Node (y, _, _)) as node when x = y -> node | Node (y, left, right) when x < y -> Node (y, (insert x left), right) | Node (y, left, right) -> Node (y, left, (insert x right))
関数 insert の第 1 引数 x が挿入するデータ、第 2 引数が二分木です。二分木が Nil であれば、新しい節を作って返します。この返り値を節の部分木にセットします。2 番目の節で、x と y が等しい場合は二分木に同じデータがあるので節をそのまま返します。
x < y であれば、insert を再帰呼び出しして左部分木をたどります。そして、左部分木を insert x left の返り値に置き換えた節を作って返します。もしも、left が Nil であれば、ここに新しい節が挿入され、新しい部分木が返されます。x > y であれば右部分木をたどり、データを挿入した新しい右部分木を返します。
次はデータを削除する処理を作りましょう。これは今までと違って少々面倒です。削除するデータが「葉」の場合は、それを削除するだけなので簡単ですが、木の途中のデータを削除する場合は、二分木の構成を崩さないように注意しないといけません。最初に、葉を削除する場合を説明します。下図を見てください。
14 14
／ ＼ ／ ＼
／ ＼ ／ ＼
12 16 => 12 16
／ ＼ ／ ＼ ／ ＼ ／ ＼
11 13 15 17 11 13 Nil 17
↑
15 を削除する 削除
図 4 : データの削除 (葉の場合)
15 を削除する場合を考えてみましょう。15 は「葉」にあたるので、それを削除するだけで大丈夫です。
次に、子が一つある場合を考えてみましょう。
14 14
／ ＼ ／ ＼
／ ＼ ／ ＼
12 16 => 12 15
／ ＼ ／ ／ ＼
11 13 15 11 13
16 を削除する
図 5 : データの削除 (子が一つの場合)
16 を削除する場合、その子である 15 と置き換えれば二分木の構成は保たれます。これも簡単ですね。問題は、子が二つある節を削除する場合です。
14 15 <- 最小値と置き換え
／ ＼ ／ ＼
／ ＼ ／ ＼
12 16 => 12 16
／ ＼ ／ ＼ ／ ＼ ／ ＼
11 13 15 17 11 13 Nil 17
↑
14 を削除する 削除
図 6 : データの削除 (子が二つの場合)
この場合、削除するデータの右部分木の中から最小値のデータ [*1] を探し、それと削除するデータと置き換えれば「右部分木 < 節 < 左部分木」の構成を崩さなくてすみます。たとえば、上図で 14 を削除することを考えてみましょう。右部分木の中で 15 が最小値なので、それと 14 を置き換えます。そして、15 を格納していた節は削除します。節が最小値を格納している場合、その節の左側の子は存在しないので、その節を削除することは簡単です。
まずは木の中から最小値を探す関数と、最小値の節を削除する関数を作成しましょう。次のリストを見てください。
リスト 4 : 最小値の探索と削除 (* 最小値を求める *) let rec search_min = function Nil -> raise (Failure "search_min") | Node (x, Nil, _) -> x | Node (_, left, _) -> search_min left (* 最小値を削除する *) let rec delete_min = function Nil -> raise (Failure "delete_min") | Node (x, Nil, right) -> right | Node (x, left, right) -> Node (x, (delete_min left), right)
二分木の場合、最小値は簡単に求めることができます。左側の子を順番にたどっていき、左側の子がない節に行き着いたとき、その節のデータが最小値になります。関数 search_min は最小値を求めてそれを返します。
最初の節はエラーチェックです。引数が空の木であれば例外を送出します。次に、左側の子の値をチェックします。もし、Nil であれば左側の子がないので、その節のデータが最小値です。格納されているデータ x を返します。そうでなければ、search_min を再帰呼び出しして左側の子をたどります。
関数 delete_min は最小値を格納している節を削除します。左側の子が Nil の節を探すのは search_min と同じです。見つけたら、もう一つの子 right を返します。そうでなければ、delete_min を再帰呼び出しして、その左部分木の中から最小値を探し出して削除します。そして、その返り値を格納した新しい節を返します。これで、最小値を持つ節が削除されます。葉の場合であれば right は Nil なので、単純に削除されることになります。
それでは、データを削除する関数 delete を作ります。まず削除するデータを探索して、見つけたら子の有無に合わせた削除処理を行います。
リスト 5 : データの削除
let rec delete x = function
Nil -> raise Not_found
| Node(y, left, right) ->
if x = y then
if left = Nil then right
else if right = Nil then left
else
let min_data = search_min right in
Node (min_data, left, (delete_min right))
else if x < y then
Node (y, (delete x left), right)
else
Node (y, left, (delete x right))
まず、節が Nil ならばデータが見つからなかったので例外 Not_found を送出します。次に、削除するデータ x と節のデータ y を比較します。等しい場合はその節を削除します。left が Nil の場合は right を返し、right が Nil の場合は left を返します。
子が 2 つある場合は、右部分木の最小値を関数 search_min で求め、その値を格納した新しい節を作ります。このとき、関数 delete_min で最小値を格納していた節を削除します。これで、削除するデータを最小値で置き換えることができます。
x と節のデータ y が等しくない場合は、左右の部分木をたどって削除するデータを探索します。この処理は今までと同じで、delete の返り値を格納した新しい節を返します。
最後に、二分木の全データにアクセスする関数を作りましょう。二分木はデータの大小関係を使って構成されているので、ある順番で節をすべて出力すると、それはソートした結果と同じになります。「木」のすべての節を規則的な順序で回ることを「巡回 (traverse)」といいいます。このなかで、次の 3 つの方法が重要です。
名前の由来は、節のデータを出力するタイミングからきています。節に最初に到達したときに出力する方法が「行きがけ」、子を出力してその節に戻ってきたときに出力する方法が「帰りがけ」、子を出力する途中でその節に戻ってきたときに出力する方法が「通りがけ」です。
二分木は「左の子 < 節のデータ < 右の子」という関係が成り立つので、通りがけ順に出力すれば、ソートされた出力結果を得ることができます。この処理は、再帰定義を使えば簡単に実現できます。
リスト 6 : 二分木の巡回 let rec iter f = function Nil -> () | Node (x, left, right) -> iter f left; f x; iter f right
関数 iter は二分木を通りがけ順に巡回し、格納されているデータに関数 f を適用します。まず、二分木が Nil ならば何もしないで unit を返します。これが再帰呼び出しの停止条件となります。あとは通りがけ順の定義そのままにプログラムをするだけです。
左部分木をたどるため、left に対して iter を再帰呼び出しします。次に、節のデータ x に関数 f を適用します。最後に右部分木をたどるため、right に対して iter を再帰呼び出しします。
それでは簡単な実行例を示しましょう。
# #use "tree0.ml";;
type 'a tree = Nil | Node of 'a * 'a tree * 'a tree
val search : 'a -> 'a tree -> bool = <fun>
val insert : 'a -> 'a tree -> 'a tree = <fun>
val search_min : 'a tree -> 'a = <fun>
val delete_min : 'a tree -> 'a tree = <fun>
val delete : 'a -> 'a tree -> 'a tree = <fun>
val iter : ('a -> 'b) -> 'a tree -> unit = <fun>
# let a0 = insert 5 Nil;;
val a0 : int tree = Node (5, Nil, Nil)
# let a1 = insert 3 a0;;
val a1 : int tree = Node (5, Node (3, Nil, Nil), Nil)
# let a2 = insert 7 a1;;
val a2 : int tree = Node (5, Node (3, Nil, Nil), Node (7, Nil, Nil))
# search 3 a2;;
- : bool = true
# search 0 a2;;
- : bool = false
# iter (fun x -> print_int x; print_string " ") a2;;
3 5 7 - : unit = ()
# let a3 = delete 5 a2;;
val a3 : int tree = Node (7, Node (3, Nil, Nil), Nil)
正常に動作していますね。
(*
* tree0.ml : 二分木
*
* Copyright (C) 2008-2020 Makoto Hiroi
*
*)
(* 二分木の定義 *)
type 'a tree = Nil | Node of 'a * 'a tree * 'a tree
(* データの探索 *)
let rec search x = function
Nil -> false
| Node (y, _, _) when x = y -> true
| Node (y, left, _) when x < y -> search x left
| Node (_, _, right) -> search x right
(* データの挿入*)
let rec insert x = function
Nil -> Node (x, Nil, Nil)
| (Node (y, _, _)) as node when x = y -> node
| Node (y, left, right) when x < y -> Node (y, (insert x left), right)
| Node (y, left, right) -> Node (y, left, (insert x right))
(* 最小値を求める *)
let rec search_min = function
Nil -> raise (Failure "search_min")
| Node (x, Nil, _) -> x
| Node (_, left, _) -> search_min left
(* 最小値を削除する *)
let rec delete_min = function
Nil -> raise (Failure "delete_min")
| Node (x, Nil, right) -> right
| Node (x, left, right) -> Node (x, (delete_min left), right)
(* データの削除 *)
let rec delete x = function
Nil -> raise Not_found
| Node(y, left, right) ->
if x = y then
if left = Nil then right
else if right = Nil then left
else
let min_data = search_min right in
Node (min_data, left, (delete_min right))
else if x < y then
Node (y, (delete x left), right)
else
Node (y, left, (delete x right))
(* 二分木の巡回 *)
let rec iter f = function
Nil -> ()
| Node (x, left, right) -> iter f left; f x; iter f right
二分木はデータの大小関係を比較することで動作します。格納するデータによっては、OCaml の比較演算子ではなく、ほかの方法でデータを比較した方が都合が良い場合もあります。このようなとき、モジュールにデータの型と比較関数を渡すことができると便利です。OCaml の場合、ファンクタを使うとモジュールを引数として受け取り、それを使って新しいモジュールを作成することができます。
ファンクタは次のように定義します。
module 名前 (moduleA: sigA) = struct ... end
ファンクタは引数に与えられたモジュール moduleA を使って新しいモジュールを生成します。moduleA は関数定義の引数 (仮引数) と同じと考えてください。ファンクタは moduleA.func や moduleA.value のように、moduleA に定義されている関数や変数を使ってモジュールを定義します。そして、moduleA の型をシグネチャ sigA で指定します。逆にいえば、ファンクタで必要になる関数や変数の仕様を sigA に記述するのです。ファンクタに与えるモジュールは、このシグネチャの仕様を満たす必要があります。
ちなみに、ファンクタの定義は次の式と同じです。
module 名前 = functor (引数: 型) -> struct ... end
functor は匿名関数の fun と似ているようにみえますが大きな違いがあります。functor はモジュールを受け付けるところでないと使用できません。モジュールは一般のデータ型と同じように扱うことはできないのです。ご注意くださいませ。
二分木の場合、格納するデータの型と比較関数が必要になります。これをモジュールに定義してファンクタに渡すことにします。シグネチャの定義は次のようになります。
リスト 7 : シグネチャの定義 module type ItemType = sig type t val compare : t -> t -> int end
シグネチャの名前は ItemType としました。データの比較関数を定義するシグネチャなので、OCaml のモジュール Map では OrderedType としています。最初に type で t というデータ型を宣言します。このデータ型を使ってシグネチャを記述します。具体的なデータ型の指定はモジュールで行います。
データを比較する関数が compare です。関数型は t -> t -> int とします。compare x y は x < y だと負の整数を返し、x = y だと 0 を返し、x > y だと正の整数を返すものとします。なお、OCaml には同様の関数 compare が定義されています。
# compare;; val compare : 'a -> 'a -> int = <fun>
このシグネチャを使ってファンクタを定義します。プログラムは次のようになります。
(*
* tree1.ml : 二分木 (ファンクタ版)
*
* Copyright (C) 2008-2020 Makoto Hiroi
*
*)
module type ItemType = sig
type t
val compare : t -> t -> int
end
module MakeTree(Item: ItemType) = struct
(* 節の定義 *)
type tree = Nil | Node of Item.t * tree * tree
(* 空の木 *)
let create = Nil
(* データの探索 *)
let rec search x = function
Nil -> None
| Node (y, _, _) when Item.compare x y = 0 -> Some y
| Node (y, left, _) when Item.compare x y < 0 -> search x left
| Node (_, _, right) -> search x right
(* データの挿入 *)
let rec insert x = function
Nil -> Node (x, Nil, Nil)
| (Node (y, _, _)) as node when Item.compare x y = 0 -> node
| Node (y, left, right) when Item.compare x y < 0 -> Node (y, (insert x left), right)
| Node (y, left, right) -> Node (y, left, (insert x right))
(* 最小値を求める *)
let rec search_min = function
Nil -> raise (Failure "search_min")
| Node (x, Nil, _) -> x
| Node (_, left, _) -> search_min left
(* 最小値を削除する *)
let rec delete_min = function
Nil -> raise (Failure "delete_min")
| Node (x, Nil, right) -> right
| Node (x, left, right) -> Node (x, (delete_min left), right)
(* 削除 *)
let rec delete x = function
Nil -> raise Not_found
| Node(y, left, right) ->
if Item.compare x y = 0 then
if left = Nil then right
else if right = Nil then left
else
let min_data = search_min right in
Node (min_data, left, (delete_min right))
else if Item.compare x y < 0 then
Node (y, (delete x left), right)
else
Node (y, left, (delete x right))
(* 巡回 *)
let rec iter f = function
Nil -> ()
| Node (x, left, right) -> iter f left; f x; iter f right
end
ファンクタの名前は MakeTree としました。引数のモジュールを Item とし、シグネチャを ItemType とします。ファンクタで指定するモジュール名は関数定義の仮引数と同じなので、あらかじめ Item というストラクチャを定義しておく必要はありません。モジュールで定義されているデータ型は Item.t で、比較関数は Item.compare で参照することができます。
二分木の型は、格納するデータ型が Item.t で渡されるので型変数を使わずに tree とします。そして、型式は Nil | Node of Item.t * tree * tree となります。これで Item.t を格納する二分木となります。それから、関数 search は見つけたデータを option 型に入れて返すことにします。あとは、データを比較する処理で、Item.compare を呼び出すように修正するだけです。
ファンクタを定義すると、次に示すシグネチャが出力されます。
# #use "tree1.ml";;
module type ItemType = sig type t val compare : t -> t -> int end
module MakeTree :
functor (Item : ItemType) ->
sig
type tree = Nil | Node of Item.t * tree * tree
val create : tree
val search : Item.t -> tree -> Item.t option
val insert : Item.t -> tree -> tree
val search_min : tree -> Item.t
val delete_min : tree -> tree
val delete : Item.t -> tree -> tree
val iter : (Item.t -> 'a) -> tree -> unit
end
ファンクタの型は functor (引数: 型) -> sig ... end で表されます。ファンクタの引数 Item を参照して、シグネチャが定義されていることがわかります。
それでは整数を格納する二分木 IntTree をファンクタ MakeTree で生成してみましょう。
# module IntTree = MakeTree(struct type t = int let compare x y = x - y end);;
module IntTree :
sig
type tree = Nil | Node of int * tree * tree
val create : tree
val search : int -> tree -> int option
val insert : int -> tree -> tree
val search_min : tree -> int
val delete_min : tree -> tree
val delete : int -> tree -> tree
val iter : (int -> 'a) -> tree -> unit
end
ファンクタ MakeTree には名前のないモジュールを渡しています。この中で type t を int とし、比較関数 compare を定義しています。IntTree のシグネチャを見ると、格納するデータ型が int になっていることがわかります。このように、データ型と比較関数をファンクタに渡せば、そのデータ型に対応する二分木を作ることができます。
それでは実際に試してみましょう。
# open IntTree;; # let a0 = create;; val a0 : IntTree.tree = Nil # let a1 = insert 5 a0;; val a1 : IntTree.tree = Node (5, Nil, Nil) # let a2 = insert 3 a1;; val a2 : IntTree.tree = Node (5, Node (3. Nil, Nil), Nil) # let a3 = insert 7 a2;; val a3 : IntTree.tree = Node (5, Node (3. Nil, Nil), Node (7, Nil, Nil)) # search 3 a3;; - : int option = Some 3 # search 8 a3;; - : int option = None # iter (fun x -> print_int x; print_string " ") a3;; 3 5 7 - : unit = ()
次の関数を定義してください。
リスト : カッコ列の生成
(* カッコ列の印字 *)
let print_kakko xs =
print_endline (List.fold_left (^) "" xs)
(* カッコ列の生成 *)
let kakko f m =
let rec kakko_sub x y a =
if x = m && y = m then f (List.rev a)
else
if x < m then kakko_sub (x + 1) y ("("::a) else ();
if y < x then kakko_sub x (y + 1) (")"::a) else ()
in kakko_sub 0 0 []
val print_kakko : string list -> unit = <fun> val kakko : (string list -> unit) -> int -> unit = <fun>
カッコ列の生成は簡単です。局所関数 kakko_sub の引数 x が左カッコの個数、引数 y が右カッコの個数を表します。引数 a は累積変数で、文字列 "(", ")" を格納したリストです。
バランスの取れたカッコ列の場合、x, y, m には y <= x <= m の関係が成り立ちます。x = m かつ y = m の場合、カッコ列がひとつ完成しました。リスト a を反転して、引数の関数 f を呼び出します。そうでなければ、kakko_sub を再帰呼び出しします。x < m であれば左カッコを追加し、y < x であれば右カッコを追加します。これでカッコ列を生成することができます。
# kakko print_kakko 2;; (()) ()() - : unit = () # kakko print_kakko 3;; ((())) (()()) (())() ()(()) ()()() - : unit = () |
# kakko print_kakko 4;; (((()))) ((()())) ((())()) ((()))() (()(())) (()()()) (()())() (())(()) (())()() ()((())) ()(()()) ()(())() ()()(()) ()()()() - : unit = () |
カタラン数 - Wikipedia によると、カッコ列の総数は「カタラン数 (Catalan number)」になるとのことです。カタラン数は次に示す公式で求めることができます。
これをそのままプログラムしてもいいのですが、それではちょっと面白くないので別な方法でプログラムを作ってみましょう。カタラン数は次に示す経路図において、A から B までの最短距離の道順を求めるとき、対角線を超えないものの総数に一致します。
Ｂ Ｂ
┌─┬─┬─┬─┐ ┌─┬─┬─０─14
│ │ │ │ │ │ │ │ │ │
├─┼─┼─┼─┤ ├─┼─０─５─14
│ │ │ │ │ │ │ │ │ │
├─┼─┼─┼─┤ ├─０─２─５─９
│ │ │ │ │ │ │ │ │ │
├─┼─┼─┼─┤ ０─１─２─３─４
│ │ │ │ │ │ │ │ │ │
└─┴─┴─┴─┘ １─１─１─１─１
Ａ Ａ
図 : 道順の総数の求め方
A からある地点にいたる最短距離の道順の総数は、左隣と真下の地点の値を足したものになります。一番下の地点は 1 で、対角線を越えた地点は 0 になります。あとは下から順番に足し算していけば、A から B までの道順の総数を求めることができます。上図の場合はカラタン数 Ｃ4 に相当し、その値は 14 となります。
これをそのままプログラムすると、次のようになります。
リスト : カッコ列の総数
(* リストの生成 *)
let make_list x n =
let rec iter n a =
if n = 0 then a
else iter (n - 1) (x::a)
in
iter n []
let kakko_num m =
let rec iter = function
[] -> Int 0
| [x] -> x
| _::xs -> iter (List.tl (List.rev (List.fold_left (fun b x -> (x +/ (List.hd b))::b) [(Int 0)] xs)))
in
iter (make_list (Int 1) (m + 1))
val make_list : 'a -> int -> 'a list = <fun> val kakko_num : int -> Num.num = <fun>
実際の処理は局所関数 iter で行います。最初に make_list で一番下の地点の道順の総数 (1) を格納したリスト生成します。これが iter に渡す初期値になります。引数 m のカラタン数を求める場合、リストの大きさは m + 1 になります。あとは、リストの要素がひとつになるまで iter を再帰呼び出しします。
一段上の地点の値を求める場合、畳み込み fold_left を使うと簡単です。初期値はリスト [(Int 0)] とします。これが対角線を越えた地点の値を表します。引数の先頭要素は不要なので、パターン _::xs で分解して fold_left に渡します。匿名関数の引数 x が真下の地点の値、引数 b の先頭要素が左隣の地点の値になります。
あとは x と (List.hd b) を足し算して、それを演算子 :: でリスト b の先頭に追加すればいいわけです。この場合、fold_left が返すリストは逆順になるので、List.rev で反転してから List.tl で先頭要素 (対角線を越えた地点の値) を削除します。これでカッコ列の総数 (カラタン数) を求めることができます。
簡単な実行例を示します。実行する前にモジュール Num のロードとオープンを行ってください。
# kakko_num 1;; - : Num.num = Int 1 # kakko_num 2;; - : Num.num = Int 2 # kakko_num 3;; - : Num.num = Int 5 # kakko_num 4;; - : Num.num = Int 14 # kakko_num 5;; - : Num.num = Int 42 # kakko_num 10;; - : Num.num = Int 16796 # string_of_num (kakko_num 50);; - : string = "1978261657756160653623774456" # string_of_num (kakko_num 100);; - : string = "896519947090131496687170070074100632420837521538745909320"