Functional Programming – Maintaining State Without Assignment

functional programminghaskellreactive

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.

Best Answer

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
Related Topic