Maintien de l'État sans affectation

J'apprends la programmation fonctionnelle et j'ai du mal à comprendre comment certains scénarios particuliers sont mis en œuvre sans utiliser d'affectation. Le simple problème suivant résume à peu près ma confusion.

Écrivez un programme qui reçoit des événements sur les changements dans une structure de données donnée et émet des événements lorsque cette structure de données atteint un certain état.

J'ai donc une copie de la structure de données que je maintiens

datastructure_copy::DataStructure 

J'ai le flux d'événements qui se déclenche quand il change:

datastructure_changes::Stream Change

J'ai une fonction qui applique une modification à une structure de données et renvoie une nouvelle copie:

apply_change::Change -> DataStructure -> DataStructure

Et j'ai un prédicat qui vérifie si l'état des données a atteint l'état souhaité.

is_ready::DataStructure ->Boolean

En d'autres termes, j'ai besoin de quelque chose comme «réduire» qui fonctionne sur les flux.

Je sais qu'une façon de mettre en œuvre cela est de recalculer l'état chaque fois qu'un changement arrive, mais cela semble peu pratique. J'ai joué un peu avec la monade d'État, mais il me semble que cela vise à résoudre un problème différent.

Alors, y a-t-il une autre façon de procéder?

Notez que ma question est purement conceptuelle et je ne connais pas très bien Haskell.

Je sais qu'une façon de mettre en œuvre cela est de recalculer l'état chaque fois qu'un changement arrive, mais cela semble peu pratique.

Si les modifications appliquées lorsqu'un événement se produit ne sont pas distributives, d'une manière ou d'une autre, vous devrez recalculer l'état chaque fois qu'un événement se produit, car l'état final n'est rien d'autre que l'état initial, plus les modifications successives. Et même si les modifications sont distributives, vous voulez généralement transformer successivement un état en un autre, car vous voulez arrêter votre processus aussi rapidement qu'un état donné est atteint, et puisque vous devez calculer l'état suivant pour déterminer si le nouveau est l'état voulu.

Dans la programmation fonctionnelle, les changements d'état sont généralement représentés par des appels de fonction et / ou des paramètres de fonction.

Comme vous ne pouvez pas prédire quand l'état final sera calculé, vous ne devez pas utiliser la fonction récursive non-queue. Un flux d'états, dans lequel chaque état est basé sur le précédent, pourrait être une bonne alternative.

Donc dans votre cas, je répondrais à la question par le code suivant, en Scala:

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 

Ce qui peut donner, par exemple (j'ai simplifié la sortie):

0.0
0.3
0.2
0.5
0.8

val states: Stream[Double] = ... est la ligne où les états successifs sont calculés.

Le premier élément de ce flux est l'état initial du système. zipfusionne le flux d'états avec le flux d'événements en un seul flux de paires d'éléments, chaque paire étant un (état, événement). maptransforme chaque paire en une seule valeur étant le nouvel état, calculé en fonction de l'ancien état et de l'événement associé. Un nouvel état est donc un état précédemment calculé, plus l'événement associé qui "modifie" l'état.

Donc, fondamentalement, vous définissez un flux potentiellement infini d'états, chaque nouvel état étant fonction du dernier état calculé et d'un nouvel événement. Étant donné que les flux sont paresseux dans Scala (entre autres), ils ne sont calculés qu'à la demande, vous n'avez donc pas à calculer des états inutiles et vous pouvez calculer autant d'états que vous le souhaitez.

Si vous n'êtes intéressé que par le premier état qui respecte le prédicat, remplacez la dernière ligne de code par:

states find predicate get

Qui récupère:

res7: Double = 1.1

Vous dites que vous avez 2 fonctions:

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

et si je vous comprends bien, cela is_readycoûte plutôt cher, donc vous ne voulez pas le faire pour chaque événement de changement encore et encore.

Ce dont vous avez besoin, c'est qu'une fonction prenne une DataStructure initiale et la condense dans un état simple et une fonction qui prend un état condensé, un changement et génère un nouvel état condensé.

Disons que DataStructure est un triplet x,y,zet que vous attendez que x, y et z soient des nombres premiers. Votre état condensé pourrait alors être un ensemble dont x, y, z ne sont pas premiers. Un changement qui rend x prime supprime x de l'ensemble. Un changement qui rend x non premier ajoute x à l'ensemble (s'il n'est pas présent). La DataStructure est prête, puis l'ensemble est vide.

L'idée serait que la mise à jour de l'état condensé est beaucoup moins chère que la mise à jour de DataStructure et que l'informatique est déjà prête à partir de zéro.

Remarque: Une approche encore meilleure pourrait être de garder une trace de qui, x, y, z a été vérifié comme étant premier et s'il était où. Pour chaque modification, vous marquez le champ correspondant comme non coché. Ensuite, lorsque is_ready est appelé, vous vérifiez et vous souvenez. C'est mieux si vous ne cochez pas is_ready après chaque changement, car x peut changer plusieurs fois et vous ne vérifiez l'amorce qu'une seule fois.