Festkomma-Kombinator

    Als ich zum ersten Mal gefragt wurde, ob eine Funktion einer Ansicht ohne die Verwendung von Ansichtskonstrukten existieren könnte , stürzte sie mich in eine tiefe kognitive Dissonanz. Wie kann es eine Funktion ohne Platz für Werte geben? Über die naheliegende OptionFunc,T>default(T)
    T Fix(Func func){
       return func(Fix(func));
    }
    Ich konnte nicht einmal denken. Können solche Funktionen ausgeführt werden? Es wird endlos aufgerufen und gibt kein Ergebnis. In Sprachen wie C # führt eine solche Konstruktion zwar zu einer Schleife, funktioniert jedoch möglicherweise auch in Sprachen wie Python oder Haskell. Jetzt wird es ein bisschen Haskell-Code geben. Ich hoffe, die Syntax ist für alle mehr oder weniger klar.
    Das einfachste Beispiel:
    fix f = f( fix f)
    const42 x = 42
    print(fix const42) -- Угадайте, что выведет эта конструкция?
    Wenn wir den Aufruf erweitern, werden wir sehen, dass die folgende Kette von Berechnungen stattfindet:
    fix const42 -> const42 ( fix const42) -> 42
    Der letzte Übergang erfolgt aufgrund der Tatsache, dass wir das Argument der Funktion nicht benötigen, um ihren Wert zu berechnen.
    Es stellt sich die Frage: Wenn die Funktion von ihrem Argument abhängt, hört die Berechnung nicht auf, was sollen wir dann tun?
    Hör nicht auf, okay. Wenn der Wert nicht verwendet wird, sollte er nicht berechnet werden, was der Faulheit von Haskell zu verdanken ist.
    : Ist die Funktion des Hinzufügens eines Elements zum Kopf der Liste. Zum Beispiel:1:[2,3] = [1,2,3], n:[] = [n]

    Betrachten Sie die Funktion fix (1:). Es wird eine Liste zurückgegeben, die offensichtlich unendlich ist, aber trotzdem verwendet werden kann.
    take 3 (fix (1:)) -> take 3 (1:fix (1:)) -> 1:take 2 (fix (1:)) -> 1:(1:take 1 (fix (1:)))
    -> 1:(1:(1:take 0 (fix (1:)))) -> 1:(1:(1:[])) -> 1:(1:[1]) -> 1:[1,1] -> [1,1,1]
    So einfach ist das Ergebnis einer Funktion, die ihren Parameter verwendet. Wir haben sogar eine nützliche Sache erstellt:
    repeat n = fix (n:)- Eine endlose Liste von einem sich wiederholenden Element erstellen.
    Unendlichkeit ist kein Laster, die Hauptsache ist, dass irgendwo, egal ob drinnen oder draußen, die Kette der Berechnungen bricht. Welche Designs können die Kette brechen?
    Bis zu diesem Punkt haben wir angenommen, dass der Funktionstyp für fix ein signifikanter Typ ist. Aber warum fangen wir nicht an, eine Funktion höherer Ordnung zu verwenden ? Versuchen wir ein traditionelles Beispiel:
    factCore f = \x -> if x == 0 then 1 else x * f (x-1)
    Dann ist die Funktion fix factCoreeine gewöhnliche Fakultät. Tatsächlich wird jedes Mal anstelle der f-Funktion die factCore-Funktion ersetzt, wodurch alles der gewöhnlichen Rekursion extrem ähnlich wird.

    Versuchen wir etwas komplizierteres. Zum Beispiel, um alle Folgen der Länge k zu erzeugen, die aus Zahlen von 1 bis n bestehen, so dass es keine zwei benachbarten identischen Zahlen gibt. Die Aufgabe wird aus dem Finger gesaugt, aber trotzdem.
    allDiffCore n f = \k cond -> if k == 1 then map (\x->[x]) $ filter cond [1..n] else concat $ map (\x -> map (x:) (f (k-1) (/=x)) ) (filter cond [1..n])
    sequences n k = fix (allDiffCore n) k (\x->True)
    Eine kleine Erklärung:
    filter- Eine Funktion, die zwei Parameter akzeptiert: Bedingungen und eine Liste. Gibt eine Liste von Objekten zurück, die die Bedingung erfüllen.
    /=- gewöhnliches "nicht gleich". Dies ist eine sehr mathematische Notation.
    concat- eine Funktion, die eine Liste von Listen in einer Liste kombiniert.
    In jedem Schritt nehmen wir mehrere geeignete Elemente und definieren eine Funktion, die bestimmt, ob das nächste Element für uns geeignet ist. Mit dieser Vorlage können Sie viele verschiedene Sequenzen generieren. Um beispielsweise immer größere Sequenzen zu erhalten, reicht es aus, nur den für die Filterfunktion verantwortlichen Teil zu ändern, dh (/ = x) durch (> x) zu ersetzen.

    Und jetzt ist die Aufgabe zu überlegen: Wie schreibt man eine Funktion, die das Queen-Problem löst , auf ein Schachbrett der Größe n * n?
    Wie Sie bereits bemerkt haben, wird durch die Verwendung der Fix-Funktion (übrigens ein Sonderfall des Festkomma-Kombinators) eine direkte Rekursion in Funktionen vermieden, die beispielsweise in der Lambda-Rechnung nützlich sein kann, da dort keine gewöhnliche Rekursion verwendet werden kann.

    Als Bonus schlage ich einen bestimmten, stark verkürzten Festkomma-Kombinator für c # vor:
    public static Func Fix(Func, Func> f)
    {
       // Создание функции необходимо использовать, чтобы дальнейшие вызовы происходили непосредственно
       // во время передачи значения внутрь. Это позволяет избежать зацикливания
       return f(x => Fix(f)(x));
    }
    Und weitere Verwendung:
    var fact = Fix(self => x =>
       {
          if (x == 0)
             return 1;
          return x * self(x - 1);
       });
    var result = fact(5);   // 120

    Jetzt auch beliebt: