不動点演算子 - 純粋関数型雑記帳
昨日日記の日付を間違ってしまって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コンビネータを読み解こう - ボクノス
Y コンビネータって何？ - IT戦記で話題になってるYコンビネータがイマイチわからない。 良記事発見したので、Y CombinatorのYコンビネータを読み解いて行きたいと思います。英語版も必見デス。 相当長いです。 Yコンビネータとはナニモノ!? そういや、再帰って、名前が無いと再帰出来ないのかなぁ・・・全ての式がλで書けるなら、再帰関数もλで書けるはずだ。名前イラナイ!!という時、困っちゃうのが再帰関数の定義。僕の少ない頭では定義出来ませんでした。 「再帰をλで書きたい」 と、思ったときに登場するのが「Yコンビネータ」らしい。追っていく。 階乗ってなんだっけ まずは復習。とりあえず階乗を書きます。 (define (fact n) (if (zero? n) 1 (* n (fact (- n 1))))) (fact 10) ; 3628800 式をを分解すると、 (* 10 (*
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
