ヴァリアントの応用：再帰的ヴァリアント

type宣言において，コンストラクタの引数に今宣言しようとしているヴァリアントを使うことができる。つまり再帰的な宣言。

以下は0を含む自然数（というか正の整数）を表す型 nat を宣言する例。

• ゼロは自然数である
• 自然数より1大きい数は自然数である

これをヴァリアントとして宣言すると：

# type nat = Zero | OneMoreThan of nat;;
type nat = Zero | OneMoreThan of nat

そのままだね。

これを使って足し算を定義するとこうなる：

# let rec add m n =
match m with
Zero -> n
| OneMoreThan m' -> OneMoreThan (add m' n)
;;
val add : nat -> nat -> nat = <fun>

• ゼロにnを足した数はnである
• m’より1大きい数にnを足した数はm’とnを足した数より1大きい数である

これもそのまんま。

実際に計算してみよう。

# let zero = Zero;;
val zero : nat = Zero
# let one = OneMoreThan zero;;
val one : nat = OneMoreThan Zero
# let two = OneMoreThan one;;
val two : nat = OneMoreThan (OneMoreThan Zero)
# add zero one;;
- : nat = OneMoreThan Zero
# add one one;;
- : nat = OneMoreThan (OneMoreThan Zero)
# add one one = two;;
- : bool = true