Y Combinator
このファイルで、我々は、再帰手続き理論の重要な成果の一つであるYコンビ ネータを導出する。手続きに名前を与える必要がない場合があることが知られ ている。たとえば、 ((lambda (x) (+ x 1)) 6) は、それを行なう手続きを名付けることなく1を6に加える。しかし、再帰手続 きはどうだろうか? たとえば、 (define fact (lambda (n) (if (zero? n) 1 (* n (fact (- n 1)))))) は数nの階乗を計算するが、手続きの最終行で自身に再帰できるようにするた めに名前"fact"が必要であるように思える。しかし、我々はそれは必要でない ことを理解し、そのプロセスにおいて、Schemeを使うことに関する多くの勘を やしなうだろう。我々は一ステップずつ進み、各ステップで"fact"をわずかに 変更する。 Step 1. 最初のアイディア
vallog
Gauche が 0.9.1 になってっから（？）、それまで gauche.experimental.apps モジュールにあった ^ とか ^x とかが使えるようになっているみたいです。引数をリストで受け取る時とか笑顔の顔文字みたいになりますよね。(^ _ ^) みたいな。 これで Y コンビネータもすっきりー！ (define Y (^c ((^f (f f))(^g (c (^ x (apply (g g) x))))))) ということで以前書いた Y コンビネータ関連エントリ。 vallog: メモ化された Y Combinator vallog: pluggable Y Combinator vallog: pluggable Y Combinator 2 vallog: また出てきたYコンビネータ。Y!。 vallog: TSS length, Y!, Y-bang vallo
さあ、Yコンビネータ(不動点演算子)を使おう！ - よくわかりません
前回、おとうさんにもわかるYコンビネータ！(絵解き解説編) - よくわかりませんというエントリで、Yコンビネータ(不動点演算子)と再帰の絵解き解説をしました。 Yコンビネータ自身は、結局のところ再帰を産み出してくれるだけです。関数(正確にはλという単純な文字列変換ルール)だけで出来て、プログラミングに関するいろんな原理の研究を可能にするのが凄い訳です。その辺のさわりを、きしださんが解説されています。しかし、単なる再帰なら、実際のプログラミングではYコンビネータなんて使わなくても出来ます。 じゃあ、Yコンビネータとか不動点とかは、偉い学者さんとかが研究に使えばいいもので、普通のプログラマには何の意味もないモノなのでしょうか？ というわけで、今回はポジティブに、Yコンビネータや不動点で出てくる考え方を、理論だけじゃなく、実際のプログラミングに応用する例を見てみましょう。 今回、プログラムの例を
おとうさんにもわかるYコンビネータ！(絵解き解説編) - よくわかりません
先日YコンビネータのきしださんのYコンビネータのエントリが話題になっていました。 ずいぶん日にちが経ってしまいましたが、自分も、自分なりにYコンビネータのあたりを絵解きで整理してみたいと思います。きしださんのエントリタイトル*1に引っ掛けて、目標として、自分の父親(非プログラマ。その辺のおっさん)でも解る内容を目指します。 なぜ不動点演算子というのか、不動点だったらなぜ再帰なのか、この辺りも含めて、実感を持って納得できればいいなと思います。 きしださんのエントリのおさらい 本題の前に、きしださんのエントリをおさらいしておきます。 Yコンビネータはただのオモチャじゃないんだよ 関数だけで色んな事が出来る 条件分岐をする関数ってのもある。 再帰(ループ)を作れる関数もある。←これがYコンビネータ。 数値も関数で表現できる。 つまり、関数だけで、条件分岐も、再帰(ループ)も、数値も作れちゃう！！
Yコンビネータ 継続編
► 2022 (2) ► 10月 (1) ► 2月 (1) ► 2021 (51) ► 11月 (2) ► 10月 (2) ► 9月 (4) ► 8月 (4) ► 7月 (4) ► 6月 (4) ► 5月 (3) ► 4月 (10) ► 3月 (7) ► 2月 (4) ► 1月 (7) ► 2020 (155) ► 12月 (7) ► 11月 (10) ► 10月 (8) ► 9月 (8) ► 8月 (11) ► 7月 (21) ► 6月 (19) ► 5月 (14) ► 4月 (20) ► 3月 (13) ► 2月 (10) ► 1月 (14) ► 2019 (293) ► 12月 (11) ► 11月 (12) ► 10月 (24) ► 9月 (29) ► 8月 (27) ► 7月 (36) ► 6月 (40) ► 5月 (24) ► 4月 (35) ► 3月 (42) ► 2月 (6
賢人鳥 - あどけない話
分かった！ 分かった！ 分かった！ 自己言及 ものまね鳥(M)は、自己言及する鳥なんだ！ Haskell では、型推論がジャマして、ものまね鳥を実現できない。 -- Mx = xx m x = x x -- エラーになる ヒバリ(L)も実現できない！ -- Lxy = x(yy) l x y = x (y y) -- エラーになる 当然の帰結として、Haskell では再帰を使わないと賢人鳥(Y)を実現できない！ 賢人鳥1 wikipediaの Y コンビネーターに書かれている最初の賢人鳥はこう。 (define Y (lambda (f) ((lambda (x) (f (lambda (y) ((x x) y)))) (lambda (x) (f (lambda (y) ((x x) y))))))) これは SLL だ！ ;; Sxyz = xz(yz) (define S (lam
Rubyのある風景 - Y Combinator
再帰的な関数を作るときに関数に名前をつけずに定義するにはどうしたらいいのかというのが、Y Combinatorの中心的な話題です。 まずは、再帰の定番、階乗を計算する関数に登場願いましょう。 fact = lambda{|n| if n < 2 1 else n * fact[n - 1] end } puts fact[10] ここからfactという名前を取り除こうというわけですね。 最終目標は、以下のようにして階乗を計算する関数を定義することができるようになることです。 fact = y[lambda{|h| lambda{|n| if n < 2 1 else n * h[n - 1] end } ] ) puts fact[10] ここで出てきたyが、Y Combinatorと呼ばれるものです。 見やすさの為に、factという名前をつけましたが、関数を定義するところではfact
おとうさん、ぼくにもYコンビネータがわかりましたよ！ - 2009-04-09 - きしだのはてな
やっと、Yコンビネータが何を意味するものなのか、どういう意義があるのかがわかりました。 名前を使わず再帰ができますよ！というだけのものじゃなかったのですね。 まずλありき 関数の話をしたいのです。 そのとき、いちいち hoge(x) = x * 2 としてhogeを・・・、とか名前をつけて話を進めるのがめんどうなので、関数を値としてあらわすと便利ということで、λという値を定義するのです。 そうすると、上のhoge関数なんかはλ(x)(x*2)などとあらわせますが、引数をあらわすのに()を使うといろいろまぎらわしいので、 λx.x*2 のように表記します。 というのがλ。 このとき、λになにかわたされたら、引数としてあらわされる部分を単純におきかえます。 (λx.x*2)y とあったら、xの部分をyでおきかえて (λx.x*2)y → y * 2 となります。λの引数部分を与えられた引数で置
再帰的な無名関数 - ヒビノキロク
次の関数は再帰的な関数だ。 (define fact (lambda (n) (if (= n 0) 1 (* n (fact (- n 1)))))) この関数は内部で自分自身を呼び出しているので、普通の方法では無名関数として定義できない。 こういう場合、不動点オペレータというものを使うと以下のようにしてfactを定義することができる。（fact関数の中で直接factという名前を使っていない所がポイント） (define fact (let ((Y (lambda (F) ((lambda (s) (F (lambda (x) ((s s) x)))) (lambda (s) (F (lambda (x) ((s s) x)))))))) (Y (lambda (f) (lambda (n) (if (= n 0) 1 (* n (f (- n 1))))))))) ここで天下り的に出て
Y Combinator - LoveRubyNet
$Id: ycombinator.html,v 1.6 2002/06/27 23:37:39 aamine Exp $ [ruby-list:35058] に刺激を受けて Y combinator を解読してみた。 こんなもん読むくらいなら以下の参考ページを読んだほうがいい。 参考にした (というかほとんどそのままな) ページ (英語) http://www.ececs.uc.edu/~franco/C511/html/Scheme/ycomb.html 動機 再帰関数は再帰するときに自分自身を名前で呼ぶのが普通である。 これをなんとかして名前を使わず、関数そのものを呼ぶように させたい。 求めかた まず単純な fact (階乗) を以下に示す。言語は Scheme である。 (define fact (lambda (n) (if (zero? n) 1 (* n (fact (- n
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
ネタ記録庫/不動点コンビネータ - ocaml-nagoya
Fei Ling's website