webentwicklung-frage-antwort-db.com.de

Was ist ein Y-Kombinator?

Ein Y-Kombinator ist ein Informatik-Konzept von der "funktionalen" Seite der Dinge. Die meisten Programmierer wissen überhaupt nicht viel über Kombinatoren, wenn sie überhaupt davon gehört haben.

  • Was ist ein Y-Kombinator?
  • Wie arbeiten Kombinatoren?
  • Wofür sind sie gut?
  • Sind sie in Verfahrenssprachen nützlich?
372
Chris Ammerman

Wenn Sie bereit für eine lange Lektüre sind, Mike Vanier hat eine großartige Erklärung . Um es kurz zu machen: Sie können die Rekursion in einer Sprache implementieren, die sie nicht unbedingt von Haus aus unterstützt.

194

Ein Y-Kombinator ist eine "Funktion" (eine Funktion, die auf andere Funktionen angewendet wird), die eine Rekursion ermöglicht, wenn Sie nicht von sich aus auf die Funktion verweisen können. In der Informatiktheorie verallgemeinert sie die Rekursion , abstrahiert ihre Implementierung und trennt sie dadurch von der eigentlichen Arbeit der fraglichen Funktion. Der Vorteil, keinen Namen zur Kompilierungszeit für die rekursive Funktion zu benötigen, ist eine Art Bonus. =)

Dies gilt für Sprachen, die Lambda-Funktionen unterstützen. Die Ausdruck - basierte Natur von Lambdas bedeutet normalerweise, dass sie sich nicht mit ihrem Namen auf sich selbst beziehen können. Und dies zu umgehen, indem man die Variable deklariert, auf sie verweist und ihr dann das Lambda zuweist, um die Selbstreferenzschleife zu vervollständigen, ist spröde. Die Lambda-Variable kann kopiert und die ursprüngliche Variable neu zugewiesen werden, wodurch die Selbstreferenz aufgehoben wird.

Y-Kombinatoren sind mühsam zu implementieren und häufig in statisch typisierten Sprachen (die prozeduralen Sprachen häufig sind) zu verwenden, da für Typisierungsbeschränkungen normalerweise die Anzahl der Argumente erforderlich ist Die betreffende Funktion muss zum Zeitpunkt der Kompilierung bekannt sein. Dies bedeutet, dass für jede zu verwendende Argumentanzahl ein y-Kombinator geschrieben werden muss.

Unten sehen Sie ein Beispiel für die Verwendung und Funktionsweise eines Y-Combinators in C #.

Die Verwendung eines Y-Kombinators beinhaltet eine "ungewöhnliche" Art, eine rekursive Funktion zu konstruieren. Zuerst müssen Sie Ihre Funktion als Code schreiben, der eine bereits vorhandene Funktion aufruft, anstatt sich selbst:

// Factorial, if func does the same thing as this bit of code...
x == 0 ? 1: x * func(x - 1);

Dann wandeln Sie das in eine Funktion um, die eine Funktion zum Aufrufen benötigt und eine Funktion zurückgibt, die dies tut. Dies wird eine Funktion genannt, da sie eine Funktion übernimmt und eine Operation damit ausführt, die zu einer anderen Funktion führt.

// A function that creates a factorial, but only if you pass in
// a function that does what the inner function is doing.
Func<Func<Double, Double>, Func<Double, Double>> fact =
  (recurs) =>
    (x) =>
      x == 0 ? 1 : x * recurs(x - 1);

Jetzt haben Sie eine Funktion, die eine Funktion übernimmt und eine andere Funktion zurückgibt, die wie eine Fakultät aussieht, aber statt sich selbst aufzurufen, ruft sie das an die äußere Funktion übergebene Argument auf. Wie macht man das zur Fakultät? Übergeben Sie die innere Funktion an sich. Der Y-Kombinator tut dies, indem er eine Funktion mit einem permanenten Namen ist, die die Rekursion einleiten kann.

// One-argument Y-Combinator.
public static Func<T, TResult> Y<T, TResult>(Func<Func<T, TResult>, Func<T, TResult>> F)
{
  return
    t =>  // A function that...
      F(  // Calls the factorial creator, passing in...
        Y(F)  // The result of this same Y-combinator function call...
              // (Here is where the recursion is introduced.)
        )
      (t); // And passes the argument into the work function.
}

Anstelle des Fakultätsaufrufs selbst wird durch den Fakultätsaufruf der Fakultätsgenerator aufgerufen (der durch den rekursiven Aufruf von Y-Combinator zurückgegeben wird). Und abhängig vom aktuellen Wert von t ruft die vom Generator zurückgegebene Funktion entweder den Generator erneut mit t - 1 auf oder gibt einfach 1 zurück und beendet die Rekursion.

