年始なのであたらしいことでもやるかと思い、Haskellの入門を見ていると
- Yコンビネータ
なんていうものが目についた。他の概念もよく分かってない(Monadとか...)けど、これがとりあえず気になったので調べてみる
読んでいると
自己参照のできない無名のラムダ式で再帰を実現するテクニックとして、不動点コンビネータを利用する方法があります。
とのこと。
Haskellでのサンプルを見ると
Yコンビネータの定義
y x = x (y x)
sumのインライン実装
main = do
print $ flip y [1..100] $ \f (x:xs) -> case xs of
[] -> x
_ -> x + f xs
全く分からないのでYコンビネータとは？というところから考えていく
その他
これを参考にすると、Yコンビネータとは
不動点演算子の一つ
であると言えます
まず
"ある関数を入力として受け取り、その関数を使う新しい関数を作って出力する関数"
があったとき、その関数を
\begin{aligned} F\end{aligned}
とします
そして、ある関数fをFに入力したときに
\begin{aligned} f = F(f) \end{aligned}
が成り立つとき、"fはFの不動点である" といいます。
つまり、どういう事かというと、
「fはFの不動点である」という事が、
「fは再帰する関数である」という事と同じ！！
http://d.hatena.ne.jp/r-west/20090417/1239972722
この、Fにおけるf(不動点)を求める関数Yがあった時、その関数Yを、Yコンビネータ(不動点演算子)という。
どのような関数でも、Yコンビネータを通して、不動点を得られれば、再帰の計算ができるということだろうか
Yコンビネータを使った再帰に必要なのは
- Yコンビネータ
- 関数を引数にとって、その関数を関数を使った新しい関数を返す関数
これを踏まえてもう一度最初の定義を見る
y x = x (y x)
関数yが不動点を求めるYコンビネータ
main = do
print $ flip y [1..100] $ \f (x:xs) -> case xs of
[] -> x
_ -> x + f xs
これを分解して考えると
\f (x:xs) -> case xs of
[] -> x
_ -> x + f xs
これが "関数を引数にとって、その関数を関数を使った新しい関数を返す関数"
flipは引数の順番を変えるものなので今回は別によいとしてつまり
y x = x(y x) -- Yコンビネータ
x = \f (x:xs) -> case xs of
[] -> x
_ -> x + f xs
f = y(x) -- 不動点を求める
main =
print $ f [1..100] -- 5050
? なぜこれが必要なのか？
つまり、今プログラムを書くときに、「プログラムの書き方」といって「スコープはせまく」とか「型あり言語は実行時エラーがでにくい」とかいう話をしてるのは、その背景にはラムダ計算があるわけだ。
ラムダ計算を基礎としてプログラムを考えていくことで、確実に動くプログラムを書くということを考えれるようになる。このようなことから、並列計算でのプログラム記述などに関数型言語が使われるようになっている。
並列計算では、プログラムを動かして検証するということは非常に難しい。ラムダ計算など、検証能力を持った計算モデルで、動かさなくても検証を行えるようにするわけだ。
あとは、メモ化と組み合わせてパフォーマンスを上げることもできる。
初めてHaskell触った。僕自身がまだまだですが素晴らしそうな言語です。
あとQiitaで数式書けるの感動した