Estado de mantenimiento sin asignación

Estoy aprendiendo programación funcional y tengo problemas para entender cómo se implementan algunos escenarios particulares sin el uso de la asignación. El siguiente problema simple resume mi confusión.

Escriba un programa que reciba eventos sobre cambios en una estructura de datos dada y emita eventos cuando esta estructura de datos alcance un cierto estado.

Entonces tengo una copia de la estructura de datos que mantengo

datastructure_copy::DataStructure 

Tengo la secuencia de eventos que se activan cuando cambia:

datastructure_changes::Stream Change

Tengo una función que aplica un cambio a una estructura de datos y devuelve una nueva copia:

apply_change::Change -> DataStructure -> DataStructure

Y tengo un predicado que verifica si el estado de los datos ha alcanzado el estado deseado.

is_ready::DataStructure ->Boolean

En otras palabras, necesito algo como 'reducir' que funcione en transmisiones.

Sé que una forma de implementar esto es recalcular el estado cada vez que llega un cambio, sin embargo, esto parece poco práctico. Jugué un poco con la mónada estatal, pero me parece que está destinado a resolver un problema diferente.

Entonces, ¿hay otra manera de hacer eso?

Tenga en cuenta que mi pregunta es puramente conceptual y no estoy muy familiarizado con Haskell.

Sé que una forma de implementar esto es recalcular el estado cada vez que llega un cambio, sin embargo, esto parece poco práctico.

Si los cambios aplicados cuando ocurre un evento no son distributivos, de una forma u otra, deberá volver a calcular el estado cada vez que ocurra un evento, ya que el estado final no es más que el estado inicial, más los cambios sucesivos. E incluso si los cambios son distributivos, normalmente desea transformar sucesivamente un estado al siguiente, ya que desea detener su proceso tan rápido como se alcanza un estado determinado, y dado que tiene que calcular el siguiente estado para determinar si uno nuevo es el estado deseado.

En la programación funcional, los cambios de estado generalmente se representan mediante llamadas a funciones y / o parámetros de funciones.

Como no puede predecir cuándo se calculará el estado final, no debe usar la función recursiva sin cola. Un flujo de estados, en el que cada estado se basa en el anterior, podría ser una buena alternativa.

Entonces, en su caso, respondería la pregunta con el siguiente código, 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 

Lo que puede dar, por ejemplo (simplifiqué el resultado):

0.0
0.3
0.2
0.5
0.8

val states: Stream[Double] = ... es la línea donde se calculan los sucesivos estados.

El primer elemento de esta secuencia es el estado inicial del sistema. zipfusiona la secuencia de estados con la secuencia de eventos en una sola secuencia de pares de elementos, cada par es un (estado, evento). maptransforma cada par en un solo valor que es el nuevo estado, calculado en función del estado anterior y el evento asociado. Por lo tanto, un nuevo estado es un estado previamente calculado, más el evento asociado que "modifica" el estado.

Básicamente, usted define un flujo de estados potencialmente infinito, cada nuevo estado es una función del último estado calculado y un nuevo evento. Dado que las secuencias son perezosas en Scala (entre otras), solo se calculan a pedido, por lo que no tiene que calcular estados inútiles y puede calcular tantos estados como desee.

Si solo está interesado en el primer estado que respeta el predicado, reemplace la última línea de código por:

states find predicate get

Que recupera:

res7: Double = 1.1

Dices que tienes 2 funciones:

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

y si te entiendo bien, entonces is_readyes bastante costoso, así que no quieres hacer eso para cada evento de cambio una y otra vez.

Lo que necesita es una función que tome una DataStructure inicial y la condense en un estado simple y una función que tome un estado condensado, un Cambio y emita un nuevo estado condensado.

Digamos que DataStructure es un triplete x,y,zy está esperando que x, y y z sean números primos. Su estado condensado podría ser un conjunto de los cuales x, y, z no son primos. Un cambio que hace que x prime elimine x del conjunto. Un cambio que hace que x no sea primo agrega x al conjunto (si no está presente). DataStructure está listo y el conjunto está vacío.

La idea sería que actualizar el estado condensado es mucho más barato que actualizar DataStructure y que la informática ya está lista desde cero.

Nota: Un enfoque aún mejor podría ser realizar un seguimiento de cuáles de x, y, z se verificaron para ser primos y si fueron dónde. Por cada cambio, marca el campo relevante como no marcado. Luego, cuando se llama a is_ready, verifica y recuerda. Esto es mejor si no verifica is_ready después de cada Cambio, ya que x puede cambiar varias veces y solo verifica el cebado una vez.