Gute Erklärung von "Combinators" (für Nicht-Mathematiker)

Question

Jeder hat eine gute Erklärung der "Kombinatoren" (Y-Kombinatoren etc. und NICHTthe company)?

Ich suche eine für den praktischen Programmierer, der Rekursion und Funktionen höherer Ordnung versteht, aber keine starke Theorie oder mathematischen Hintergrund hat.

(Hinweis: dass ich rede these things)

Answer 1

Dies ist eine gute article. Die Codebeispiele sind im Schema, aber sie sollten nicht schwer zu folgen sein.

Answer 2

Sofern Sie nicht tief in der Theorie sind, können Sie den Y-Kombinator als einen ordentlichen Trick mit Funktionen, wie Monaden betrachten.

Monaden können Sie Aktionen ketten, der Y-Kombinator ermöglicht es Ihnen, selbstrekursive Funktionen zu definieren.

Python hat eine integrierte Unterstützung für die Selbst rekursiven Funktionen, so dass Sie können sie ohne Y definieren:

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

> fun() 
bla 
bla 
bla 
... 

fun innen fun zugänglich selbst ist, so können wir es leicht nennen.

Aber was, wenn Python anders waren, und fun waren nicht zugänglich innen fun?

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

Die Lösung ist fun selbst als Argument an fun weitergeben müssen:

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

Und Y macht das möglich:

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

> Y(fun) 
bla 
bla 
bla 
... 

Alles, was es mit sich selbst eine Funktion nicht nennen als Argument.

(ich weiß nicht, ob diese Definition von Y 100% richtig ist, aber ich denke, es ist die allgemeine Idee.)

Answer 3

Reginald Braithwaite (aka Raganwald) eine große Serie auf combinators in Ruby geschrieben hat über in seinem neuen Blog, homoiconic.

Während er nicht (meines Wissens) auf der Y-Combinator sucht sich, er in anderen combinators sieht, zum Beispiel:

• die Kestrel
• die Thrush
• die Cardinal
• die Obdurate Kestrel
• andere Schrullige Vögel

und ein paar Beiträge, wie Sie canuse sie.

Answer 4

Ich bin ziemlich kurz an der Theorie, aber ich kann Ihnen ein Beispiel geben, das meine Phantasie beunruhigt, was für Sie hilfreich sein kann. Der einfachste interessante Kombinator ist wahrscheinlich "Test".

Hoffe, dass Sie Python kennen

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

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

Verbrauch:

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

Test auf das zweite Argument ausgewertet wird, wenn das erste Argument wahr ist, sonst wird die dritte.

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

Komplette Systeme können aus ein paar grundlegenden Kombinatoren aufgebaut werden.

Answer 5

Zitat Wikipedia (Dieses Beispiel ist mehr oder weniger aus Typen und Programmiersprachen von Benjamin C. Pierce kopiert):

A combinator ist eine Funktion höherer Ordnung, die nur Funktionsanwendung verwendet und früher definierte Kombinatoren, um ein Ergebnis aus seinen Argumenten zu definieren.

Was bedeutet das nun? Es bedeutet, dass ein Kombinator eine Funktion ist (die Ausgabe wird ausschließlich durch ihre Eingabe bestimmt), deren Eingabe eine Funktion als Argument enthält.

Wie sehen solche Funktionen aus und wofür werden sie verwendet? Hier sind einige Beispiele:

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

o hier ist ein Kombinator, der in 2-Funktionen übernimmt, f und g und gibt eine Funktion als Ergebnis der Zusammensetzung des f mit g, nämlich f o g.

Kombinatoren können verwendet werden, um Logik zu verstecken. Angenommen, wir haben einen Datentyp NumberUndefined, wobei NumberUndefined einen numerischen Wert Num x oder einen Wert Undefined annehmen kann, wobei x ein Number ist. Nun wollen wir Addition, Subtraktion, Multiplikation und Division für diesen neuen numerischen Typ konstruieren. Die Semantik ist dieselbe wie für die von Number, außer wenn Undefined ein Eingang ist, muss der Ausgang auch Undefined sein und wenn durch die Nummer 0 dividiert wird, ist der Ausgang auch Undefined.

Man könnte die langweilige Code schreiben, wie folgt:

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) 

Beachten Sie, wie die alle die gleiche Logik über Undefined Eingangswerte haben. Nur Division macht ein bisschen mehr. Die Lösung besteht darin, die Logik zu extrahieren, indem man sie zu einem Kombinator macht.

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 

Dies kann in die sogenannten Maybe Monade verallgemeinert werden, die Programmierer Verwendung in funktionalen Sprachen wie Haskell zu machen, aber ich werde nicht dorthin gehen.

Answer 6

Kurz gesagt, Y-Kombinator ist eine Funktion höherer Ordnung, die verwendet wird, um Rekursion auf Lambda-Ausdrücke (anonyme Funktionen) zu implementieren. Überprüfen Sie den Artikel How to Succeed at Recursion Without Really Recursing von Mike Vanier - es ist eine der besten praktischen Erklärung dieser Angelegenheit, die ich gesehen habe.

auch scannen die SO-Archive:

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

Answer 7

A combinator ist Funktion mit keine freien Variablen. Das bedeutet unter anderem, dass der Kombinator keine Abhängigkeiten von Dingen außerhalb der Funktion hat, sondern nur von den Funktionsparametern.

Mit F # Das ist mein Verständnis von combinators:

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

Im obigen Fall Summe ist ein combinator weil beide a und b auf die Funktionsparameter gebunden sind.

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

Die obige Funktion ist nicht ein Kombinator, wie es sum verwendet, die nicht eine gebundene Variable (das heißt, es kommt nicht von einem der Parameter).

Wir können einfach durch das Bestehen der Summenfunktion als einer der Parameter SUM3 eine combinator machen:

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

Auf diese Weise sumFunc ist gebunden und damit die gesamte Funktion ist eine combinator.

Also, das ist mein Verständnis von Kombinatoren. Ihre Bedeutung hingegen entkommt mir immer noch. Wie andere darauf hingewiesen haben, erlauben Festkomma-Kombinatoren, eine rekursive Funktion ohne explicit Rekursion auszudrücken. I.e. Anstatt sich die recusrsive Funktion zu nennen, wird Lambda aufgerufen, das als eines der Argumente übergeben wird.

ist hier einer der verständlichste combinator Ableitungen, die ich gefunden:

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

Answer 8

Das sieht eine gute: http://www.catonmat.net/blog/derivation-of-ycombinator/