Maintaining State without assignment

Question

I am learning functional programming and I have trouble understanding how some particular scenarios are implemented without the use of assignment. The following simple problem pretty much sums up my confusion.

Write a program that receives events about changes in a given data structure and emits events when this data structure reaches a certain state.

So I have a copy of the datastructure that I maintain

datastructure_copy::DataStructure 

I have the stream of events which are fired when it changes:

datastructure_changes::Stream Change

I have a function that applies a change to a data structure and returns a new copy it:

apply_change::Change -> DataStructure -> DataStructure

And I have a predicate which checks if the data state has reached the desired state.

is_ready::DataStructure ->Boolean

In other words I need something like 'reduce' that works on streams.

I know that one way to implement this is to recompute the state each time a change arrives, however this seems impractical. I played a bit with the State monad, but it looks to me like it is meant to solve a different problem.

So is there another way to do that?

Note that my question is purely conceptual and I am not deeply familiar with Haskell.

Answer 1

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

If the changes applied when an event occurs are not distributive, in one way or another, you will have to recompute the state each time an event occurs, since the final state is nothing but the initial state, plus successive changes. And even if the changes are distributive, you typically want to successively transform a state to the next one, since you want to stop your process as fast as a given state is reached, and since you have to compute the next state to determine if the new one is the wanted state.

In functional programming, state changes are typically represented by function calls and/or function parameters.

As you can not predict when the final state will be computed, you should not use non-tail recursive function. A stream of states, in which each state is based on the previous one, could be a good alternative.

So in your case, I would answer the question by the following code, 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 

Which can give, for instance (I simplified the output) :

0.0
0.3
0.2
0.5
0.8

val states: Stream[Double] = ... is the line where successive states are computed.

The first element of this stream is the initial state of the system. zip merges the stream of states with the stream of events into a single stream of pairs of elements, each pair being a (state, event). map transforms each pair into a single value being the new state, computed as a function of the old state and the associated event. A new state is therefore a previously computed state, plus the associated event that "modifies" the state.

So basically, you define a potentially infinite stream of states, each new state being a function of the last computed state, and a new event. Since streams are lazy in Scala (among others), there are only computed on demand, so you don't have to compute useless states, and you can compute as many states as you want.

If you are only interested in the first state that respects the predicate, replace the last line of code by:

states find predicate get

Which retrieves:

res7: Double = 1.1

Answer 2

You say you have 2 functions:

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

and if I understand you right then is_ready is rather expensive so you don't want to do that for every change event over and over.

What you need is a function takes an initial DataStructure and condenses it into a simple state and a function that takes a condensed state, a Change and outputs a new condensed state.

Say DataStructure is a triplet x,y,z and you are waiting for x, y and z to be prime numbers. Your condensed state could then be a set of which of x,y,z are not prime. A Change that makes x prime removes x from the set. A Change that makes x not prime adds x to the set (if not present). The DataStructure is ready then the set is empty.

The idea would be that updating the condensed state is a lot cheaper than updating DataStructure and computing is_ready from scratch.

Note: An even better approach could be to keep track of which of x,y,z where checked for being prime and if they where. For every Change you flag the relevant field as not checked. Then when is_ready is called you check and remember. This is better if you do not check is_ready after every Change since x might change multiple times and you only check for prime once.