Dies ist eine Frage, die durch eine bereits gelöschte Antwort auf diese Frage . Das Problem könnte wie folgt zusammengefasst werden:
Ist es möglich, über eine Liste zu falten, wobei das Ende der Liste beim Falten erzeugt wird?
Hier ist was ich meine. Sagen wir, ich möchte die Fakultät berechnen (das ist ein dummes Beispiel, aber es ist nur zur Demonstration) und beschließe, es so zu machen:
%Vor% Hier muss ich die Liste erstellen, die ich foldl gebe. Allerdings könnte ich dasselbe im konstanten Speicher tun (ohne die Liste zu erzeugen und ohne foldl zu benutzen):
Der Punkt hier ist, dass im Gegensatz zu der Lösung, die foldl verwendet, dies konstanten Speicher verwendet: keine Notwendigkeit, eine Liste mit allen Werten zu erzeugen!
Das Berechnen einer Fakultät ist nicht das beste Beispiel, aber es ist einfacher, die Dummheit zu verfolgen, die als nächstes kommt.
Nehmen wir an, ich habe wirklich Angst vor Schleifen (und Rekursion) und bestehe darauf, die Fakultät mit einer Falte zu berechnen. Ich würde trotzdem eine Liste brauchen. Also hier ist, was ich versuchen könnte:
%Vor% Zu meiner Überraschung funktioniert das wie beabsichtigt. Ich kann die Falte mit einem Anfangswert am Anfang einer Teilliste "säen" und das nächste Element hinzufügen, wenn ich den aktuellen Kopf konsumiere. Die Definition von fac_foldl/4 ist fast identisch mit der obigen Definition von fac_b_1/4 : Der einzige Unterschied besteht darin, dass der Zustand anders gepflegt wird. Meine Annahme hier ist, dass dies ein konstantes Gedächtnis verwenden sollte: ist diese Annahme falsch?
Ich weiß, dass das albern ist, aber es könnte nützlich sein, wenn man eine Liste überfaltet, die nicht bekannt ist, wenn die Faltung beginnt. In der ursprünglichen Frage mussten wir eine zusammenhängende Region finden, die eine Liste von x-y-Koordinaten enthält. Es reicht nicht aus, die Liste der XY-Koordinaten einmal zu überfliegen (Sie können jedoch es in zwei Pässen tun ; Beachten Sie, dass es mindestens einen besseren Weg gibt , der im selben Wikipedia-Artikel referenziert wird , aber dies verwendet auch mehrere Durchgänge, insgesamt nehmen die Mehrfachdurchlaufalgorithmen einen konstanten Zeitzugriff auf benachbarte Pixel an!).
Meine eigene Lösung für die ursprüngliche "Regionen" -Frage sieht ungefähr so aus:
%Vor%Unter Verwendung der gleichen "Technik" wie oben können wir dies in eine Falte drehen:
%Vor% Das funktioniert auch ". Die Falte hinterlässt einen Auswahlpunkt, weil ich die Endbedingung nicht wie in fac_foldl/4 oben artikuliert habe, also brauche ich einen Schnitt direkt danach (hässlich).
Sie berühren einige äußerst interessante Aspekte von Prolog, von denen jede mehrere separate Fragen allein wert ist. Ich werde eine hochrangige Antwort auf Ihre tatsächlichen Fragen geben und hoffe, dass Sie Follow-up-Fragen zu den Punkten stellen, die für Sie am interessantesten sind.
Zuerst werde ich das Fragment auf seine Essenz reduzieren:
%Vor%Beachten Sie, dass dies die Erzeugung extrem großer Ganzzahlen verhindert, so dass wir das Speicherverhalten dieses Musters wirklich untersuchen können.
Zu Ihrer ersten Frage: Ja , dies wird im O (1) -Raum ausgeführt (unter Annahme eines konstanten Platzes für entstehende Ganzzahlen).
Warum? Obwohl Sie kontinuierlich Listen in Back = [X1|Rest] erstellen, können diese Listen ohne weiteres Garbage Collection sein, weil Sie sie nirgends referenzieren.
Um Speicheraspekte Ihres Programms zu testen, betrachten Sie zum Beispiel die folgende Abfrage und begrenzen Sie den globalen Stack Ihres Prolog-Systems, so dass Sie wachsenden Speicher schnell erkennen können, wenn Sie keinen (globalen) Stack mehr haben:
%Vor%Dies ergibt:
%Vor%Es wäre komplett anders, wenn Sie die Liste irgendwo referenzieren . Zum Beispiel:
%Vor%Mit dieser sehr kleinen Änderung ergibt die obige Abfrage:
%Vor%Somit kann die Frage, ob ein Begriff irgendwo referenziert wird, die Speicheranforderungen Ihres Programms erheblich beeinflussen. Das hört sich beängstigend an, ist aber in der Praxis kaum ein Thema: Entweder brauchen Sie den Begriff, in diesem Fall müssen Sie ihn ohnehin im Speicher darstellen, oder Sie brauchen den Begriff nicht, dann wird er einfach nicht mehr referenziert in Ihrem Programm und wird Garbage Collection zugänglich. In der Tat ist das Erstaunliche, dass GC in Prolog auch für ziemlich komplexe Programme so gut funktioniert, dass man in vielen Situationen nicht viel darüber sagen muss.
Weiter zu Ihrer zweiten Frage: Natürlich ist die Verwendung von (->)/2 fast immer sehr problematisch, da es Sie auf eine bestimmte Verwendungsrichtung beschränkt und die von logischen Beziehungen erwartete Allgemeingültigkeit zerstört.
Dafür gibt es mehrere Lösungen. Wenn Ihr CLP (FD) -System zcompare/3 oder eine ähnliche Funktion unterstützt, können Sie essence_/3 wie folgt schreiben:
Ein weiteres sehr schönes Meta-Prädikat namens if_/3 wurde vor kurzem in Indexing dif / 2
Zur dritten Frage: Wie beziehen sich Staaten mit DCGs darauf? Die DCG-Notation ist definitiv nützlich, wenn Sie einen globalen Zustand auf mehrere Prädikate übertragen wollen, von denen nur ein paar auf den Zustand zugreifen oder ihn ändern müssen, und die meisten von ihnen den Zustand einfach durchlassen. Dies ist völlig analog zu Monaden in Haskell.
Die "normale" Prolog-Lösung wäre, jedes Prädikat um zwei Argumente zu erweitern, um die Beziehung zwischen dem Zustand vor dem Aufruf des Prädikats und dem Zustand danach zu beschreiben. Mit der DCG-Notation können Sie diesen Aufwand vermeiden.
Wichtig: Mithilfe der DCG-Notation können Sie imperative Algorithmen nahezu wortwörtlich in Prolog kopieren, ohne dass Sie viele Hilfsargumente einführen müssen, selbst wenn Sie globale Zustände benötigen. Betrachten Sie als Beispiel dafür ein Fragment von Tarjans stark verbundener Komponenten -Algorithmus im Imperativ Begriffe:
%Vor%Dies verwendet eindeutig einen globalen Stack und index , der normalerweise zu neuen Argumenten wird, die Sie in all weitergeben müssen Prädikate. Nicht so mit DCG-Notation! Nehmen wir einmal an, dass die globalen Entitäten einfach zugänglich sind und Sie das gesamte Fragment in Prolog als:
codieren können %Vor%Das ist ein sehr guter Kandidat für seine eigene Frage , also denkt über diesen Teaser nach.
Endlich habe ich eine allgemeine Bemerkung: Meiner Ansicht nach sind wir nur am Anfang einer Reihe sehr mächtiger und allgemeiner Meta-Prädikate, und der Lösungsraum ist immer noch weitgehend < em> unerforscht . call/N , maplist/[3,4] , foldl/4 und andere Meta-Prädikate sind definitiv ein guter Anfang. if_/3 hat das Potenzial, gute Leistung mit der von Prolog-Prädikaten erwarteten Allgemeingültigkeit zu kombinieren.
Wenn Ihre Prolog-Implementierung freeze / 2 oder ein ähnliches Prädikat (z. B. Swi-Prolog) unterstützt, können Sie den folgenden Ansatz verwenden:
%Vor%Das obige Beispiel definiert zuerst ein Prädikat ( fac_list ), das eine "faule" Liste von steigenden Ganzzahlwerten beginnend mit N bis zum Maximalwert (Max) erstellt, wobei das nächste Listenelement erst nach dem vorherigen generiert wird Einer wurde "zugegriffen" (mehr dazu unten). Dann faltet faktoriell einfach Multiplikation über die faule Liste, was zu einer konstanten Speichernutzung führt.
Der Schlüssel zum Verständnis dieses Beispiels besteht darin, sich daran zu erinnern, dass Prolog-Listen tatsächlich nur Begriffe von Arity 2 mit dem Namen '.' (Tatsächlich wurde in Swi-Prolog 7 der Name geändert, aber das ist für diese Diskussion nicht wichtig), wobei das erste Element das Listenelement und das zweite Element das Ende (oder das abschließende Element - leere Liste, []) darstellt. Beispielsweise. [1, 2, 3] kann wie folgt dargestellt werden:
%Vor%Dann ist freeze wie folgt definiert:
%Vor%Das heißt, wenn wir anrufen:
%Vor%dann werden folgende Schritte passieren:
Wir können dieses Beispiel wie folgt erweitern:
%Vor%Dies funktioniert genau wie im vorherigen Beispiel, außer dass es nach und nach 3 Elemente statt 1 generiert.
Gemäß der Anfrage von Boris wurde das zweite Beispiel mit freeze implementiert. Ehrlich gesagt bin ich nicht ganz sicher, ob das die Frage beantwortet, da der Code (und IMO, das Problem) eher erfunden ist, aber hier ist es. Zumindest hoffe ich, dass dies anderen Menschen die Idee geben wird, für welchen Frost es nützlich sein könnte. Der Einfachheit halber verwende ich ein 1D-Problem anstelle von 2D, aber die Änderung des Codes zur Verwendung von 2 Koordinaten sollte eher trivial sein.
Die allgemeine Idee ist, (1) Funktion zu haben, die neue Open / Closed / Rest / etc erzeugt. Zustand basierend auf vorherigem, (2) "unendlicher" Listengenerator, dem gesagt werden kann, dass er "neue" Elemente von "außen" erzeugt, und (3) fold_step-Funktion, die über "unendliche" Liste faltet, wobei jeder neue Zustand erzeugt wird Listenelement und, wenn dieser Zustand als letzter betrachtet wird, Generator wird angehalten.
Es ist erwähnenswert, dass die Elemente der Liste aus keinem anderen Grund verwendet werden, als den Generator zu informieren, damit er aufhört. Der gesamte Berechnungszustand wird im Akkumulator gespeichert.
Boris , bitte klären Sie, ob dadurch Ihr Problem gelöst wird. Genauer gesagt, welche Art von Daten haben Sie versucht, an den Step-Handler (Element, Akkumulator, Nächster Akkumulator) zu übergeben?
%Vor%Eine feine Verbesserung des obigen Codes wäre es, fold_step zu einer Funktion höherer Ordnung zu machen, die next_state als erstes Argument übergeben würde.
Tags und Links prolog swi-prolog fold meta-predicate