チャーチ数

チャーチ数を使うとλを使って自然数を表すことができます。詳しくは、ラムダ計算ＡＢＣを参照してください。
で。以下の関数curried_lambdaを使うと、

def curried_lambda(n = -1, xs = [], &f)
  n = f.arity if n < 0
  if n == 0
    f[*xs]
  else
    lambda {|x| curried_lambda(n - 1, xs + [x], &f) }
  end
end

0〜3はこのように表現できます。

zero  = curried_lambda {|f, x| x          } # λfx.x        
one   = curried_lambda {|f, x| f[x]       } # λfx.fx       
two   = curried_lambda {|f, x| f[f[x]]    } # λfx.f(fx)    
three = curried_lambda {|f, x| f[f[f[x]]] } # λfx.f(f(fx)) 

つまりfを畳み込んだ回数が数です。一般化すると以下のようになります。

def n(m)
  curried_lambda do |f, x|
    (1 .. m).inject(x) {|a, i| f[a] }
  end
end

このチャーチ数に演算を定義してます。

class Proc
  def to_i
    self[lambda {|n| n + 1 }][0]
  end
  
  def +(other) # λabfx.af(bfx) 
    curried_lambda {|f, x| self[f][other[f][x]] }
  end

  def *(other) # λabf.a(bf)
    curried_lambda {|f| self[other[f]] }
  end

  def **(other) # λab.ba
    other[self]
  end
end

p n(100).to_i         # => 100
p (n(2) +  n(3)).to_i # => 5
p (n(2) *  n(3)).to_i # => 6
p (n(2) ** n(3)).to_i # => 8

んー、すばらしいです。これ何てRuby？
参照: Ruby チャーチ数 - 冬通りに消え行く制服ガールは✖夢物語にリアルを求めない。 - subtech