Mantenimento dello stato senza incarico

I know that one way to implement this is to recompute the state each time a change arrives, however this seems impractical.

Se le modifiche applicate quando si verifica un evento non sono distributive, in un modo o nell'altro, dovrai ricalcolare lo stato ogni volta che si verifica un evento, poiché lo stato finale non è altro che lo stato iniziale, più le modifiche successive. E anche se le modifiche sono distributive, in genere si desidera trasformare successivamente uno stato in quello successivo, poiché si desidera arrestare il processo alla stessa velocità con cui viene raggiunto un determinato stato e poiché è necessario calcolare lo stato successivo per determinare se il il nuovo è lo stato desiderato.

Nella programmazione funzionale, le variazioni di stato sono tipicamente rappresentate da chiamate di funzione e / o parametri di funzione.

Poiché non è possibile prevedere quando verrà calcolato lo stato finale, non utilizzare la funzione ricorsiva non a coda. Un flusso di stati, in cui ogni stato è basato sul precedente, potrebbe essere una buona alternativa.

Quindi nel tuo caso, risponderei alla domanda con il seguente codice, in 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 

Che può dare, per esempio (ho semplificato l'output):

0.0
0.3
0.2
0.5
0.8

val states: Stream[Double] = ... è la riga in cui vengono calcolati gli stati successivi.

Il primo elemento di questo stream è lo stato iniziale del sistema. zip unisce il flusso di stati con il flusso di eventi in un singolo flusso di coppie di elementi, ogni coppia essendo uno (stato, evento). map trasforma ogni coppia in un singolo valore come nuovo stato, calcolato come una funzione del vecchio stato e dell'evento associato. Un nuovo stato è quindi uno stato precedentemente calcolato, più l'evento associato che "modifica" lo stato.

Quindi, in pratica, si definisce un flusso potenzialmente infinito di stati, ogni nuovo stato essendo una funzione dell'ultimo stato calcolato e un nuovo evento. Poiché gli stream sono pigri in Scala (tra gli altri), vengono calcolati solo su richiesta, quindi non devi calcolare stati inutili e puoi calcolare quanti stati vuoi.

Se ti interessa solo il primo stato che rispetta il predicato, sostituisci l'ultima riga di codice con:

states find predicate get

Che recupera:

res7: Double = 1.1

Dici di avere 2 funzioni:

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

e se ti capisco, allora is_ready è piuttosto costoso, quindi non vuoi farlo per ogni evento di cambiamento più e più volte.

Ciò di cui hai bisogno è che una funzione acquisisca una struttura dati iniziale e la condensa in uno stato semplice e una funzione che prende uno stato condensato, una modifica e genera un nuovo stato condensato.

Dire che DataStructure è un tripletto x,y,z e stai aspettando che x, yez siano numeri primi. Il tuo stato condensato potrebbe quindi essere un insieme di quale tra x, y, z non è primo. Una modifica che fa x primo rimuove x dal set. Una modifica che rende x non primo aggiunge x all'insieme (se non presente). DataStructure è pronto, quindi il set è vuoto.

L'idea sarebbe che l'aggiornamento dello stato di condensazione sia molto più economico dell'aggiornamento di DataStructure e che l'elaborazione sia già da zero.

Nota: Un approccio ancora migliore potrebbe essere quello di tenere traccia di quale tra x, y, z è stata selezionata per essere la prima e se è dove. Per ogni modifica, contrassegni il campo pertinente come non selezionato. Quindi quando is_ready viene chiamato tu controlli e ricordi. Questo è meglio se non si controlla is_ready dopo ogni modifica poiché x potrebbe cambiare più volte e si controlla solo per prime una volta.