Was ist ein Y-Kombinator?[geschlossen]

StackOverflow https://stackoverflow.com/questions/93526

Frage

Ein Y-Kombinator ist ein Informatikkonzept aus „funktionaler“ Sicht.Die meisten Programmierer wissen überhaupt nicht viel über Kombinatoren, wenn sie überhaupt davon gehört haben.

  • Was ist ein Y-Kombinator?
  • Wie funktionieren Kombinatoren?
  • Wofür sind sie gut?
  • Sind sie in prozeduralen Sprachen nützlich?
War es hilfreich?

Lösung

Wenn Sie für eine lange Lese bereit sind, Mike Vanier hat eine groß Erklärung . Lange Rede kurzer Sinn, ermöglicht es Ihnen Rekursion in einer Sprache zu implementieren, die nicht unbedingt nativ unterstützen.

Andere Tipps

Ein Y-Combinator ist eine „funktionelle“ (eine Funktion, die auf anderen Funktionen arbeitet), die Rekursion ermöglicht, wenn Sie nicht auf die Funktion aus mich selbst beziehen. In Computer-Wissenschaft Theorie, es verallgemeinert Rekursion , deren Umsetzung zu abstrahieren, und damit es von der eigentlichen Arbeit der Funktion in Frage zu trennen. Der Vorteil der nicht einen Compiler-Namen für die rekursive Funktion benötigen, ist eine Art Bonus. =)

Dies gilt in Sprachen, die Lambda-Funktionen . Die Ausdruck -basierte Natur lambda bedeutet in der Regel, dass sie nicht selbst mit Namen verweisen können. Und um diese Arbeit durch die Variable deklarieren, was sich auf sie, dann die Lambda es zuweisen, die Selbstreferenz Schleife zu vervollständigen, ist brüchig. Das Lambda-Variable kopiert werden kann, und der ursprüngliche Variable Wieder zugewiesen, was die Selbstreferenz bricht.

Y-Kombinatoren sind umständlich zu implementieren, und oft zu verwenden, statisch typisierte Sprachen, da in der Regel die Eingabe Einschränkungen erfordern die Anzahl der Argumente für das (die href="http://en.wikipedia.org/wiki/Procedural_programming" rel="noreferrer"> Verfahrenssprachen oft

Im Folgenden ist ein Beispiel dafür, wie die Nutzung und die Arbeit eines Y-Combinator, in C #.

ein Y-Combinator Verwendung beinhaltet eine „ungewöhnliche“ Art und Weise eine rekursive Funktion zu konstruieren. Zunächst müssen Sie Ihre Funktion als ein Stück Code schreiben, die eine bereits bestehende Funktion aufruft, anstatt selbst: 

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

Sie dann wiederum, dass in eine Funktion, die eine Funktion aufzurufen nimmt und gibt eine Funktion, die so tut. Dies ist eine funktionale genannt, weil sie eine Funktion übernimmt, und führt eine Operation damit, dass in 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 gibt eine weitere Funktion, die wie eine Art faktorielles aussieht, sondern sich selbst zu nennen, ruft das Argument in die äußere Funktion übergeben. Wie machen Sie das die Fakultät? Passiert die innere Funktion selbst. Der Y-Combinator das tut, durch eine Funktion mit einem dauerhaften Namen zu sein, die die Rekursion einführen können. 

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

Anstatt die Fakultäts selbst nennen, was passiert ist, dass der Fakultäts den Fakultäts Generator ruft (durch den rekursiven Aufruf an Y-Combinator zurückgegeben). Und je nach dem aktuellen Wert von t die Funktion vom Generator zurückgeführt wird entweder wieder den Generator rufen, mit t -. 1, oder nur 1 zurückzukehren, die Rekursion beendet

Es ist kompliziert und kryptisch, aber es ist alles schüttelt zur Laufzeit aus, und der Schlüssel zu seiner Arbeits ist „deferred execution“, und die aus der Rekursion brechen zwei Funktionen zu überbrücken. Die innere F als Argument übergibt , in der nächsten Iteration aufgerufen werden, nur bei Bedarf .

Ich habe hob diese von http: //www.mail-archive .com / boston-pm @ mail.pm.org / msg02716.html , die eine Erklärung, die ich vor einigen Jahren geschrieben haben.

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

Unser Ziel ist es, eine rekursive Funktion von 1 schreiben Variable nur Funktionen von 1 Variablen und keine Zuweisungen, die Dinge beim Namen zu definieren usw. (Warum dies ist unser Ziel ist eine andere Frage, nehmen wir nur das als die Herausforderung, die uns gegeben sind.) Es scheint unmöglich, nicht wahr? Wie ein Beispiel nehmen wir factorial implementieren.

Nun Schritt 1 ist zu sagen, dass wir dies leicht tun könnten, wenn wir ein wenig betrogen. Mit Funktionen von 2 Variablen und Zuordnung können wir zumindest vermeiden verwenden Zuordnung der Rekursion einzurichten. 

// 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 betrügen können. Nun erstens wir verwenden Zuordnung, aber wir müssen nicht. Wir können nur X schreiben und Y inline. 

// 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
);

