OCamlでチャーチ数【メモ】 #OCaml

背景

最近、五十嵐淳先生の「プログラミング言語の基礎概念」という本を読んで、興味が湧いたので自分の忘備録として残しておきます。

ここでチャーチ数は高階関数として表され、関数fと値xを受け取り、fにxをn回適用する関数として定義します。
まず、ゼロと後続数を定義します。

let zero f x = x
let succ n f x = f (n f x)

すると、自然数1を表すoneと自然数2を表すtwoはこうなります。

let one = succ zero
let two = succ (succ zero)

加算を定義してみます。

let add n1 n2 f x = n1 f (n2 f x)

チャーチ数をOCamlの整数に変換する関数を定義してみます。

let to_int n = n (fun k -> k+1) 0

楽しい。