Gute Erklärung von "Combinators" (Für nicht-Mathematiker)

Hat jemand eine gute Erklärung von "combinators" (Y-combinators etc. und NICHT das Unternehmen)?

Ich bin auf der Suche nach einem für das praktische-Programmierer, die Rekursion versteht und höherer Ordnung Funktionen, die aber nicht über eine starke Theorie oder mathematischen hintergrund.

(Hinweis: ich spreche diese Dinge)

InformationsquelleAutor interstar | 2008-09-18
  1. 29

    Sei denn, Sie sind tief in der Theorie, können Sie die Y combinator
    als ein netter trick, mit Funktionen, wie Monaden.

    Monaden erlauben, Sie an die Kette von Aktionen, die Y-combinator können Sie
    Definition von selbst-rekursiven Funktionen.

    Python hat eine eingebaute Unterstützung für selbst-rekursive Funktionen, so dass Sie
    können Sie definieren, ohne Y:

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

> fun()
bla
bla
bla
...

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

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

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

    Die Lösung ist ein pass fun sich als argument, um fun:

    > 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
...

    Alle es tut, aufrufen einer Funktion mit sich selbst als argument.

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

    • Technisch ist der Omega-combinator — der tatsächliche Y-combinator ermöglicht, die Funktion zu nutzen, Argumente zu finden 🙂
    • Schließlich verstanden die Y-combinator nach der Suche SO für eine halbe Stunde. Die besten Antworten auf, SO sind diejenigen, welche kurz mit nur alltägliche Sprache.
    InformationsquelleAutor
  2. 22

    Reginald Braithwaite (aka Raganwald) hat er eine tolle Serie auf combinators in Ruby hinüber zu seinem neuen blog, homoiconic.

    Während er nicht (meines Wissens) Blick auf die Y-combinator selbst, er hat den Blick auf andere combinators, zum Beispiel:

    und ein paar Beiträge auf, wie Sie kann verwenden Sie.

    • Ja, ich habe bemerkt, dass die Serie mich. Ich brauche die Untersuchung der Beispiele ein bisschen mehr, weil ich bin nicht fließend in Ruby, aber es ist toll.
    InformationsquelleAutor
  3. 11

    Zitat Wikipedia:

    Einen combinator ist ein higher-order-Funktion, die verwendet nur die Funktion, Anwendung und früher definiert combinators zu definieren, die eine Folge seiner Argumente.

    Nun, was hat das zu bedeuten??? Es bedeutet einen combinator ist eine Funktion (Ausgang ist bestimmt allein durch seinen input), deren Eingang enthält eine Funktion als argument.

    Welche Bedeutung haben solche Funktionen Aussehen, und was werden Sie verwendet? Hier sind einige Beispiele:

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

    Hier o ist ein combinator, die 2 Funktionen f und g aus und liefert eine Funktion als Ergebnis wird die Zusammensetzung der f mit g nämlich f o g.

    Combinators können ausgeblendet werden, um die Logik. Sagen wir, wir haben einen Datentyp NumberUndefined, wo NumberUndefined nehmen können, auf einen numerischen Wert Num x oder einen Wert Undefined, wo x a ist ein Number. Nun wollen wir bauen addition, Subtraktion, Multiplikation und division für diese neu numerischen Typ. Die Semantik ist die gleiche wie für diejenigen der Number außer wenn Undefined ist ein input, der output muss auch Undefined und bei der Division durch die Anzahl 0 ist die Ausgabe auch Undefined.

    Könnte man schreiben die mühsame code 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 input-Werte. Nur division spielt ein bisschen mehr. Die Lösung ist ein Extrakt aus der Logik, indem es einen combinator.

    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 verallgemeinert werden und in den so genannten Maybe Monade, die Programmierer nutzen in funktionalen Sprachen wie Haskell, aber ich werde nicht dorthin gehen.

    InformationsquelleAutor Thomas Eding
  4. 7

    Einen combinator ist die Funktion mit keine freien Variablen. Das bedeutet unter anderem, dass der combinator keine Abhängigkeiten haben, die auf Dinge außerhalb der Funktion, nur auf die Parameter der Funktion.

    Mit F# dies ist mein Verständnis des combinators:

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

    In die oben genannte Summe ist ein combinator, da beide a und b sind gebunden an die Funktion Parameter.

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

    Die obige Funktion ist nicht combinator, wie es verwendet sum, die nicht eine gebundene variable (d.h., es kommt nicht aus einer der Parameter).

    Können wir machen sum3 ein combinator, indem Sie einfach übergeben Sie die Summe-Funktion als Parameter:

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

    Diese Weise sumFunc ist gebunden und damit die gesamte Funktion ist ein combinator.

    So, dies ist mein Verständnis des combinators. Ihre Bedeutung, auf der anderen Seite, noch entgeht mir. Wie andere darauf hingewiesen, fixed-point-combinators ermöglichen die express eine rekursive Funktion ohne explicit Rekursion. I. e. anstatt das sich die recusrsive Funktionsaufrufe lambda-Ausdruck, der übergeben wird als eines der Argumente.

    Hier ist eine der am meisten verständlich combinator, die Ableitungen, die ich gefunden habe:

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

    • Was + in der definition von sum? Es ist nicht gebunden.
    InformationsquelleAutor Igor Zevaka
  6. 1

    Ich bin ziemlich kurz, auf der Theorie, aber ich kann Ihnen ein Beispiel geben, dass setzt meine Phantasie aflutter, die hilfreich sein können. Die einfachste interessant combinator ist wohl "testen".

    Hoffe du weißt Python

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

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

    Verwendung:

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

    test wertet das zweite argument, wenn das erste argument wahr ist, sonst das Dritte.

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

    Ganze Systeme aufgebaut werden kann, von ein paar grundlegende combinators.

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

    InformationsquelleAutor mbac32768
  7. 1

    Dies ist eine gute Artikel.
    Die code-Beispiele sind in Schema, aber Sie sollte nicht schwer zu Folgen.

    • Ich hatte gehofft, für etwas ein bisschen mehr einführende als die dreamsongs ein. Vielleicht mit etwas mehr motivation, über das, was problem Sie Adresse usw.
    InformationsquelleAutor Jonathan Arkell
  8. 0

    Kurz -, Y-combinator ist ein höherer Ordnung-Funktion, die verwendet wird, zu implementieren Rekursion auf lambda-Ausdrücke (anonyme Funktionen). Überprüfen Sie die Artikel Wie Erfolgreich die Rekursion Ohne Wirklich Recursing von Mike Vanier - es ist eines der besten praktischen Erläuterung dieser Frage, die ich gesehen habe.

    Auch, Scannen Sie den SO-Archive:

    InformationsquelleAutor mloskot
Schreibe einen Kommentar