Yコンビネータ
id:sshiさんにブクマで「これってYコンビネータ？」とコメントを頂いたので、考えてみました。
とりあえず、
- カリー化されてない
- 美しくない
という理由で、Yコンビネータではないみたいです。
で、Yコンビネータに持っていけるかやってみました。
ほとんど「再帰的な関数」を手続きオブジェクトにする - バリケンのRuby日記 - Rubyistをそのままなぞりました。そっちのエントリを見たほうがいいと思います。
前回、出来たコードは
fact10 =
lambda{|f|
lambda{|n|
f.call(f, n)
}
}.call(
lambda {|slf, m| # factorial
if m == 0
1
else
m * slf.call(slf, m-1)
end
}
).call(10)
p fact10でした。とりあえずカリー化します。変数名は変えました。
y =
lambda{|f|
lambda{|n|
f[f][n]
}
}
h =
lambda{|u|
lambda{|m|
if m == 0
1
else
m * u[u][m-1] # dirty!
end
}
}
fact = y[h]
p fact[10]1のカリー化はクリアしましたが、2が顕在化しました。hの中のu[u][m-1]が美しくない。できればu[m-1]と書けたほうが人に優しい。
そこで、hを等価に変えていきます。利用するのはfとlambda{|x| f[x]}が等価だということ。
hに等価なgを作ります。カリー化されてるので、2変数関数でも気にしなくていいのが気分いい。
y =
lambda{|f|
lambda{|n|
f[f][n]
}
}
# hと同値なg
g =
lambda{|u|
lambda{|v|
h = lambda{|slf|
lambda{|m|
if m == 0
1
else
m * slf[slf][m-1] # dirty!
end
}
}
h[u][v]
}
}
fact = y[g]
p fact[10]まだいやなところは残ってます。slfには、h[u][v]の形でuが実引数で渡されてます。uはそれ以外に使われてないので、h[u][v]段階でuの代わりにu[u]としてやれば、slf[slf]は、slf一つで済みます。
y =
lambda{|f|
lambda{|n|
f[f][n]
}
}
# u <-> slfの呼び出し関係を修正
g =
lambda{|u|
lambda{|v|
h = lambda{|slf|
lambda{|m|
if m == 0
1
else
m * slf[m-1]
end
}
}
h[u[u]][v]
}
}
fact = y[g]
p fact[10]hの定義部分のlambdaは独立させられるので、外へ。
y =
lambda{|f|
lambda{|n|
f[f][n]
}
}
# くくりだした
h = lambda{|slf|
lambda{|m|
if m == 0
1
else
m * slf[m-1]
end
}
}
g =
lambda{|u|
lambda{|v|
h[u[u]][v]
}
}
fact = y[g]
p fact[10]最後のfact = y[g]で、yにはhを与えれば良いようにgを入れ込む。
長くなって見にくいので、yのなかで変数を使いました。
# yが直接hを受け取れるように修正
y =
lambda{|q|
p = lambda{|f|
lambda{|n|
f[f][n]
}
}
g = lambda{|u|
lambda{|v|
q[u[u]][v]
}
}
p[g]
}
h =
lambda{|slf|
lambda{|m|
if m == 0
1
else
m * slf[m-1]
end
}
}
fact = y[h]
p fact[10]これで、当初の美しくない部分がすっきりしました。
うーん、「再帰的な関数」を手続きオブジェクトにする - バリケンのRuby日記 - RubyistのYコンビネータと形が違うなぁ。いいのかな？
sum_sub =
lambda{|s|
lambda{|n|
if n == 0
0
else
n + s[n-1]
end
}
}
sum = y[sum_sub]
p sum[10] # 55まあ、よしとしよう。
それと、ちょっと理解できたことがあるけど、また明日にでも。