Es ist kompliziert und kryptisch, aber zur Laufzeit rüttelt es alles, und der Schlüssel zu seiner Funktionsweise ist die "verzögerte Ausführung" und das Aufbrechen der Rekursion auf zwei Funktionen. Das innere F wird als Argument übergeben , um in der nächsten Iteration aufgerufen zu werden , nur wenn nötig .

278
Chris Ammerman

Ich habe dies von http://www.mail-archive.com/[email protected]/msg02716.html aufgehoben, was eine Erklärung ist, die ich vor einigen Jahren geschrieben habe.

In diesem Beispiel werde ich JavaScript verwenden, aber auch viele andere Sprachen werden funktionieren.

Unser Ziel ist es, eine rekursive Funktion von 1 Variablen zu schreiben, wobei nur Funktionen von 1 Variablen und keine Zuweisungen verwendet werden, Dinge durch Namen usw. definiert werden. (Warum dies unser Ziel ist, ist eine andere Frage. Nehmen wir dies einfach als die Herausforderung, die wir stellen ist gegeben.) Scheint unmöglich, nicht wahr? Lassen Sie uns als Beispiel Fakultät implementieren.

Nun, Schritt 1 ist zu sagen, dass wir dies leicht tun könnten, wenn wir ein wenig schummeln würden. Durch die Verwendung von Funktionen mit 2 Variablen und Zuweisung können wir zumindest vermeiden, die Zuweisung zum Einrichten der Rekursion zu verwenden.

// Here's the function that we want to recurse.
X = function (recurse, n) {
  if (0 == n)
    return 1;
  else
    return n * recurse(recurse, n - 1);
};

// This will get X to recurse.
Y = function (builder, n) {
  return builder(builder, n);
};

// Here it is in action.
Y(
  X,
  5
);

Nun wollen wir sehen, ob wir weniger schummeln können. Zunächst verwenden wir die Zuweisung, aber das müssen wir nicht. Wir können einfach X und Y inline schreiben.

// No assignment this time.
function (builder, n) {
  return builder(builder, n);
}(
  function (recurse, n) {
    if (0 == n)
      return 1;
    else
      return n * recurse(recurse, n - 1);
  },
  5
);

Wir verwenden jedoch Funktionen von 2 Variablen, um eine Funktion von 1 Variable zu erhalten. Können wir das beheben? Nun, ein schlauer Typ namens Haskell Curry hat einen tollen Trick. Wenn Sie gute Funktionen höherer Ordnung haben, brauchen Sie nur Funktionen mit einer Variablen. Der Beweis ist, dass Sie mit einer rein mechanischen Texttransformation wie folgt von Funktionen von 2 (oder mehr im Allgemeinen) Variablen zu 1 Variablen gelangen können:

// Original
F = function (i, j) {
  ...
};
F(i,j);

// Transformed
F = function (i) { return function (j) {
  ...
}};
F(i)(j);

wo ... bleibt genau das gleiche. (Dieser Trick wird nach seinem Erfinder "Currying" genannt. Die Sprache Haskell wird auch nach Haskell Curry benannt. Legen Sie das unter unnützen Umständen ab.) Wenden Sie diese Transformation jetzt einfach überall an und wir erhalten unsere endgültige Version.

// The dreaded Y-combinator in action!
function (builder) { return function (n) {
  return builder(builder)(n);
}}(
  function (recurse) { return function (n) {
    if (0 == n)
      return 1;
    else
      return n * recurse(recurse)(n - 1);
  }})(
  5
);

Fühlen Sie sich frei, es zu versuchen. alert (), die zurückkehren, binde es an einen Knopf, was auch immer. Dieser Code berechnet rekursiv Fakultäten, ohne Zuweisung, Deklaration oder Funktion von 2 Variablen. (Wenn Sie jedoch nachverfolgen, wie es funktioniert, dreht sich wahrscheinlich der Kopf. Wenn Sie es ohne die Ableitung nur geringfügig neu formatieren, wird der Code mit Sicherheit verwirrend und verwirrend.)

Sie können die 4 Zeilen, die rekursiv Fakultät definieren, durch eine beliebige andere rekursive Funktion ersetzen.

98
btilly

Ich frage mich, ob es Sinn macht, dies von Grund auf zu versuchen. Wir werden sehen. Hier ist eine grundlegende rekursive Fakultätsfunktion:

function factorial(n) {
    return n == 0 ? 1 : n * factorial(n - 1);
}

Lassen Sie uns eine neue Funktion namens fact umgestalten und erstellen, die eine anonyme Fakultätsberechnungsfunktion zurückgibt, anstatt die Berechnung selbst durchzuführen:

function fact() {
    return function(n) {
        return n == 0 ? 1 : n * fact()(n - 1);
    };
}

var factorial = fact();

Das ist ein bisschen komisch, aber daran ist nichts auszusetzen. Wir generieren nur bei jedem Schritt eine neue Fakultätsfunktion.