Aber wir sind mit den Funktionen von zwei Variablen, die eine Funktion von 1 zu erhalten Variable. Können wir das Problem lösen? Nun ein intelligenter Kerl mit Namen Haskell Curry hat einen ordentlichen Trick, wenn Sie eine gute höherer Ordnung Funktionen, dann müssen Sie nur Funktionen von 1 Variable. Das Beweis dafür ist, dass Sie von Funktionen von 2 (oder mehr in die bekommen allgemeiner Fall) Variablen 1 Variable mit einem rein mechanische Text Transformation wie folgt aus: 

// 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 aufgerufen „Currying“ nach seinem Erfinder. Die Sprache Haskell ist auch für Haskell Curry benannt. Datei, die unter nutzlos Nebensächlichkeiten.) Jetzt gelten nur diese Transformation überall und wir bekommen 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. (Alarm), die zurückkehren, binden Sie es auf eine Schaltfläche, was auch immer. Dieser Code berechnet factorials, rekursiv, ohne Verwendung von Zuweisung, Erklärungen oder Funktionen von 2 Variablen. (Aber nachzuzeichnen versucht, wie es funktioniert, ist wahrscheinlich den Kopf drehen machen. Und es, ohne die Ableitung geben, nur leicht umformatiert wird in Code zur Folge haben, die verblüffen sicher ist und zu verwirren.)

Sie können die 4 Zeilen ersetzen, die rekursiv faktorielles definieren mit andere rekursive Funktion, die Sie wollen.

Ich frage mich, ob es irgendeine Verwendung bei dem Versuch, das von Grund auf neu zu bauen. Mal sehen. Hier ist eine grundlegende, rekursive Fakultäts-Funktion: 

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

Lassen Sie sich Refactoring und eine neue Funktion namens fact erstellen, die eine anonyme faktorielles-Computing-Funktion gibt, anstatt die Berechnung der Durchführung selbst: 

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

var factorial = fact();

Das ist ein wenig seltsam, aber es ist nichts falsch mit ihm. Wir erzeugen, gerade eine neue Fakultäts-Funktion bei jedem Schritt.

Die Rekursion in diesem Stadium ist noch ziemlich eindeutig. Die fact Funktion muss sich seiner eigenen Namen. Lassen Sie uns den rekursiven Aufruf parametrieren: 

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 parametrieren, dass auch: 

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

var factorial = recurser(recurser);

Nun, statt des Aufrufs recurser(recurser) direkt, lassen Sie uns eine Wrapper-Funktion erstellen, die das Ergebnis zurückgibt: 

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

var factorial = Y();

Wir können nun von dem recurser Namen ganz loszuwerden; es ist nur ein Argument für Y Innen-Funktion, die mit der Funktion ersetzt werden kann, selbst: 

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 noch referenziert ist fact, aber es sollte inzwischen klar sein, dass das ist, auf einfachste Weise parametriert, auch die kompletten, 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);
    };
});

Die meisten Antworten oben beschreiben, was der Y-Combinator ist , aber nicht, was es ist für .

Festpunkt combinators verwendet werden, die Lambda-Kalkül ist turing komplette . Dies ist ein sehr wichtiges Ergebnis in der Theorie der Berechnung und bietet eine theoretische Grundlage für funktionale Programmierung .

Studieren Fixpunkt combinators hat auch dazu beigetragen, mich wirklich funktionale Programmierung verstehen. Ich habe gefunden, nie Verwendung für sie in der tatsächlichen Programmierung though.

y-combinator 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

Bearbeiten : Ich lerne viel von im Code suchen, aber dies ist ein bisschen hart ist ohne einige Hintergrundinformationen zu schlucken - leid. Mit etwas Allgemeinwissen von anderen Antworten präsentiert, können Sie auseinander zu nehmen beginnen, was geschieht.

