Y combinator. そして末尾再帰に取り付かれる - rayfillのプログラムネタ帳
不動点演算子といってラムダ計算やらコンビネータ理論やらのものらしいです。 ちゃんと調べてないのでよくわかってません(笑) ただ、これを使うと無名関数を再帰することができる、ということです。 で自分で実装して考えてみる。 まずは再帰のお供、fact関数。 (defun fact (n) (if (<= n 1) 1 (* n (fact (- n 1))))) 末尾再帰にもなっていませんがとりあえず実装。 ここから進めていきましょう。 この関数をlambda関数にした場合、何が使えなくて再帰できないのか？ そう、関数名fact、というか関数自身です。 んじゃどうすればいける？と考えると・・・ないものは無いんで外部から差し込むしかないよなーということになります。 つまり自分自身を引数として受け取って(なんか話が矛盾してきた！(笑))それをfuncallすれば再帰できるはず、ということで定義した
combinator - Nobuhisa's diary
コンビネータとは自由変数を含まないλ項のことをいいますが、Yコンビネータ以外あまり取り上げられていない気がするのですが、これも100年に1度の金融危機の影響かとか、WBC楽しみですねだとか、そういえば今年雪祭り行けなかったんですよとか、最近携帯変えましたとか色々あるのですが、自分の練習もかねて、そんなコンビネータ達と戯れたいと思います。 沢山ある！ Y以外にも広く知られている（？）コンビネータはいっぱいあるようですが、その中からいくつか。 I ≡ λx.x K ≡ (λx.(λy.x)) //以下、簡単に λx y.x と書きます F ≡ λx y.y M ≡ λx.xx S ≡ λx y z.xz(yz) B ≡ λx y z.x(yz) C ≡ λx y z.xzy L ≡ λx y.x(yy) Y ≡ (λx.xx)(λx.xx) (SLL) （当てるアルファベットが違うのはたまに見
Combinator Birds
((S(K((S((SK)K))(K((S(K(S((SK)K))))K)))))((S(K((S(K((S(KS))K)))((S(KS))K))))((S(K(S((SK)K))))K)))
いげ太のブログ: フドーテンが倒せない
不動点とは、関数を適用しても動かない点、つまり、f(x) = x なる x が不動点である。 と、簡潔に説明されても理解できない素地のなさ。そんなわけで、ググりつつ、妄想しつつ、なんとか解せぬものかと頭をひねり、首をひねるのである。 一次関数で考えてみる。たとえば、y = 2x - 3 （傾きが 2 で切片が -3）において、y = x であるときの x を求めればよいので、y に x を代入し、x = 2x - 3 を解いて、x = 3 が得られ、よって、y = 2x - 3 の不動点は 3 である。グラフで考えれば、x 軸と y 軸が同じである点が不動点であるので、不動点とは、ある関数 f(x) が f(x) = x （傾きが 1 で切片が 1）のグラフと交わる点である、と言い換えることもできる。 ここで、f(x) = x を x 軸上に横に平行移動したようなグラフについて考えれば、そ
不動点オペレータについて
不動点オペレータ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))
fix と memo とそのおまけ。 - 嫌気性平均律
不動点オペレータと関数のメモ化で大いに遊ぶのが流行っているみたいで（k.inaba さんの発端の記事、結城浩さんによるリンク集）、楽しそうなのでひっそり書いてみます。Common Lisp で、というか xyzzy でちょこちょこしてみます。 まずは普通に。 とりあえず不動点オペレータを教科書的に書いてみます。funcall が健全な精神に対して極めて有害そうであることがよく判ります。 ;;;figure.1 (defun %fib (f) #'(lambda (x) (if (<= x 1) 1 (+ (funcall f (- x 1)) (funcall f (- x 2)))))) (defun fix (f) (funcall #'(lambda (g) (funcall g g)) #'(lambda (h) #'(lambda (x) (funcall (funcall f
不動点演算子ふたたび - sumiiの日記
（追記：Ｙコンビネータって何に使うの？） Yコンビネータ（Curryの不動点演算子）を説明するのがプチブーム（死語）らしいので、ふたたび挑戦。 まず、ふつーに再帰関数factをSchemeで定義してみる。 (define fact (lambda (n) (if (= n 0) 1 (* n (fact (- n 1))))))この定義は、右辺にfact自身が出現するので、再帰的定義なのであった。ここから右辺にfactが出現しないようにするのが目標。とりあえず、factを関数の引数として外から受け取るようにしてみる。 (define make-fact (lambda (my-fact) (lambda (n) (if (= n 0) 1 (* n (my-fact (- n 1)))))))これは( (make-fact fact) 10)みたく使えるが、make-factを呼び出す際に
2005-11-12
今日は寒い．朝は雨が降ってたようだが，昼前にはすっかり秋晴れである． PCをいじってると，つい鉛筆に手を伸ばして紙にあれこれ書くのが面倒になってしまう．しかしPC上では計算も図を描くのも気軽にはできないから，ちょっと頭の整理をしたいときに自由に紙の上にあれこれを書きつけるのはやはり大事なことだ．紙に書く/描くことの重要性は言うまでもないことで，私は普段はどこにでも計算用紙を持ち歩いてたりするんだが，まだPCとのインターオペラビリティ（？）には自分なりの追求の余地があるな，と思った次第． あ，「タブレットPCを買え」というのはナシでお願いします． （Helmholtzはともかく）未だに区別がつかない．Laplacian（だけ）を使う3つ： Laplace方程式 ⊂ Poisson方程式 ⊂ Helmholtz方程式 か... どうせ明日になれば忘れるのだろうな． Δφ=0 (Laplace)
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
不動点演算子 - 純粋関数型雑記帳
昨日日記の日付を間違ってしまって8月11日が欠番になってしまった。 が、まぁ、いいか。めんどくさいし。 今日やった量子計算の勉強会の発表で力を使い果たした…かも。 ねたに困ったときはライトな?話題でも。いつもどおりだらだらと。 λ計算にて再帰的な関数の意味づけに不動点演算子というものを用いる。 不動点演算子(Y)は、λ式Mに対して Y M = M (Y M) を満たすようなλ式で、 具体的には Y = λf.(λx.f(x x)) (λx.f(x x)) と定義される(これは一例。定義は他にも考えられる)。 数学的には(Y M)がMの不動点になっているので、 Yを不動点演算子というのだが、 Y M => M (Y M) => M (M (Y M)) => ... のようにMを繰り返し適用できるので再帰的な計算を行える。 ここでYの型を考えると、Y MがMの不動点なので Y :: (a ->
Y Combinator
In this file we derive the Y combinator, one of the fundamental results of recursive procedure theory. You already know that in some cases it is not necessary to give a procedure a name. For example, ((lambda (x) (+ x 1)) 6) adds 1 to 6 without naming the procedure that does it. But, what about a recursive procedure? For example, (define fact (lambda (n) (if (zero? n) 1 (* n (fact (- n 1)))))) whi
Y Combinatorが凄すぎる！ - yuji1982の日記
って言いたかったけど、難しくて理解できません＞＜ ラムダの話をしてたら会社の人が、Recursive lambda expressions – The Mellow Musings of Dr. Tの説明をしてくれました。 去年の秋にブクマで見たときは難しそうだからスルーしたけど、、今回は理解しようと頑張って見てみます。 やっぱり理解はできないorz でも、ここで諦めたら負けなので、とりあえず触ってみました。 昔、書いてみたフィボナッチ数列で試してみる public static void Main() { foreach (var item in Math.Fib(10)) Console.WriteLine(item); } static public class Math { static public IEnumerable<int> Fib(int count) { Func<i
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
