再帰的データ型

さらに引き続き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)))))

とんでもないことになったｗ
慌ててnatをintに変換する関数を作った。

# 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_of_nat (mul five (add five (add five five)));;
- : 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

自然数の範囲なので、引く数が引かれる数よりも大きい場合は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"

できたー！