Die Y-Funktion ist der "y-Kombinator". Nun nehmen Sie einen Blick auf die var factorial Linie, wo Y verwendet wird. Beachten Sie eine Funktion, um es passieren, die einen Parameter (in diesem Beispiel recurse) hat, die auch später in der inneren Funktion verwendet wird. Der Parametername wird im Grunde genommen der Name der inneren Funktion ermöglicht es einen rekursiven Aufruf durchzuführen (da es recurse() in seiner Definition verwendet.) Der y-Kombinator die Magie führt mit dem Parameternamen der Funktion der ansonsten anonym innere Funktion des Zuordnens weitergegeben Y.

Für die vollständige Erklärung, wie Y die Magie der Fall ist, überprüft, um die verlinkten Artikel (nicht von mir btw.)

Für Programmierer, die nicht der funktionalen Programmierung in die Tiefe gestoßen sind, und kümmern sich nicht, jetzt zu beginnen, sind aber leicht neugierig:

Die Y Combinator ist eine Formel, die Sie Rekursion in einer Situation implementieren können, wo Funktionen keine Namen haben kann, sondern um als Argumente, als Rückgabewerte verwendet geben werden, und definiert in anderen Funktionen.

Es funktioniert durch die Funktion selbst als Argument übergeben, so kann es selbst nennen.

Es ist ein Teil des Lambda-Kalkül, die wirklich Mathematik ist aber effektiv eine Programmiersprache und ist ziemlich grundlegend für Informatik und insbesondere der funktionalen Programmierung.

Der Tag zu Tag praktischen Wert des Y-Combinator ist begrenzt, da Programmiersprachen Sie neigen dazu, Funktionen benennen zu lassen.

Falls Sie es in einer Polizei Formation identifizieren müssen, sieht es wie folgt aus:

  

Y = & lambda; f. (Λx.f (x x)) (λx.f (x x))

Sie können es in der Regel vor Ort wegen der wiederholten (λx.f (x x)).

Die λ Symbole sind die griechischen Buchstaben Lambda, der die Lambda-Kalkül seinen Namen gibt, und es gibt eine Menge von Begriffen (λx.t) Stil, weil das ist, was die Lambda-Kalkül aussieht.

