「コンビネーター」（Yコンビネーターなどであり、会社ではありません ）について適切な説明を受けた人はいますか？
再帰と高階関数を理解しているが、理論や数学のバックグラウンドが強くない実用的なプログラマーを探しています。
（注：私はこれらのことについて話していること）
interstar
質問する
11316 次
8 に答える
34
理論に詳しくない限り、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% 正しいかどうかはわかりませんが、一般的な考え方だと思います。)
于 2008-09-19T13:45:20.113 に答える
15
ウィキペディアの引用:
コンビネータは、関数適用と以前に定義されたコンビネータのみを使用して引数からの結果を定義する高階関数です。
これはどういう意味ですか？これは、コンビネータが関数 (出力はその入力によってのみ決定される) であることを意味し、その入力には引数として関数が含まれます。
そのような関数はどのように見え、何に使用されますか? ここではいくつかの例を示します。
(f o g)(x) = f(g(x))
これは、とoの 2 つの関数を受け取り、その結果としてwithの構成、つまりを返すコンビネータです。fgfgf o g
コンビネータを使用して、ロジックを非表示にすることができます。数値または値を取ることNumberUndefinedができるデータ型があるとします。ここで、a は aです。次に、この新しい数値型の加算、減算、乗算、および除算を作成します。セマンティクスは のセマンティクスと同じですが、 が入力の場合、出力も である必要があり、数値で割ると出力もになります。NumberUndefinedNum xUndefinedxNumberNumberUndefinedUndefined0Undefined
以下のように面倒なコードを書くことができます:
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)
Undefined入力値に関して、すべてが同じロジックを持っていることに注目してください。除算のみがもう少し多くのことを行います。解決策は、ロジックをコンビネータにして抽出することです。
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
Maybeこれは、プログラマーが Haskell のような関数型言語で使用する、いわゆるモナドに一般化できますが、そこには行きません。
于 2010-02-06T23:45:52.997 に答える
6
コンビネータは自由変数のない関数です。つまり、とりわけ、コンビネーターは関数の外部のものには依存せず、関数のパラメーターにのみ依存することを意味します。
F# を使用すると、これはコンビネーターに関する私の理解です。
let sum a b = a + b;; //sum function (lambda)
a上記の場合、との両方bが関数パラメーターにバインドされているため、 sum はコンビネーターです。
let sum3 a b c = sum((sum a b) c);;
上記の関数はsum、バインドされた変数ではない (つまり、どのパラメーターからも取得されない) を使用するため、コンビネーターではありません。
パラメータの 1 つとして sum 関数を渡すだけで、sum3 をコンビネータにすることができます。
let sum3 a b c sumFunc = sumFunc((sumFunc a b) c);;
この方法sumFuncはバインドされているため、関数全体がコンビネーターです。
これが私のコンビネータの理解です。一方、それらの重要性は、まだ私を逃れています。他の人が指摘したように、固定小数点コンビネータを使用すると、再帰なしで再帰関数を表現できexplicitます。つまり、再帰関数はそれ自体を呼び出す代わりに、引数の 1 つとして渡される lambda を呼び出します。
以下は、私が見つけた最もわかりやすいコンビネータの派生の 1 つです。
于 2010-02-07T00:09:12.567 に答える
2
これは良い記事です。コード例はスキーム内にありますが、従うのは難しいことではありません。
于 2008-09-18T22:47:13.167 に答える
2
于 2010-02-23T19:20:18.957 に答える
1
私は理論がかなり不足していますが、私の想像力を揺さぶる例をあげることができます。これはあなたに役立つかもしれません。最も単純で興味深いコンビネータは、おそらく「テスト」です。
Pythonを知っているといいのですが
tru = lambda x,y: x
fls = lambda x,y: y
test = lambda l,m,n: l(m,n)
使用法：
>>> test(tru,"goto loop","break")
'goto loop'
>>> test(fls,"goto loop","break")
'break'
testは、最初の引数がtrueの場合は2番目の引数に評価され、そうでない場合は3番目の引数に評価されます。
>>> x = tru
>>> test(x,"goto loop","break")
'goto loop'
システム全体は、いくつかの基本的なコンビネータから構築できます。
（この例は、ベンジャミンC.ピアスによるタイプとプログラミング言語から多かれ少なかれコピーされています）
于 2008-11-13T01:22:09.413 に答える