練習問題 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