Andere Antworten geben ziemlich kurze Antwort auf diese Frage, ohne eine wichtige Tatsache: Sie brauchen keine festen Punkt combinator in jeder praktischen Sprache in diesem gewundenen Weg zu implementieren und dienen dabei keinen praktischen Zweck (mit Ausnahme von „aussieht, weiß ich, was Y-Kombinator ist "). Es ist wichtig, theoretisches Konzept, aber wenig praktischen Wert.

Hier ist eine JavaScript-Implementierung des Y-Combinator und die Funktion Factorial (von Douglas Crockford Artikeln, abrufbar 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);

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

Ich habe eine Art „Idiot Guide“ auf den Y-Combinator sowohl in Clojure und Schema geschrieben, um mich damit in dem Griff zu helfen kommen. Sie werden von Material in "The Little Schemer"

beeinflusst

In Schema: https://gist.github.com/z5h/238891

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

Beide Tutorials Code eingefügt mit Kommentaren und geschnitten werden sollte & verpastbarem in Ihrem bevorzugten Editor.

Anonyme Rekursion

Ein Festkommakombinator ist eine Funktion höherer Ordnung fix das erfüllt per Definition die Äquivalenz

forall f.  fix f  =  f (fix f)

fix f stellt eine Lösung dar x zur Fixpunktgleichung

               x  =  f x

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

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

Benutzen fix, können beliebige konstruktive Beweise über allgemeine/μ-rekursive Funktionen ohne anonyme Selbstreferenzialität abgeleitet werden.

fact n = (fix fact') n

Wo

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 dafür

fact 3  =  6

Verwendet methodisch die Festkomma-Kombinator-Äquivalenz für schreibt um

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

Lambda-Kalkül

Der untypisierter Lambda-Kalkül Der Formalismus besteht in einer kontextfreien Grammatik

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

Wo v Bereiche über Variablen, zusammen mit dem Beta Und Eta-Reduktion Regeln

(λ 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 Abstraktionskörper („Funktion“) B durch den Ausdruck („Argument“) E.Die Eta-Reduktion eliminiert redundante Abstraktion.Manchmal wird es im Formalismus weggelassen.Ein irreduzibel Ausdruck, für den keine Reduktionsregel gilt, ist in normal oder kanonische Form.

λ x y. E

ist eine Abkürzung für

λ x. λ y. E

(Abstraktion Multiarität),

E F G

ist eine Abkürzung für

(E F) G

(Anwendung Linksassoziativität),

λ x. x

Und

λ y. y

Sind Alpha-Äquivalent.

Abstraktion und Anwendung sind die beiden einzigen „Sprachprimitiven“ des Lambda-Kalküls, aber sie erlauben Codierung beliebig komplexer Daten und Operationen.

Die Kirchenzahlen sind eine Kodierung der natürlichen Zahlen, ähnlich den Peano-axiomatischen Naturzahlen.

   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

unter Verwendung 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 gilt: Kombinatoren sind Abstraktionen, 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 von Kombinatorrechnungen wie das SKI-System.

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

Beta-Reduktion ist nicht der Fall stark normalisierend;Nicht alle reduzierbaren Ausdrücke, „Redexe“, konvergieren unter Betareduktion zur Normalform.Ein einfaches Beispiel ist die divergente 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“) hat Priorität. Anwendbare Reihenfolge normalisiert Argumente vor der Substitution, normale Reihenfolge nicht.Die beiden Strategien sind analog zur eifrigen Bewertung, z.B.C und verzögerte Auswertung, z.B.Haskell.

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

divergiert unter eifriger Beta-Reduktion in applikativer Reihenfolge

=  (λ 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 in strikt Semantik

forall f.  f _|_  =  _|_

konvergiert aber unter Lazy-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 Normalform hat, wird er durch die Betareduktion normaler Ordnung gefunden.

Y

Die wesentliche Eigenschaft der Y Festkomma-Kombinator

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

 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, Konfluenz)

Für die untypisierte Lambda-Rechnung nach Churchian wurde außerdem gezeigt, dass es eine rekursiv aufzählbare Unendlichkeit von Festkomma-Kombinatoren gibt Y.

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

In Haskell lässt sich der Festkomma-Kombinator elegant implementieren

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

Haskells Faulheit normalisiert sich auf eine 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])

Der Y-Combinator implementiert anonyme Rekursion. So anstelle von 

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

Sie tun können, 

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

natürlich der y-combinator funktioniert nur im Call-by-Namen Sprachen. Wenn Sie dies in jeder normalen Call-by-Wert Sprache verwenden möchten, dann müssen Sie die zugehörigen z-combinator (y-combinator divergieren / unendlich-Schleife).

Als Neuling auf combinators, fand ich Mike Vanier der Artikel (Dank Nicholas Mancuso) zu wirklich hilfreich sein. Ich möchte eine Zusammenfassung schreiben, außer meinem Verständnis zu dokumentieren, wenn es von Hilfe sein könnte einige andere ich sehr froh sein würde.

Von Crappy Weniger Crappy

Mit faktorielles als Beispiel verwenden wir die folgende almost-factorial Funktion factorial die Nummer x zu berechnen: 

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

In dem obigen Pseudocode nimmt almost-factorial in Funktion f und Anzahl x (almost-factorial curried ist, so kann es als Einnahme in Funktion f und Zurückgeben eine 1-arity Funktion gesehen werden).

Wenn almost-factorial faktorielles für x berechnet, delegiert die Berechnung der Fakultät für x - 1 f funktionieren und reichert sich dieses Ergebnis mit x (in diesem Fall ist es multipliziert das Ergebnis von (x - 1) mit x).

Es ist zu sehen, wie almost-factorial nimmt in einer bescheißt Version von Fakultäts-Funktion (die nur bis Nummer x - 1 berechnen kann) und gibt eine weniger beschissen Version von faktoriellen ( die berechnet werden bis Nummer x). Wie es in dieser Form: 

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

Wenn wir passieren immer wieder die weniger beschissen Version von Fakultäts almost-factorial, werden wir schließlich unsere gewünschten Fakultäts-Funktion f erhalten. Wo es kann als in Betracht gezogen werden: 

almost-factorial f = f

Fix-Punkt

Die Tatsache, dass almost-factorial f = f bedeutet f ist der Fix-Punkt der Funktion almost-factorial.

