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コンビネータ 継続編
► 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
再帰的な無名関数 - ヒビノキロク
次の関数は再帰的な関数だ。 (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 階乗関数は、 (define fact (lambda (n) (if (= n 0) 1 (* n (fact (- n 1)))))) のように、再帰的に定義できる。 再帰的定義を行なう場合はdefineやletrecを使うけど、 代わりにletを使うと再帰的定義はできない。 defineやletrecをどうしても使いたくないなら、多少工夫がいる。 例えば、factの引数を増やすという方法がある。 (let ((fact (lambda (self n) (if (= n 0) 1 (* n (self self (- n 1))))))) (fact fact 10)) ⇒ 3628800 (中略) 不動点オペレータYを使うと次のように書ける。 (let* ((Y (lambda (g) ((lambda (s) (g (lambda (x) ((s s) x))
羊堂本舗 脳ざらし紀行 (2003-10-22)
_ [ネット] Fの不動点 ラムダ式fを受けとったら、ラムダ式を返す次のようなプロシージャFを定義します。 (define F (lambda (f) (lambda (n) (if (= n 0) 1 (* n (f (- n 1))))))) とりあえず簡単な例で計算してみましょう。Fに常に5を返すラムダ式を渡して、返ってきたラムダ式に3を渡してみましょう。 ((F (lambda (n) 5)) 3) いくらになるでしょうか。 ;; => (* 3 (f (- 3 1))) => 15 15になりました。そして、次のようなプロシージャ fを考えます。 (define f (lambda (s) (F (lambda (x) ((s s) x))))) fはラムダ式を受けとるようなラムダ式sを受けとって、ラムダ式を生成した後、それをFに渡します。 さて、次のような単純なプロシージャhを
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ページを開く
Lua/組み込み - assari