不動点演算子 - 純粋関数型雑記帳
昨日日記の日付を間違ってしまって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 ->
SICPを読む(39) 問題 2.6 Church数 - ボクノス
わからないときは、わかっている所を書き出そう。 Church数ってなんだ!! 404 Blog Not Found:TuringとChurchの狭間で 要は、ある数は、ある関数fを何回xに適用するか、という定義にしてしまうのである。 Church 数 -- OCaml.JP OCamlだけど、わかりやすい。 selflearn @ ウィキ - SICP (問題2.1 -) かなり参考になりました。 なんとなく掴めた所でコーディング。 まずは定義 Church数を定義すると。 (define zero (lambda (f) (lambda (x) x))) (define one (lambda (f) (lambda (x) (f x)))) (define two (lambda (f) (lambda (x) (f (f x))))) 実行してみると、 #を返すだけで、何をやっている
Y コンビネータについて調べてみた - F.Ko-Jiの「一秒後は未来」
Y コンビネータって何？ – IT戦記 Y コンビネータすら知らない(研究室で勉強してたかもしれないけど記憶にない)のでそこだけ調べてみた。 f=g(f) となるような関数fのことを不動点と呼ぶ 不動点を表すための演算子が不動点演算子 Y コンビネータは不動点演算子と呼ばれるものの一種 λ計算では Y = λf.(λx.f(xx))(λx.f(xx)) で定義できる。 λ計算ではYを用いると Yg が g の不動点 となる。 Y コンビネータを利用するとλ計算で再帰的な関数を定義できる Yg = g(Yg) の証明 (→はβ簡約) Yg = (λf.(λx.f(xx))(λx.f(xx)))g → (λx.g(xx))(λx.g(xx)) → g((λx.g(xx))(λx.g(xx))) g(Yg) = g((λf.(λx.f(xx))(λx.f(xx)))g) → g((λx.g(xx
Ｙコンビネータって何に使うの？ - sumiiのブログ
という反応が複数。λ計算という「lambdaしかない」計算体系があって、それでも再帰が表現できる（のでチューリング完全である）ことを示すために使います。Schemeっぽく書くと e ::= x | (lambda (x) e) | (e1 e2)という構文と ((lambda (x) e1) e2) --> [e2/x]e1という簡約で定義される言語です（右辺はe1の中のxにe2を代入した式）。 そんなことよりも、λ計算を習ってないのにＹコンビネータについて聞いたことがある、というgeneration gapに年をとったショックを受けたり。そういう私の20代も昨日（今日の深夜？）で終了。 追記：Haskellなどlazyな言語だったら、 (define (my-fib m) ((my-make-fib my-make-fib) m))の部分は (define my-fib (my-make
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Luca Bolognese
The Mellow Musings of Dr. T
http://ja.doukaku.org/comment/2782/
Lua/組み込み - assari