OCaml

練習問題 6.3 再帰ヴァリアント nat

練習問題 6.3

まず、自然数の定義。

type nat = Zero | OMT of nat;;  (* OMT -- OneMoreThan *)

let zero = Zero
and one = OMT Zero
and two = OMT (OMT Zero);;

let three = OMT two;;
let four = OMT three;;
let five = OMT four;;
let six = OMT five;;

次は、足し算。

(*
足し算の定義:
・ゼロに自然数 n を足したものは n である。
・m より 1 大きい数に n を足したものは、m と n を足したものより 1 大きい数である。
 *)
let rec add m n =
  match m with
    Zero -> n
  | OMT m' -> OMT (add m' n);;

(* 整数リスト *)
type intlist = INil | ICons of int * intlist;;

掛け算から考える。

(* 掛け算 *)  
let rec mul m n =
  match n with
    Zero -> zero
  | OMT n' -> add (mul m n') m;;
# mul two three;;
- : nat = OMT (OMT (OMT (OMT (OMT (OMT Zero)))))
# mul four six;;
- : nat =                                                                                                                    OMT                                                                                                                           (OMT                                                                                                                        
   (OMT
     (OMT
       (OMT
         (OMT
           (OMT
             (OMT
               (OMT
                 (OMT
                   (OMT
                     (OMT
                       (OMT
                         (OMT
                           (OMT
                             (OMT
                               (OMT
                                 (OMT (OMT (OMT (OMT (OMT (OMT (OMT Zero)))))))))))))))))))))))

引き算は考えてもわからなかったので、ネットで解答を調べた。

(* 引き算 *)
(*
ここを見た:
http://gifnksm.hatenablog.jp/category/OCaml?page=1205602283
 *)
let rec monus m n =
  match (m, n) with
    (Zero, _) -> zero
  | (_, Zero) -> m
  | (OMT m', OMT n') -> monus m' n';;
# monus five two;;
- : nat = OMT (OMT (OMT Zero))                                                                                              # monus three five;;
- : nat = Zero