Wie kann ein Wert vom Typ:
%Vor%Haben Sie einen Wert, der auf sich selbst verweist?
Der resultierende Wert sollte im folgenden Python-Code für eine geeignete Definition von Tree:
gleich x sein %Vor%Bearbeiten : Offensichtlich ist mehr Erklärung notwendig. Ich versuche F # und funktionale Programmierung zu lernen, also habe ich beschlossen, den Cover-Tree zu implementieren, den ich zuvor in anderen Sprachen programmiert habe . Die relevante Sache hier ist, dass die Punkte jeder Ebene eine Untermenge von denen der Ebene darunter sind. Die Struktur geht konzeptionell auf Ebene -Unendlichkeit.
In Imperativsprachen hat ein Knoten eine Liste von Kindern, die sich selbst enthalten. Ich weiß, dass dies in F # zwingend gemacht werden kann. Und nein, es wird keine Endlosschleife mit dem Cover-Tree-Algorithmus erstellt.
Tomas 'Antwort schlägt zwei mögliche Wege vor, um rekursive Datenstrukturen in F # zu erzeugen. Eine dritte Möglichkeit besteht darin, die Tatsache auszunutzen, dass Datensatzfelder direkte Rekursion unterstützen (wenn sie in derselben Assembly verwendet werden, in der der Datensatz definiert ist). Zum Beispiel funktioniert der folgende Code ohne jedes Problem:
%Vor%Wenn Sie diesen Listentyp anstelle des integrierten Typs verwenden, können wir Ihren Code verwenden:
%Vor%Sie können dies nicht direkt tun, wenn die rekursive Referenz nicht verzögert wird (z. B. in eine Funktion oder einen Lazy-Wert eingeschlossen). Ich denke, die Motivation ist, dass es keinen Weg gibt, den Wert mit unmittelbaren Verweisen "auf einmal" zu erzeugen, was aus theoretischer Sicht unangenehm wäre.
F # unterstützt jedoch rekursive Werte - Sie können diese verwenden, wenn der rekursive Verweis verzögert wird (der F # -Compiler generiert dann einen Code, der die Datenstruktur initialisiert und die rekursiven Referenzen ausfüllt). Der einfachste Weg ist, den Verweis in einen Lazy-Wert zu schreiben (Funktion würde auch funktionieren):
%Vor% Eine andere Möglichkeit ist, dies mit Mutationen zu schreiben. Dann müssen Sie auch Ihre Datenstruktur änderbar machen. Sie können beispielsweise ref<Tree> anstelle von Tree speichern:
Wie James erwähnte, können Sie, wenn Sie das nicht tun dürfen, einige nette Eigenschaften haben, so dass jedes Programm, das die Datenstruktur durchläuft, beendet wird (weil die Datenstruktur beschränkt ist und nicht rekursiv sein kann). Sie müssen also mit rekursiven Werten vorsichtiger sein: -)
Tags und Links f# tail-recursion recursive-datastructures