Zustand ohne Zuordnung erhalten

Ich lerne funktionale Programmierung und habe Probleme zu verstehen, wie bestimmte Szenarien ohne Zuweisung implementiert werden. Das folgende einfache Problem fasst meine Verwirrung ziemlich gut zusammen.

Schreiben Sie ein Programm, das Ereignisse über Änderungen in einer bestimmten Datenstruktur empfängt und Ereignisse ausgibt, wenn diese Datenstruktur einen bestimmten Zustand erreicht.

Ich habe also eine Kopie der Datenstruktur, die ich pflege

datastructure_copy::DataStructure 

Ich habe den Strom von Ereignissen, die ausgelöst werden, wenn er sich ändert:

datastructure_changes::Stream Change

Ich habe eine Funktion, die eine Änderung auf eine Datenstruktur anwendet und eine neue Kopie zurückgibt:

apply_change::Change -> DataStructure -> DataStructure

Und ich habe ein Prädikat, das prüft, ob der Datenzustand den gewünschten Zustand erreicht hat.

is_ready::DataStructure ->Boolean

Mit anderen Worten, ich brauche so etwas wie "Reduzieren", das bei Streams funktioniert.

Ich weiß, dass eine Möglichkeit, dies zu implementieren, darin besteht, den Status jedes Mal neu zu berechnen, wenn eine Änderung eintrifft. Dies scheint jedoch unpraktisch. Ich habe ein bisschen mit der Staatsmonade gespielt, aber es scheint mir, dass es ein anderes Problem lösen soll.

Gibt es einen anderen Weg, das zu tun?

Beachten Sie, dass meine Frage rein konzeptionell ist und ich mit Haskell nicht sehr vertraut bin.

Ich weiß, dass eine Möglichkeit, dies zu implementieren, darin besteht, den Status jedes Mal neu zu berechnen, wenn eine Änderung eintrifft. Dies scheint jedoch unpraktisch.

Wenn die Änderungen, die beim Eintreten eines Ereignisses angewendet werden, auf die eine oder andere Weise nicht verteilend sind, müssen Sie den Status jedes Mal neu berechnen, wenn ein Ereignis auftritt, da der Endstatus nichts anderes als der Anfangszustand ist, zuzüglich aufeinanderfolgender Änderungen. Und selbst wenn die Änderungen verteilend sind, möchten Sie normalerweise einen Status sukzessive in den nächsten umwandeln, da Sie Ihren Prozess stoppen möchten, sobald ein bestimmter Status erreicht ist, und da Sie den nächsten Status berechnen müssen, um festzustellen, ob der Neu ist der gesuchte Zustand.

Bei der Funktionsprogrammierung werden Zustandsänderungen typischerweise durch Funktionsaufrufe und / oder Funktionsparameter dargestellt.

Da Sie nicht vorhersagen können, wann der Endzustand berechnet wird, sollten Sie keine rekursive Funktion ohne Schwanz verwenden. Ein Strom von Staaten, in denen jeder Staat auf dem vorherigen basiert, könnte eine gute Alternative sein.

In Ihrem Fall würde ich die Frage in Scala mit dem folgenden Code beantworten:

import scala.util.Random

val initState = 0.0
def nextState(state: Double, event: Boolean): Double = if(event) state + 0.3 else state - 0.1 // give a new state
def predicate(state: Double) = state >= 1

// random booleans as events
// nb: must be a function in order to force Random.nextBoolean to be called for each  element of the stream
def events(): Stream[Boolean] = Random.nextBoolean #:: events()  

val states: Stream[Double] = initState #:: states.zip(events).map({ case (s,e) => nextState(s,e)}) // a stream of all the successive states

// stop when the state is >= 1 ;
// display all the states computed before it stopped
states takeWhile(! predicate(_)) foreach println 

Was zum Beispiel geben kann (ich habe die Ausgabe vereinfacht):

0.0
0.3
0.2
0.5
0.8

val states: Stream[Double] = ... ist die Zeile, in der aufeinanderfolgende Zustände berechnet werden.

Das erste Element dieses Streams ist der Anfangszustand des Systems. zipführt den Strom von Zuständen mit dem Strom von Ereignissen zu einem einzigen Strom von Paaren von Elementen zusammen, wobei jedes Paar ein (Zustand, Ereignis) ist. mapwandelt jedes Paar in einen einzelnen Wert um, der der neue Zustand ist und als Funktion des alten Zustands und des zugehörigen Ereignisses berechnet wird. Ein neuer Status ist daher ein zuvor berechneter Status sowie das zugehörige Ereignis, das den Status "ändert".

Im Grunde definieren Sie einen potenziell unendlichen Strom von Zuständen, wobei jeder neue Zustand eine Funktion des zuletzt berechneten Zustands und ein neues Ereignis ist. Da Streams in Scala (unter anderem) faul sind, werden sie nur bei Bedarf berechnet, sodass Sie keine nutzlosen Zustände berechnen müssen und so viele Zustände berechnen können, wie Sie möchten.

Wenn Sie nur an dem ersten Status interessiert sind, der das Prädikat berücksichtigt, ersetzen Sie die letzte Codezeile durch:

states find predicate get

Welches ruft ab:

res7: Double = 1.1

Sie sagen, Sie haben 2 Funktionen:

apply_change::Change -> DataStructure -> DataStructure
is_ready::DataStructure ->Boolean

und wenn ich dich richtig verstehe, is_readyist es ziemlich teuer, also willst du das nicht für jedes Änderungsereignis immer und immer wieder tun.

Was Sie brauchen, ist eine Funktion, die eine anfängliche DataStructure in einen einfachen Zustand umwandelt und eine Funktion, die einen komprimierten Zustand, eine Änderung, annimmt und einen neuen komprimierten Zustand ausgibt.

Angenommen, DataStructure ist ein Triplett x,y,zund Sie warten darauf, dass x, y und z Primzahlen sind. Ihr kondensierter Zustand könnte dann eine Menge sein, von denen x, y, z keine Primzahl sind. Eine Änderung, die x prime macht, entfernt x aus der Menge. Eine Änderung, bei der x nicht primiert wird, fügt x zur Menge hinzu (falls nicht vorhanden). Die DataStructure ist fertig, dann ist der Satz leer.

Die Idee wäre, dass das Aktualisieren des komprimierten Zustands viel billiger ist als das Aktualisieren von DataStructure und das Rechnen von Grund auf neu.

Hinweis: Ein noch besserer Ansatz könnte darin bestehen, zu verfolgen, welche von x, y, z auf Primzahl überprüft wurden und ob sie wo waren. Bei jeder Änderung markieren Sie das entsprechende Feld als nicht markiert. Wenn dann is_ready aufgerufen wird, überprüfen Sie und erinnern sich. Dies ist besser, wenn Sie is_ready nicht nach jeder Änderung überprüfen, da sich x möglicherweise mehrmals ändert und Sie nur einmal nach prime suchen.