Die Rekursion ist zu diesem Zeitpunkt noch ziemlich eindeutig. Die Funktion fact muss ihren eigenen Namen kennen. Parametrisieren wir den rekursiven Aufruf:

function fact(recurse) {
    return function(n) {
        return n == 0 ? 1 : n * recurse(n - 1);
    };
}

function recurser(x) {
    return fact(recurser)(x);
}

var factorial = fact(recurser);

Das ist toll, aber recurser muss noch seinen eigenen Namen kennen. Lassen Sie uns das auch parametrisieren:

function recurser(f) {
    return fact(function(x) {
        return f(f)(x);
    });
}

var factorial = recurser(recurser);

Anstatt jetzt direkt recurser(recurser) aufzurufen, erstellen wir eine Wrapper-Funktion, die das Ergebnis zurückgibt:

function Y() {
    return (function(f) {
        return f(f);
    })(recurser);
}

var factorial = Y();

Wir können jetzt den Namen recurser insgesamt loswerden; Es ist nur ein Argument für die innere Funktion von Y, die durch die Funktion selbst ersetzt werden kann:

function Y() {
    return (function(f) {
        return f(f);
    })(function(f) {
        return fact(function(x) {
            return f(f)(x);
        });
    });
}

var factorial = Y();

Der einzige externe Name, auf den noch verwiesen wird, ist fact, aber es sollte inzwischen klar sein, dass dies auch leicht zu parametrisieren ist, um die vollständige, generische Lösung zu erstellen:

function Y(le) {
    return (function(f) {
        return f(f);
    })(function(f) {
        return le(function(x) {
            return f(f)(x);
        });
    });
}

var factorial = Y(function(recurse) {
    return function(n) {
        return n == 0 ? 1 : n * recurse(n - 1);
    };
});
80
Wayne Burkett

Die meisten der obigen Antworten beschreiben, was der Y-Kombinator ist , aber nicht, was er ist für .

Fixpunktkombinatoren werden verwendet, um zu zeigen, dass Lambda-KalkülTuring abgeschlossen ist. Dies ist ein sehr wichtiges Ergebnis in der Berechnungstheorie und liefert eine theoretische Grundlage für funktionale Programmierung .

Das Studium von Festkomma-Kombinatoren hat mir auch geholfen, die funktionale Programmierung wirklich zu verstehen. Ich habe jedoch nie eine Verwendung für sie in der tatsächlichen Programmierung gefunden.

48
Jørgen Fogh

y-Kombinator in JavaScript :

var Y = function(f) {
  return (function(g) {
    return g(g);
  })(function(h) {
    return function() {
      return f(h(h)).apply(null, arguments);
    };
  });
};

var factorial = Y(function(recurse) {
  return function(x) {
    return x == 0 ? 1 : x * recurse(x-1);
  };
});

factorial(5)  // -> 120

Edit : Ich lerne viel vom Betrachten von Code, aber dieser ist ohne Hintergrund ein bisschen schwer zu schlucken - tut mir leid. Mit einigen allgemeinen Kenntnissen, die durch andere Antworten vermittelt werden, können Sie beginnen, herauszufinden, was gerade passiert.

Die Y-Funktion ist der "y-Kombinator". Schauen Sie sich nun die Zeile var factorial An, in der Y verwendet wird. Beachten Sie, dass Sie eine Funktion übergeben, die einen Parameter hat (in diesem Beispiel recurse), der später auch in der inneren Funktion verwendet wird. Der Parametername wird im Grunde genommen zum Namen der inneren Funktion, die einen rekursiven Aufruf ausführen kann (da in ihrer Definition recurse() verwendet wird.) Der y-Kombinator führt die Magie aus, die ansonsten anonyme innere Funktion mit der zu verknüpfen Parametername der an Y übergebenen Funktion.

Für die vollständige Erklärung, wie Y die Magie macht, siehe verlinkter Artikel (übrigens nicht von mir)

23
Zach

Für Programmierer, die sich noch nicht mit funktionaler Programmierung befasst haben und jetzt nicht anfangen möchten, aber ein wenig neugierig sind:

Der Y-Kombinator ist eine Formel, mit der Sie eine Rekursion in Situationen implementieren können, in denen Funktionen keine Namen haben, sondern als Argumente übergeben, als Rückgabewerte verwendet und in anderen Funktionen definiert werden können.

Es funktioniert, indem es die Funktion als Argument an sich selbst übergibt, sodass es sich selbst aufrufen kann.

Es ist Teil der Lambda-Rechnung, die eigentlich Mathematik ist, aber effektiv eine Programmiersprache ist und für die Informatik und insbesondere für die funktionale Programmierung von grundlegender Bedeutung ist.

Der Alltagswert des Y-Kombinators ist begrenzt, da Sie in der Regel in Programmiersprachen Funktionen benennen können.

Falls Sie es in einer Polizeiaufstellung identifizieren müssen, sieht es so aus:

Y = λf (λx.f (xx)) (λx.f (xx))