Das war eine sehr interessante Art und Weise die Beziehungen der oben genannten Funktionen des Sehens und es war für mich ein Aha-Erlebnis. (Bitte Mike Beitrag auf Fix-Punkt lesen, wenn Sie nicht haben)

Drei Funktionen

Zur Verallgemeinerung, haben wir eine nicht-rekursive Funktion fn (wie unsere fast-Fakultät), haben wir seine Fix-Punkt Funktion fr (wie unsere f), dann, was Y tut, wenn Sie Y fn geben, Y gibt die Fix-Punkt-Funktion von fn.

So in der Zusammenfassung (vereinfachte durch fr unter der Annahme, nur einen Parameter, x x - 1 degeneriert, x - 2 ... in Rekursion):

  • Wir definieren die Kern Berechnungen fn : def fn fr x = ...accumulate x with result from (fr (- x 1)), ist dies die fast nützlich Funktion - obwohl wir können nicht direkt auf fn verwenden x, wird es sehr bald nützlich sein. Dieser nicht-rekursive fn verwendet eine Funktion fr ihr Ergebnis zu berechnen
  • fn fr = fr, fr ist der Fixpunkt von fn, fr ist die nützlich funciton, können wir fr auf x benutzen Sie unser Ergebnis
  • Y fn = fr, Y gibt den Fix-Punkt einer Funktion, Y dreht sich unsere fast nützlich Funktion fn in nützlich fr

Die Ableitung Y (nicht enthalten)

Ich werde die Ableitung von Y überspringen und zum Verständnis Y gehen. Mike Vainer der Post hat viele Details.

Die Form der Y

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

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

Wenn wir die Variable s in der linken Seite der 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)

So in der Tat, the Ergebnis (Y f) ist der Fix-Punkt von f.

Warum (Y f) Arbeit?

die Unterschrift von f Je nach (Y f) kann eine Funktion von jedem arity sein, zu vereinfachen, nehmen wir an, (Y f) nimmt nur einen Parameter, wie unsere Fakultätsfunktion. 

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

da fn fr = fr wir weiter 

=> 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 endet, wenn die am weitesten innen (fn fr 1) die Fallbasis ist und fn fr bei der Berechnung nicht verwendet werden.

Mit Blick auf Y wieder: 

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 dieser Einrichtung sind:

  • fn und fr wechselseitigen Abhängigkeiten voneinander: (? ‚Aufzüge‘) fr ‚Wraps‘ fn nach innen, wird jedes Mal fr verwendet x zu berechnen, ist es Spawns 'eine fn und delegiert die Berechnung dieser fn (vorbei an sich fr und x); auf der anderen Seite hängt fn auf fr und verwendet fr Ergebnis eines kleineren Problem x-1 zu berechnen.
  • Zu der Zeit fr verwendet fn zu definieren (wenn fn fr in seinen Operationen verwendet) wird der reale fr noch nicht definiert.
  • Es ist fn die die eigentliche Business-Logik definiert. Basierend auf fn schafft Y fr - eine Hilfsfunktion in einer bestimmten Form - die Berechnung für fn in eine rekursive Art und Weise zu erleichtern
    • .

Es half mir Y auf diese Weise im Moment zu verstehen, hofft, dass es hilft.

BTW, fand ich auch das Buch Eine Einführung in die funktionale Programmierung Durch Lambda-Kalkül sehr gut, ich bin nur durch sie und die Tatsache, Teil, dass ich nicht meinen Kopf um Y im Buch führte mich zu diesem Post bekommen.

Hier finden Sie Antworten auf die ursprünglichen Fragen , zusammengestellt von Antwort erwähnt von Nicholas Mancuso sowie anderen Antworten:

  

Was ist ein Y-Combinator?

Ein Y-Kombinator ist ein „funktionelles“ (oder eine Funktion höherer Ordnung - eine Funktion, die auf anderen Funktionen arbeitet), die ein einziges Argument annimmt, die eine Funktion ist, die nicht rekursiv ist, und gibt eine Version der Funktion, die rekursiv ist.

Etwas rekursive =), aber weitergehende Definition:

Ein combinator - ist nur ein Lambda-Ausdruck ohne freie Variablen.
Variable - ist eine Variable, die nicht eine gebundene Variable ist.
Bound Variable - Variable, die im Inneren des Körpers eines Lambda-Ausdruck enthalten ist, die die Variablennamen als eines seiner Argumente hat

.

