Erklärung von „den Bund fürs Leben“

Question

Beim Lesen Sachen-Haskell ich manchmal über den Ausdruck komme „den Bund fürs Leben“, ich glaube, ich verstehe WHAT es tut, aber nicht wie.

Also, gibt es irgendwelche gute, grundlegende und einfach zu verstehen Erklärungen dieses Konzepts?

Answer 1

Das Binden des Knotens ist eine Lösung für das Problem der kreisförmigen Datenstrukturen. In imperativen Sprachen konstruieren Sie eine zirkuläre Struktur, indem Sie zuerst eine nicht-kreisförmige Struktur erstellen und dann zurückgehen und die Zeiger reparieren, um die Zirkularität hinzuzufügen.

Angenommen, Sie wollten eine zweigliedrige Kreisliste mit den Elementen "0" und "1". Es wäre unmöglich zu konstruieren, denn wenn Sie den Knoten "1" erstellen und dann den Knoten "0" erstellen, um auf ihn zu zeigen, können Sie nicht zurückgehen und den Knoten "1" reparieren, um auf den Knoten "0" zu zeigen . Sie haben also eine Situation mit Hühnern und Eiern, in der beide Knoten existieren müssen, bevor beide erstellt werden können.

Hier ist, wie Sie es in Haskell tun. Betrachten Sie den folgenden Wert:

alternates = x where 
    x = 0 : y 
    y = 1 : x 

In einer nicht faul Sprache wird dies eine Endlosschleife wegen der nicht abgeschlossenen Rekursion. Aber in Haskell macht die faule Bewertung das Richtige: Sie erzeugt eine zweigliedrige Kreisliste.

Um zu sehen, wie es in der Praxis funktioniert, denken Sie darüber nach, was zur Laufzeit passiert. Die übliche "Thunk" -Implementierung der Lazy-Evaluierung stellt einen unausgewerteten Ausdruck als eine Datenstruktur dar, die einen Funktionszeiger plus die an die Funktion zu übergebenden Argumente enthält. Wenn dies ausgewertet wird, wird der Thunk durch den tatsächlichen Wert ersetzt, so dass zukünftige Referenzen die Funktion nicht erneut aufrufen müssen.

Wenn Sie das erste Element der Liste nehmen, wird 'x' bis auf einen Wert (0, & y) ausgewertet, wobei das Bit "& y" ein Zeiger auf den Wert von 'y' ist. Da 'y' nicht ausgewertet wurde, ist dies zur Zeit ein Thunk. Wenn Sie das zweite Element der Liste übernehmen, folgt der Computer dem Link von x zu diesem Thunk und wertet ihn aus. Sie ergibt (1, & x), oder anders ausgedrückt, einen Zeiger zurück auf den ursprünglichen 'x'-Wert. Sie haben jetzt eine kreisförmige Liste im Speicher. Der Programmierer muss die Back-Pointer nicht reparieren, weil der Lazy-Evaluierungsmechanismus dies für Sie erledigt.

Answer 2

Es ist nicht ganz, was Sie gefragt, und es ist nicht direkt mit Haskell verwandt, aber Bruce McAdam Papier That About Wraps It Up geht in diesem Thema in erheblicher Breite und Tiefe. Bruce Grundidee ist, einen expliziten Knoten-Binde-Operator genannt WRAP anstelle der impliziten Knoten-Verknüpfung, die automatisch in Haskell, OCaml und einigen anderen Sprachen erfolgt. Das Papier hat viele unterhaltsame Beispiele, und wenn Sie in Knotenketten interessiert sind, denke ich, dass Sie mit einem viel besseren Gefühl für den Prozess kommen werden.