そのまま実装してみます。チャーチ数は自然数 n の場合、引数 f をとり、引数 x に対し f を n 回適用する関数を返す高階関数らしいです。

\f x -> x       -- 0
\f x -> f x     -- 1
\f x -> f (f x) -- 2

数としてもどしたいときは

-- cn はチャーチ数
cn (\x -> x + 1) 0

とかやるとたぶん数になります。

class ChurchNumber < Lambda

	# ¥m n f x -> m f (n f x)
	def +(m)
		n = self
		m = m.to_church_number
		ChurchNumber.new {|f|
			lambda {|x|
				m[f][n[f][x]]
			}
		}
	end

	# ¥n f x -> f (n f x)
	def succ
		n = self
		ChurchNumber.new {|f|
			lambda {|x|
				f[n[f][x]]
			}
		}
	end

	def to_i
		self[lambda {|x| x + 1 }][0]
	end

	def coerce(number)
		[number, self.to_i]
	end

	def inspect
		# "#<%s:0x%08x:%d>" % [self.class, self.object_id, self.to_i]
		"#<%s:%d>" % [self.class, self.to_i]
	end

	def to_church_number
		self
	end
end

class Integer
	def to_church_number
		n = self
		ChurchNumber.new {|f|
			lambda {|x|
				(1..n).inject(x) {|r,i| f[r] }
			}
		}
	end
end

p 1.to_church_number      #=> #<ChurchNumber:1>
p 1.to_church_number.succ #=> #<ChurchNumber:2>
p 2 + 1.to_church_number  #=> 3
p 2.to_church_number + 1  #=> #<ChurchNumber:3>

(0..10).each do |i|
	p [i.to_church_number, i.to_church_number.to_i]
end