Eine andere Möglichkeit, um darüber nachzudenken, ist, dass combinator ist so ein Lambda-Ausdruck, in dem Sie in der Lage, den Namen eines combinator mit seiner Definition ersetzen überall gefunden und haben alles, was noch arbeiten (Sie werden eine Endlosschleife geraten in wenn combinator würde Bezug auf sich selbst, innerhalb der Lambda-Körper enthalten).

Y-Kombinator ist ein Fixpunkt-Kombinator.

Festpunkt einer Funktion ist ein Element der Domäne der Funktion, die durch die Funktion selbst abgebildet wird.
Das heißt, ist c ein Fixpunkt der Funktion f(x) wenn f(c) = c
Das bedeutet f(f(...f(c)...)) = fn(c) = c

  

Wie combinators arbeiten?

Beispiele unten annehmen strong + dynamische Eingabe:

Faul (normal Ordnung) Y-Combinator:
Diese Definition gilt für Sprachen mit faul. (auch: aufgeschoben, Call-by-need) Bewertung - Bewertungsstrategie, welche die Auswertung eines Ausdrucks, bis ihr Wert verzögert benötigt wird, 

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

Was dies bedeutet, ist, daß für eine gegebene Funktion f (die eine nicht-rekursive Funktion ist), kann die entsprechende rekursive Funktion ersten λx.f(x x) durch Berechnung erhalten werden, und dann auf sich selbst diese Lambda-Ausdruck angewendet wird.

Strenge (applicative Ordnung) Y-Combinator:
gilt diese Definition auf Sprachen mit strengen (auch: eifrig, gierig). Bewertung - Bewertungsstrategie, in der ein Ausdruck ausgewertet 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 das gleiche wie faul man darin die Natur ist, ist es nur einen zusätzlichen λ Wrapper bietet die Lambda-Körper Auswertung zu verzögern. Ich habe gefragt, href="https://stackoverflow.com/questions/49404583/self-self-call-inside-the-let-statement-in-strict-language">, etwas im Zusammenhang mit diesem Thema.

  

Was sind sie gut?

Stolen entlehnt Antwort von Chris Ammerman : Y -combinator verallgemeinert Rekursion, ihre Umsetzung zu abstrahieren, und damit es von der eigentlichen Arbeit der betreffenden Funktion zu trennen.

Auch wenn Y-Combinator hat einige praktische Anwendungen, es ist vor allem ein theoretisches Konzept, das Verständnis von denen Ihre allgemeine Vision erweitern und wird, wahrscheinlich, steigern Sie Ihre analytischen und Entwickler Fähigkeiten.

  

Sind sie sinnvoll in prozeduralen Sprachen?

Wie von Mike Vanier angegeben: ist es möglich, definiert einen Y Combinator in vielen statisch typisierten Sprachen, aber in der Regel solche Definitionen (zumindest in den Beispielen, die ich gesehen habe) einig nicht offensichtliche Art hackery erfordern, da ter Y Combinator selbst keine einfachen statischen Typ. Das ist über den Rahmen dieses Artikels sprengen, also werde ich es nicht weiter erwähnen

Und wie von Chris Ammerman erwähnt : Die meisten Verfahrenssprachen hat statische Typisierung.

So Antwort auf diese -. Nicht wirklich

Ein Fixpunkt-Kombinator (oder Festkommaoperator) ist eine Funktion höherer Ordnung, die einen festen Punkt anderer Funktionen berechnet. Dieser Vorgang ist relevant in der Theorie Programmiersprache, weil sie die Umsetzung der Rekursion in Form einer Rewrite-Regel erlaubt, ohne explizite Unterstützung von der Runtime-Engine Sprache. (Src Wikipedia)

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 zusätzliche Funktion: 

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

Schließlich rufen Sie fac(5).

Ich denke, der beste Weg, dies zu beantworten ist, um eine Sprache zu wählen, wie Sie 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));
    }
}

Jetzt ist es so umschreiben, dass es nicht den Namen der Funktion innerhalb der Funktion verwendet, sondern nennt es noch rekursiv.

Der einzige Ort, der Name der Funktion factorial ist an der Aufrufstelle gesehen werden soll.

. Hinweis: Sie können keine Namen von Funktionen verwenden, aber Sie können Namen von Parametern verwenden

Die Arbeit des Problems. Schauen Sie es nicht auf. Sobald Sie es zu lösen, werden Sie verstehen, welches Problem des y-combinator löst.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top