Sie können es normalerweise aufgrund des wiederholten (λx.f (x x)) Erkennen.

Die λ - Symbole sind der griechische Buchstabe Lambda, der dem Lambda-Kalkül seinen Namen gibt, und es gibt viele (λx.t) - Stilbegriffe, da der Lambda-Kalkül so aussieht.

17
El Zorko

Andere Antworten liefern eine ziemlich knappe Antwort auf diese Frage, ohne eine wichtige Tatsache: Sie müssen den Festkomma-Kombinator in keiner praktischen Sprache auf diese verschlungene Weise implementieren, und dies hat keinen praktischen Zweck (außer "Schau, ich weiß, welcher Y-Kombinator") ist "). Es ist ein wichtiges theoretisches Konzept, das jedoch wenig praktischen Wert hat.

11
Ales Hakl

Hier ist eine JavaScript-Implementierung des Y-Combinators und der Factorial-Funktion (aus Douglas Crockfords Artikel, verfügbar unter: http://javascript.crockford.com/little.html ).

function Y(le) {
    return (function (f) {
        return f(f);
    }(function (f) {
        return le(function (x) {
            return f(f)(x);
        });
    }));
}

var factorial = Y(function (fac) {
    return function (n) {
        return n <= 2 ? n : n * fac(n - 1);
    };
});

var number120 = factorial(5);
6
xgMz

Ein Y-Kombinator ist ein anderer Name für einen Flusskondensator.

6
Jon Davis

Anonyme Rekursion

Ein Festkomma-Kombinator ist eine Funktion höherer Ordnung fix, die per Definition die Äquivalenz erfüllt

forall f.  fix f  =  f (fix f)

fix f steht für eine Lösung x der Festkommagleichung

               x  =  f x

Die Fakultät einer natürlichen Zahl kann durch bewiesen werden

fact 0 = 1
fact n = n * fact (n - 1)

Mit fix können beliebige konstruktive Beweise über allgemeine/μ-rekursive Funktionen ohne nicht-synonyme Selbstreferenzialität abgeleitet werden.

fact n = (fix fact') n

woher

fact' rec n = if n == 0
                then 1
                else n * rec (n - 1)

so dass

   fact 3
=  (fix fact') 3
=  fact' (fix fact') 3
=  if 3 == 0 then 1 else 3 * (fix fact') (3 - 1)
=  3 * (fix fact') 2
=  3 * fact' (fix fact') 2
=  3 * if 2 == 0 then 1 else 2 * (fix fact') (2 - 1)
=  3 * 2 * (fix fact') 1
=  3 * 2 * fact' (fix fact') 1
=  3 * 2 * if 1 == 0 then 1 else 1 * (fix fact') (1 - 1)
=  3 * 2 * 1 * (fix fact') 0
=  3 * 2 * 1 * fact' (fix fact') 0
=  3 * 2 * 1 * if 0 == 0 then 1 else 0 * (fix fact') (0 - 1)
=  3 * 2 * 1 * 1
=  6

Dieser formale Beweis, dass

fact 3  =  6

verwendet methodisch die Festkomma-Kombinator-Äquivalenz fürrewrites

fix fact'  ->  fact' (fix fact')

Lambda-Kalkül

Deruntypisierte Lambda-KalkülFormalismus besteht in einer kontextfreien Grammatik

E ::= v        Variable
   |  λ v. E   Abstraction
   |  E E      Application

wobei v zusammen mit den Regelnbetaundeta reductionüber Variablen liegt

(λ x. B) E  ->  B[x := E]                                 Beta
  λ x. E x  ->  E          if x doesn’t occur free in E   Eta

Die Beta-Reduktion ersetzt alle freien Vorkommen der Variablen x im Abstraktions „Funktions-“) body B durch den Ausdruck („Argument“) E. Eta-Reduktion eliminiert redundante Abstraktion. Es wird manchmal aus dem Formalismus weggelassen. EinirreduziblerAusdruck, für den keine Reduktionsregel gilt, befindet sich innormaloderkanonische Form.

λ x y. E

ist eine Abkürzung für

λ x. λ y. E

(Abstraktionsvielfalt),

E F G

ist eine Abkürzung für

(E F) G

(Linksassoziativität der Anwendung),

λ x. x

und

λ y. y

sindAlpha-Äquivalent.

Abstraktion und Anwendung sind die beiden einzigen „Sprachprimitive“ des Lambda-Kalküls, aber sie ermöglichen dieKodierungbeliebig komplexer Daten und Operationen.

Die Zahlen der Kirche sind eine Kodierung der natürlichen Zahlen, die den peano-axiomatischen Zahlen ähneln.

   0  =  λ f x. x                 No application
   1  =  λ f x. f x               One application
   2  =  λ f x. f (f x)           Twofold
   3  =  λ f x. f (f (f x))       Threefold
    . . .

SUCC  =  λ n f x. f (n f x)       Successor
 ADD  =  λ n m f x. n f (m f x)   Addition
MULT  =  λ n m f x. n (m f) x     Multiplication
    . . .

Ein formeller Beweis dafür

1 + 2  =  3

mit der Rewrite-Regel der Beta-Reduktion:

   ADD                      1            2
=  (λ n m f x. n f (m f x)) (λ g y. g y) (λ h z. h (h z))
=  (λ m f x. (λ g y. g y) f (m f x)) (λ h z. h (h z))
=  (λ m f x. (λ y. f y) (m f x)) (λ h z. h (h z))
=  (λ m f x. f (m f x)) (λ h z. h (h z))
=  λ f x. f ((λ h z. h (h z)) f x)
=  λ f x. f ((λ z. f (f z)) x)
=  λ f x. f (f (f x))                                       Normal form
=  3

Kombinatoren

In der Lambda-Rechnung sindcombinatorsAbstraktionen, die keine freien Variablen enthalten. Am einfachsten: I, der Identitätskombinator

λ x. x

isomorph zur Identitätsfunktion

id x = x

Solche Kombinatoren sind die primitiven Operatoren vonKombinatorkalkülenwie das SKI-System.

S  =  λ x y z. x z (y z)
K  =  λ x y. x
I  =  λ x. x

Beta-Reduktion ist nichtstark normalisierend; Nicht alle reduzierbaren Ausdrücke, "Redexes", konvergieren unter Beta-Reduktion zur normalen Form. Ein einfaches Beispiel ist die unterschiedliche Anwendung des Omega ω Kombinator

λ x. x x

zu sich selbst:

   (λ x. x x) (λ y. y y)
=  (λ y. y y) (λ y. y y)
. . .
=  _|_                     Bottom

Die Reduzierung der am weitesten links stehenden Unterausdrücke („Köpfe“) wird priorisiert.Anwendbare Reihenfolgenormalisiert Argumente vor der Ersetzung,normale Reihenfolgenicht. Die beiden Strategien sind analog zu einer eifrigen Bewertung, z. C und verzögerte Auswertung, z.B. Haskell.

   K          (I a)        (ω ω)
=  (λ k l. k) ((λ i. i) a) ((λ x. x x) (λ y. y y))

divergenzen bei eifriger Beta-Reduktion nach Anwendungsreihenfolge

=  (λ k l. k) a ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ y. y y) (λ y. y y))
. . .
=  _|_

seit instrictsemantics

forall f.  f _|_  =  _|_

aber konvergiert unter fauler Beta-Reduktion normaler Ordnung

=  (λ l. ((λ i. i) a)) ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ x. x x) (λ y. y y))
=  a

Wenn ein Ausdruck eine normale Form hat, wird er von der Beta-Reduktion normaler Ordnung gefunden.

Y.

Die wesentliche Eigenschaft des YFestkomma-Kombinators

λ f. (λ x. f (x x)) (λ x. f (x x))

ist gegeben durch

   Y g
=  (λ f. (λ x. f (x x)) (λ x. f (x x))) g
=  (λ x. g (x x)) (λ x. g (x x))           =  Y g
=  g ((λ x. g (x x)) (λ x. g (x x)))       =  g (Y g)
=  g (g ((λ x. g (x x)) (λ x. g (x x))))   =  g (g (Y g))
. . .                                      . . .

Die Äquivalenz

Y g  =  g (Y g)

ist isomorph zu

fix f  =  f (fix f)

Der untypisierte Lambda-Kalkül kann beliebige konstruktive Beweise über allgemeine/μ-rekursive Funktionen codieren.

 FACT  =  λ n. Y FACT' n
FACT'  =  λ rec n. if n == 0 then 1 else n * rec (n - 1)

   FACT 3
=  (λ n. Y FACT' n) 3
=  Y FACT' 3
=  FACT' (Y FACT') 3
=  if 3 == 0 then 1 else 3 * (Y FACT') (3 - 1)
=  3 * (Y FACT') (3 - 1)
=  3 * FACT' (Y FACT') 2
=  3 * if 2 == 0 then 1 else 2 * (Y FACT') (2 - 1)
=  3 * 2 * (Y FACT') 1
=  3 * 2 * FACT' (Y FACT') 1
=  3 * 2 * if 1 == 0 then 1 else 1 * (Y FACT') (1 - 1)
=  3 * 2 * 1 * (Y FACT') 0
=  3 * 2 * 1 * FACT' (Y FACT') 0
=  3 * 2 * 1 * if 0 == 0 then 1 else 0 * (Y FACT') (0 - 1)
=  3 * 2 * 1 * 1
=  6

(Multiplikation verzögert, Zusammenfluss)

Für die nicht typisierte Lambda-Rechnung der Kirche wurde gezeigt, dass es neben Y eine rekursiv aufzählbare Unendlichkeit von Festkomma-Kombinatoren gibt.

 X  =  λ f. (λ x. x x) (λ x. f (x x))
Y'  =  (λ x y. x y x) (λ y x. y (x y x))
 Z  =  λ f. (λ x. f (λ v. x x v)) (λ x. f (λ v. x x v))
 Θ  =  (λ x y. y (x x y)) (λ x y. y (x x y))
  . . .

Die Beta-Reduktion normaler Ordnung macht den nicht erweiterten, untypisierten Lambda-Kalkül zu einem Turing-vollständigen Umschreibungssystem.

In Haskell kann der Festkomma-Kombinator elegant implementiert werden

fix :: forall t. (t -> t) -> t
fix f = f (fix f)

Haskells Faulheit normalisiert sich zu einer Endlichkeit, bevor alle Unterausdrücke ausgewertet wurden.

primes :: Integral t => [t]
primes = sieve [2 ..]
   where
      sieve = fix (\ rec (p : ns) ->
                     p : rec [n | n <- ns
                                , n `rem` p /= 0])

6
user6428287

Ich habe sowohl in Clojure als auch in Scheme eine Art "Idiotenführer" für den Y-Kombinator geschrieben, um mich damit zurechtzufinden. Sie sind beeinflusst von Material in "The Little Schemer"

Im Schema: https://Gist.github.com/z5h/238891

oder Clojure: https://Gist.github.com/z5h/5102747

Beide Tutorials sind Code mit Kommentaren durchsetzt und sollten in Ihren bevorzugten Editor geschnitten und eingefügt werden können.

5
z5h

Der y-Kombinator implementiert eine anonyme Rekursion. Also statt

function fib( n ){ if( n<=1 ) return n; else return fib(n-1)+fib(n-2) }

du kannst tun

function ( fib, n ){ if( n<=1 ) return n; else return fib(n-1)+fib(n-2) }

natürlich funktioniert der y-combinator nur in call-by-name sprachen. Wenn Sie dies in einer normalen Call-by-Value-Sprache verwenden möchten, benötigen Sie den zugehörigen Z-Kombinator (Y-Kombinator läuft auseinander/Endlosschleife).

4
Andrew

Als Neuling bei Kombinatoren fand ich Mike Vaniers Artikel (danke Nicholas Mancuso) sehr hilfreich. Ich würde gerne eine Zusammenfassung schreiben, neben der Dokumentation meines Verständnisses, wenn es für einige andere hilfreich sein könnte, würde ich mich sehr freuen.

Von Crappy bis Less Crappy

Am Beispiel der Fakultät verwenden wir die folgende Funktion almost-factorial, Um die Fakultät der Zahl x zu berechnen:

def almost-factorial f x = if iszero x
                           then 1
                           else * x (f (- x 1))

Im obigen Pseudocode übernimmt almost-factorial Die Funktion f und die Nummer x (almost-factorial Wird als Funktion f und Rückgabe einer 1-Arity-Funktion).

Wenn almost-factorial Die Fakultät für x berechnet, delegiert es die Berechnung der Fakultät für x - 1 An die Funktion f und summiert dieses Ergebnis mit x ( in diesem Fall multipliziert es das Ergebnis von (x - 1) mit x).

Es kann so gesehen werden, dass almost-factorial Eine crappy Version der Fakultätsfunktion (die nur bis zur Zahl x - 1 Berechnen kann) annimmt und ein less zurückgibt -crappy Fakultätsversion (berechnet die Kassenanzahl x). Wie in dieser Form:

almost-factorial crappy-f = less-crappy-f

Wenn wir wiederholt die less-crappy Version von Fakultät an almost-factorial Übergeben, erhalten wir schließlich unsere gewünschte Fakultätsfunktion f. Wo kann es betrachtet werden als:

almost-factorial f = f

Fixpunkt

Die Tatsache, dass almost-factorial f = ff bedeutet, ist der Fixpunkt der Funktion almost-factorial.

Dies war eine wirklich interessante Art, die Beziehungen der oben genannten Funktionen zu sehen, und es war ein Aha-Moment für mich. (Bitte lies Mikes Beitrag über den Fixpunkt, wenn du ihn nicht hast.)

Drei Funktionen

Zur Verallgemeinerung haben wir eine nicht-rekursive Funktion fn (wie unsere fast Fakultät), wir haben ihre Fixpunkt Funktion fr (wie unser f), dann macht Y, wenn Sie Yfn, Y gibt die Fixpunktfunktion von fn zurück.

Zusammenfassend (vereinfacht durch die Annahme, dass fr nur einen Parameter annimmt; x degeneriert zu x - 1, x - 2 ... in Rekursion):

  • Wir definieren die Kernberechnungen als fn: def fn fr x = ...accumulate x with result from (fr (- x 1)), dies ist die fast nützlich Funktion - obwohl wir nicht fn direkt auf x, wird es sehr bald nützlich sein. Dieses nicht-rekursive fn verwendet eine Funktion fr, um das Ergebnis zu berechnen
  • fn fr = fr, fr ist der Fixpunkt von fn, fr ist die nützlich Funktion, die wir mit fr auf x bekommen können unser ergebnis
  • Y fn = fr, Y gibt den Fixpunkt einer Funktion zurück, Y verwandelt unsere fast nützlich Funktion fn in nützlichfr

Ableitung Y (nicht enthalten)

Ich werde die Herleitung von Y überspringen und zum Verständnis von Y übergehen. Mike Vainers Beitrag enthält viele Details.

Die Form von Y

Y ist definiert als (im Lambda-Kalkül Format):

Y f = λs.(f (s s)) λs.(f (s s))

Wenn wir die Variable s links von den Funktionen ersetzen, erhalten wir

Y f = λs.(f (s s)) λs.(f (s s))
=> f (λs.(f (s s)) λs.(f (s s)))
=> f (Y f)

In der Tat ist das Ergebnis von (Y f) Der Fixpunkt von f.

Warum funktioniert (Y f)?

Abhängig von der Signatur von f kann (Y f) Eine Funktion beliebiger Art sein. Nehmen wir zur Vereinfachung an, dass (Y f) Nur einen Parameter verwendet, wie unsere Fakultätsfunktion.

def fn fr x = accumulate x (fr (- x 1))

seit fn fr = fr fahren wir fort

=> accumulate x (fn fr (- x 1))
=> accumulate x (accumulate (- x 1) (fr (- x 2)))
=> accumulate x (accumulate (- x 1) (accumulate (- x 2) ... (fn fr 1)))

die rekursive Berechnung wird beendet, wenn der innerste (fn fr 1) der Basisfall ist und fn nicht fr in der Berechnung verwendet.

Schauen Sie sich noch einmal Y an:

fr = Y fn = λs.(fn (s s)) λs.(fn (s s))
=> fn (λs.(fn (s s)) λs.(fn (s s)))

So

fr x = Y fn x = fn (λs.(fn (s s)) λs.(fn (s s))) x

Für mich sind die magischen Teile dieses Setups:

  • fn und fr hängen voneinander ab: fr 'umhüllt' fn jedes Mal, wenn fr zur Berechnung von x, es 'erzeugt' ('hebt'?) Eine fn und delegiert die Berechnung an diese fn (in sich übergebend fr und x ); Andererseits hängt fn von fr ab und berechnet mit fr das Ergebnis eines kleineren Problems x-1.
  • Zum Zeitpunkt, an dem fr zum Definieren von fn verwendet wird (wenn fnfr in seinen Operationen verwendet), ist das echte fr noch nicht vorhanden definiert.
  • Es ist fn, das die eigentliche Geschäftslogik definiert. Basierend auf fn erstellt Yfr - eine Hilfsfunktion in einer bestimmten Form - um die Berechnung für fn in einem rekursiven Weise.

Es hat mir geholfen, Y im Moment so zu verstehen, hoffe es hilft.

Übrigens fand ich auch das Buch Eine Einführung in die funktionale Programmierung durch Lambda-Berechnung sehr gut, ich bin nur ein Teil davon und die Tatsache, dass ich mich nicht zurechtfinden konnte Y in dem Buch führte mich zu diesem Beitrag.

4
Dapeng Li

Hier finden Sie Antworten auf die Originalfragen , zusammengestellt aus dem Artikel (der VOLLSTÄNDIG lesenswert ist), die auch in Antwort von Nicholas Mancuso erwähnt werden als andere Antworten:

Was ist ein Y-Kombinator?

Ein Y-Kombinator ist eine "Funktion" (oder eine Funktion höherer Ordnung - eine Funktion, die auf andere Funktionen angewendet wird), die ein einzelnes Argument verwendet, eine Funktion, die nicht rekursiv ist, und eine Version der Funktion zurückgibt, die ist rekursiv.


Etwas rekursiv =), aber genauere Definition:

Ein Kombinator - ist nur ein Lambda-Ausdruck ohne freie Variablen.
Freie Variable - ist eine Variable, die keine gebundene Variable ist.
Gebundene Variable - Variable, die im Körper eines Lambda-Ausdrucks enthalten ist, dessen Argument der Variablenname ist.

Eine andere Möglichkeit, dies zu betrachten, besteht darin, dass der Kombinator ein solcher Lambda-Ausdruck ist, in dem Sie den Namen eines Kombinators durch seine Definition ersetzen können, wo immer er gefunden wird und alles noch funktioniert (Sie werden in eine Endlosschleife geraten, wenn der Kombinator dies tun würde Verweis auf sich selbst im Lambda-Körper enthalten).

Der Y-Kombinator ist ein Festkomma-Kombinator.

Ein fester Punkt einer Funktion ist ein Element der Funktionsdomäne, das von der Funktion auf sich selbst abgebildet wird.
Das heißt, c ist ein fester Punkt der Funktion f(x) if f(c) = c
Dies bedeutet f(f(...f(c)...)) = fn(c) = c

Wie arbeiten Kombinatoren?

Die folgenden Beispiele setzen starke + dynamische Eingabe voraus:

Fauler (normaler) Y-Kombinator:
Diese Definition gilt für Sprachen mit verzögerter (auch: verzögerter, bedarfsabhängiger) Bewertung - Bewertungsstrategie, die die Bewertung eines Ausdrucks verzögert, bis sein Wert benötigt wird.

Y = λf.(λx.f(x x)) (λx.f(x x)) = λf.(λx.(x x)) (λx.f(x x))

Dies bedeutet, dass für eine gegebene Funktion f (die eine nicht rekursive Funktion ist) die entsprechende rekursive Funktion zuerst durch Berechnen von λx.f(x x) und dann Anwenden dieses Lambda-Ausdrucks erhalten werden kann zu sich selbst.

Strenger (anwendungsorientierter) Y-Kombinator:
Diese Definition gilt für Sprachen mit strenger (auch: eifriger, gieriger) Bewertung - Bewertungsstrategie, bei der ein Ausdruck bewertet wird, sobald er an eine Variable gebunden ist.

Y = λf.(λx.f(λy.((x x) y))) (λx.f(λy.((x x) y))) = λf.(λx.(x x)) (λx.f(λy.((x x) y)))

Es ist dasselbe wie bei einem Faulen in seiner Natur, es hat nur eine zusätzliche λ Hülle, um die Körperbewertung des Lambda zu verzögern. Ich habe eine andere Frage gestellt, etwas im Zusammenhang mit diesem Thema.

Wofür sind sie gut?

Gestohlen entlehnt von Antwort von Chris Ammerman: Y-combinator verallgemeinert die Rekursion, abstrahiert ihre Implementierung und trennt sie dadurch von der eigentlichen Arbeit der fraglichen Funktion.

Obwohl Y-combinator einige praktische Anwendungen hat, handelt es sich hauptsächlich um ein theoretisches Konzept, dessen Verständnis Ihre Gesamtvision erweitert und wahrscheinlich Ihre Analyse- und Entwicklerfähigkeiten verbessert.

Sind sie in Verfahrenssprachen nützlich?

Wie von Mike Vanier angegeben : ist es möglich, einen Y-Kombinator in vielen statisch typisierten Sprachen zu definieren, aber (zumindest in den Beispielen, die ich gesehen habe) ) Für solche Definitionen ist normalerweise ein nicht offensichtlicher Typhacker erforderlich, da der Y-Kombinator selbst keinen einfachen statischen Typ hat. Das würde den Rahmen dieses Artikels sprengen, deshalb werde ich es nicht weiter erwähnen

Und wie von Chris Ammerman erwähnt : Die meisten prozeduralen Sprachen haben statische Typisierung.

Also antworte auf diese Frage - nicht wirklich.

4
Filipp W.

Der this-Operator kann Ihr Leben vereinfachen:

var Y = function(f) {
    return (function(g) {
        return g(g);
    })(function(h) {
        return function() {
            return f.apply(h(h), arguments);
        };
    });
};

Dann vermeiden Sie die Zusatzfunktion:

var fac = Y(function(n) {
    return n == 0 ? 1 : n * this(n - 1);
});

Schließlich rufen Sie fac(5) auf.

3
Tires

Ein Festkomma-Kombinator (oder Festkomma-Operator) ist eine Funktion höherer Ordnung, die einen Festpunkt aus anderen Funktionen berechnet. Diese Operation ist in der Programmiersprachtheorie relevant, da sie die Implementierung einer Rekursion in Form einer Umschreiberegel ohne ausdrückliche Unterstützung durch die Laufzeit-Engine der Sprache ermöglicht. (src Wikipedia)

3
Thomas Wagner

Ich denke, der beste Weg, dies zu beantworten, ist die Auswahl einer Sprache wie JavaScript:

function factorial(num)
{
    // If the number is less than 0, reject it.
    if (num < 0) {
        return -1;
    }
    // If the number is 0, its factorial is 1.
    else if (num == 0) {
        return 1;
    }
    // Otherwise, call this recursive procedure again.
    else {
        return (num * factorial(num - 1));
    }
}

Schreiben Sie es jetzt so um, dass es nicht den Namen der Funktion innerhalb der Funktion verwendet, sondern immer noch rekursiv aufruft.

Der einzige Ort, an dem der Funktionsname factorial angezeigt werden sollte, ist an der Aufrufstelle.

Hinweis: Sie können keine Funktionsnamen verwenden, aber Sie können Parameternamen verwenden.

Arbeite das Problem. Schau nicht nach. Sobald Sie es gelöst haben, werden Sie verstehen, welches Problem der y-combinator löst.

0
zumalifeguard