"Combinators"の良い説明（非数学者の方）

Question

"コンビネータ"（Y-コンビネータなど、NOTthe company）については、誰でも良い説明がありますか？

私は再帰関数と高次関数を理解しているが、強い理論や数学の背景を持っていない実用的なプログラマーのためのものを探しています。

（注：私はおよそthese things話しているということ）

Answer 1

これは良いarticleです。 コード例はschemeにありますが、それに従うのは困難ではありません。

Answer 2

理論に深く関わっていない限り、Yコンビネータ は、モナドのような機能を持つきちんとしたトリックとみなすことができます。

モナドでアクションを連鎖させることができます.Yコンビネータでは、 に自己回帰関数を定義することができます。

Pythonは自己再帰関数のサポートを内蔵しているので、あなた はYなく、それらを定義することができます。

> def fun(): 
> print "bla" 
> fun() 

> fun() 
bla 
bla 
bla 
... 

funはfun自体の内部にアクセス可能であるので、我々は簡単にそれを呼び出すことができます。

しかし、どのようなPythonは異なっていた、とfunはfun内部にアクセス可能 なかったら？

> def fun(): 
> print "bla" 
> # what to do here? (cannot call fun!) 

ソリューションは、funへの引数としてfun自体を渡すことです：

> def fun(arg): # fun receives itself as argument 
> print "bla" 
> arg(arg) # to recur, fun calls itself, and passes itself along 

そしてYは、可能なことを行います

> def Y(f): 
> f(f) 

> Y(fun) 
bla 
bla 
bla 
... 

それは自分自身で関数を呼び出すんすべてを引数として。

（Yのこの定義は、100％正しいかどうかはわからないが、私はそれが一般的な考えだと思います。）

Answer 3

レジナルドブレイスウェイト（別名Raganwaldは）オーバーRubyでコンビネータに大きなシリーズを執筆されています彼の新しいブログでhomoiconic。

彼は（私の知る限り）は、Yコンビネータ自体を見ていませんが、彼は、例えば、他のコンビネータを見ない：

• Kestrel
• Thrush
Cardinal
• Obdurate Kestrel
• 他ひと味違う鳥

と投稿方法はcanuseです。

Answer 4

私は理論的にはかなり短いですが、私はあなたに役立つかもしれない想像力を盛り上げる例を挙げることができます。最も単純な興味深い組み合わせはおそらく "テスト"です。それ以外の場合は第三、第一引数がtrueの場合

>>> test(tru,"goto loop","break") 
'goto loop' 
>>> test(fls,"goto loop","break") 
'break' 

テストは、第二引数に評価されます。

あなたはPythonの

tru = lambda x,y: x 
fls = lambda x,y: y 

test = lambda l,m,n: l(m,n) 

使い方を知っている願っています。

>>> x = tru 
>>> test(x,"goto loop","break") 
'goto loop' 

いくつかの基本コンビネータからシステム全体を構築することができます。

（この例では、多かれ少なかれタイプからコピーされ、ベンジャミン・C・ピアスによってプログラミング言語れる）

Answer 5

引用ウィキペディア：

コンビネータのみ機能アプリケーションを使用して高次関数であります以前に定義されたコンビネータを使用して、その引数から結果を定義します。

これはどういう意味ですか？これは、コンビネータが、入力が関数を引数として含む関数（出力はその入力によってのみ決定される）であることを意味します。

このような機能はどのように見え、どのように使用されますか？ここではいくつかの例は：

(f o g)(x) = f(g(x))

ここoは2つの機能、fとg取り込みコンビネータであり、その結果としての機能を返し、gとfの組成、すなわちf o g。

ロジックを非表示にするためにコンビネータを使用できます。データ型がNumberUndefinedであるとします。ここでは、は数値Num xまたは値Undefinedをとります。xはNumberです。今度は、この新しい数値型の加算、減算、乗算、および除算を構築したいと考えています。意味はUndefinedが入力である場合を除き、の場合と同じですが、出力もUndefinedでなければなりません。数値0で除算すると、出力もUndefinedになります。すべてがUndefined入力値に関する同じロジックを持っているか

Undefined +' num = Undefined 
num +' Undefined = Undefined 
(Num x) +' (Num y) = Num (x + y) 

Undefined -' num = Undefined 
num -' Undefined = Undefined 
(Num x) -' (Num y) = Num (x - y) 

Undefined *' num = Undefined 
num *' Undefined = Undefined 
(Num x) *' (Num y) = Num (x * y) 

Undefined /' num = Undefined 
num /' Undefined = Undefined 
(Num x) /' (Num y) = if y == 0 then Undefined else Num (x/y) 

お知らせ：

一つは以下のように面倒なコードを書くことができます。部門だけがもう少しです。解決策は、それをコンビネータにすることによってロジックを抽出することです。

comb (~) Undefined num = Undefined 
comb (~) num Undefined = Undefined 
comb (~) (Num x) (Num y) = Num (x ~ y) 

x +' y = comb (+) x y 
x -' y = comb (-) x y 
x *' y = comb (*) x y 
x /' y = if y == Num 0 then Undefined else comb (/) x y 

この

は、プログラマはHaskellのような関数型言語での利用を行う、いわゆる Maybeモナドに一般化することができますが、私はそこに行くことはありません。

Answer 6

まもなく、Yコンビネータは、ラムダ式（無名関数）の再帰を実装するために使用される上位関数です。記事How to Succeed at Recursion Without Really RecursingをMike Vanierがチェックしてください - これは私が見たこの問題の最も実用的な説明の1つです。

また、SOアーカイブをスキャン：

• What is a y-combinator?
• Y-Combinator Practical Example

Answer 7

コンビネータはなし自由変数を持つ関数です。これは、とりわけ、コンビネータは、関数パラメータ以外のものに依存しないことを意味します。これはコンビネータの私の理解であるF＃を使用して

：aとbの両方が関数のパラメータにバインドされているので、上記の場合の合計で

let sum a b = a + b;; //sum function (lambda) 

はコンビネータです。それはsumを使用するように

let sum3 a b c = sum((sum a b) c);; 

上記機能は、結合された変数（すなわち、それはパラメータのいずれかから来ていない）されていない、コンビネータありません。

我々は単にパラメータの1つとしてsum関数を渡すことでSUM3コンビネータを行うことができます。

let sum3 a b c sumFunc = sumFunc((sumFunc a b) c);; 

この方法sumFuncがを結合させ、ひいては全体の機能がコンビネータです。

これは私のコンビネータの理解です。一方、彼らの意義は、まだ私を逃れています。他の人が指摘しているように、固定小数点結合子は、explicit再帰なしで再帰関数を表現することを可能にします。私。引数の1つとして渡される関数recambrsiveを呼び出す代わりに、ラムダを呼び出します。ここで

は、私が見つけた最も理解しやすいコンビネータ派生の一つである：

http://mvanier.livejournal.com/2897.html

Answer 8

これは良いものになります：http://www.catonmat.net/blog/derivation-of-ycombinator/