[function] "Combinators"の良い説明(非数学者の場合)


Answers

Reginald Braithwaite(別名Raganwald)は、彼の新しいブログhomoiconicでRubyのコンビネータの素晴らしいシリーズを書いています。

彼は私の知る限り、Y-コンビネータそのものを見ていないが、他のコンビネータを見ている。例えば:

どのようにそれらcan use canかについてのいくつかの記事can use

Question

誰でも "コンビネータ"(Y-コンビネータなど、会社ではない )についての良い説明がありますか?

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

(注:私はこれらのことについて話しています




コンビネータは自由変数持たない関数です 。 これは、とりわけ、コンビネータは、関数パラメータ以外のものに依存しないことを意味します。

F#を使用すると、これは私のコンビネータの理解です:

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

上のケースでは、 ab両方が関数パラメータにバインドされているため、sumはコンビネータです。

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

上記の関数は結合変数ではないsum使用するため、コンビネータではありません(つまり、パラメータのいずれにも該当しません)。

単にsum関数をパラメータの1つとして渡すことによって、sum3をコンビネータにすることができます:

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

このようにsumFuncバインドされており、したがって関数全体がコンビネータです。

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

ここに私が見つけた最も理解できるコンビネータの導出の一つがあります:

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







私は理論的にはかなり短いですが、私はあなたに役立つ可能性がある私の想像力を盛り上げる例を与えることができます。 最も単純な興味深い組み合わせはおそらく "テスト"です。

あなたが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'

テストは、最初の引数がtrueの場合は2番目の引数を評価し、それ以外の場合は3番目の引数を評価します。

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

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

(この例は、Benjamin C. Pierceによって多少なりともTypes and Programming Languagesからコピーされています)




Links