# 再帰的データ型

さらに引き続きOCaml勉強中。この本を使って勉強しています。

プログラミング in OCaml ~関数型プログラミングの基礎からGUI構築まで~

```# 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>
# let zero = Zero;;
val zero : nat = Zero
# let one = OneMoreThan Zero;;
val one : nat = OneMoreThan Zero
# let two = add one one;;
val two : nat = OneMoreThan (OneMoreThan Zero)
# let three = add two one;;
val three : nat = OneMoreThan (OneMoreThan (OneMoreThan Zero))
# let four = add three one;;
val four : nat = OneMoreThan (OneMoreThan (OneMoreThan (OneMoreThan Zero)))
# let five = add four one;;
val five : nat =
OneMoreThan (OneMoreThan (OneMoreThan (OneMoreThan (OneMoreThan Zero))))
```

```# let rec mul m n =
match m with
Zero -> Zero
| OneMoreThan Zero -> n
| OneMoreThan m' -> add n (mul m' n);;
val mul : nat -> nat -> nat = <fun>
# mul five four;;
- : nat =
OneMoreThan
(OneMoreThan
(OneMoreThan
(OneMoreThan
(OneMoreThan
(OneMoreThan
(OneMoreThan
(OneMoreThan
(OneMoreThan
(OneMoreThan
(OneMoreThan
(OneMoreThan
(OneMoreThan
(OneMoreThan
(OneMoreThan
(OneMoreThan
(OneMoreThan
(OneMoreThan
(OneMoreThan (OneMoreThan Zero)))))))))))))))))))
# mul five zero;;
- : nat = Zero
# mul three two;;
- : nat =
OneMoreThan
(OneMoreThan (OneMoreThan (OneMoreThan (OneMoreThan (OneMoreThan Zero)))))
```

とんでもないことになったｗ

```# let int_of_nat n =
let rec get_num nt it =
match nt with
Zero -> it
| OneMoreThan nt' -> get_num nt' (it+1)
in
get_num n 0;;
val int_of_nat : nat -> int = <fun>
# int_of_nat (mul four five);;
- : int = 20
- : int = 75
```

ちゃんと動いているみたい。λ式で書かれるより、やっぱりプログラムになった方が分かりやすい。

```# let rec monus m n =
match (m, n) with
(Zero, _) -> Zero
| (_, Zero) -> m
| (OneMoreThan m', OneMoreThan n') -> monus m' n';;
val monus : nat -> nat -> nat = <fun>
# int_of_nat (monus four three);;
- : int = 1
# int_of_nat (monus five one);;
- : int = 4
# int_of_nat (monus two five);;
- : int = 0
# int_of_nat (monus two two);;
- : int = 0
# int_of_nat (monus one one);;
- : int = 0
```

このとき、解無しを返すようにしてみます。そのために、まずはオプション型を定義して、引き算の関数を書き換えます。

```# type 'a option = None | Some of 'a;;
type 'a option = None | Some of 'a
# let rec minus m n =
match (m, n) with
(_, Zero) -> Some (m)
| (Zero, _) -> None
| (OneMoreThan m', OneMoreThan n') -> minus m' n';;
val minus : nat -> nat -> nat option = <fun>
# let string_of_nat_option = function
None -> "None"
| Some n -> string_of_int (int_of_nat n);;
val string_of_nat_option : nat option -> string = <fun>
# string_of_nat_option (minus five four);;
- : string = "1"
# string_of_nat_option (minus five five);;
- : string = "0"
# string_of_nat_option (minus four five);;
- : string = "None"
# string_of_nat_option (minus zero five);;
- : string = "None"
# string_of_nat_option (minus zero zero);;
- : string = "0"
```

できたー！