F#入門
コンビネータ ラムダ計算の親戚みたいな理論として、コンビネータ理論がありますが このページの趣旨は、理論的なことはさておき コンビネータを使って遊んでみようというものです。 例えばコンビネータを使うと 「引数の順序を入れ替えたり、入れ替えて適用する」 といったことができます。 なお、ここではλ式について少し知識があることを仮定しています。 最初にコンビネータとは何かというと 「自由変数を含まないλ式」、と定義されています。 自由変数とはλ式において束縛されていない変数のことで letによる関数定義をλ式の定義とみなすと 引数が束縛変数、 既に定義されてる識別子が自由変数 になります。 コンビネータに関する本として スマリヤンの本「To mock a mocking bird」 (邦題：数学パズル ものまね鳥をまねる―愉快なパズルと結合子論理の夢の鳥物語) は有名です。 この本の楽しいところ
Church numerals と Lambda Calculus アルゴリズムとデータ構造入門 補足
Church Numerals と Lambda Calculus アルゴリズムとデータ構造入門 補足 後半は佐藤雅彦先生に教えてもらいました. SICP Exercise 2.4 〜 Exercise 2.6 誤解を恐れずに大雑把にいうと, λ計算では名前つきのシンボル (名前付きの手続き) による再帰呼出しや special form が使えないところが Scheme と違うところです. そのため, λ計算を Scheme で行うためにはいろいろな工夫が必要となります. そのポイントは closure (閉包) と呼ばれる構造です. 自然数 n の Church numeral を c(n) とすると, c(n) f x = (f ... (f x)), ただし, f は n 回出現. となることを利用します. まず, c0 と successor を定義します. (SICP Ex.
おとうさん、ぼくにも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 となります。λの引数部分を与えられた引数で置
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) （当てるアルファベットが違うのはたまに見
不動点オペレータについて
不動点オペレータ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))
Unlambda
Your Functional Programming Language Nightmares Come True. 関数型言語の悪夢がやってくる Unlambdaについて 公式サイト: http://www.eleves.ens.fr:8080/home/madore/programs/unlambda/ Unlambdaは、obfuscated programming languages (混乱させるプログラム言語、といったところでしょうか) の一種として開発された言語です。 しかしただそれだけではなく、純粋関数型言語というもう一つの特徴も持っています。 そのためオブジェクトは関数しかなく、数値や文字列などというものは(組み込みでは)存在しません。 しかしこの極限的な状況でのプログラムには、実に楽しいものがあります。 このページでは、そんなUnlambdaのプログラミングの解説を行い
flatline's Wiki for memo - Y in Practical Programs
大抵，Yコンビネータには型推論はできない． でも例えばStandard MLの再帰関数を定義する機能を使えば楽々定義できる． fun Y f x = f (Y f) x fun fact_ fact x = (* この fact_ を "seed" と呼ぶ *) if x = 0 then 1 else x * fact (x-1) val fact = Y fact_ "Seed" にラッパをかぶせれば機能を楽に付加できる． fun printerWrapper f_ f x = let val result = f_ f x val _ = printInt result in result end val factPrint = Y (printerWrapper fact_) このfactPrintは再帰の途中経過を印字する． Haskellのように副作用をモナドで分離しなければな
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Y-Combinator
http://www.city5.org/AlligatorEggs.html