How does Reactive Banana's mapAccum function work?

Question

I have looked at a number answers to questions here on Stack Overflow trying to find a solution to my problem in using the Reactive Banana library. All the answers use some magic using 'mapAccum' that I can't quite understand. Looking at the API documentation all I find is "Efficient combination of accumE and accumB." which is not very helpful.

It seems that this function can be used to compare the values of a Behavior at the time of two consecutive events which is what I'd like to do. But I not clear how to make that work.

How exactly does mapAccum work?

Ligurian

Answer 1

Notice that

mapAccum :: acc -> Event t (acc -> (x, acc)) -> (Event t x, Behavior t acc)

so it takes an initial value :: acc to accumulate on, and an Event which produces a function that updates that accumulated value whilst producing an output value ::x. (Typically you'd make such an event by partially applying some function via <$>.) As a result you get a new Event that fires your x values whenever they turn up and a Behaviour containing your current accumulated value.

Use mapAccum if you have an event and you want to make a related behaviour and event.

For example in your problem domain from your other question, suppose you have an event eTime :: Event t Int that fired erratically and you wanted to calculate eDeltaTime :: Event t Int for the differences and bTimeAgain :: Behaviour t Int for the currently used time:

type Time = Int
type DeltaTime = Time 

getDelta :: Time -> Time -> (DeltaTime,Time)
getDelta new old = (new-old,new)

I could have written that getDelta new = \old -> (new-old,new) to make the next step clearer:

deltaMaker :: Event t (Time -> (DeltaTime,Time))
deltaMaker = getDelta <$> eTime

(eDeltaT,bTimeAgain) = mapAccum 0 $ deltaMaker

In this case, bTimeAgain would be a behaviour with the same value as the events in eTime. This happens because my getDelta function passes new straight through unchanged from eTime to the acc value. (If I wanted bTimeAgain on its own, I would have used stepper :: a -> Event t a -> Behaviour t a.) If I don't need bTimeAgain, I could just write (eDeltaT,_) = mapAccum 0 $ deltaMaker.

Abundance

Answer 2

The mapAccum function is very similar to the mapAccumL function from the standard Data.List module, hence the name. The documentation on Hackage also includes a link to the source code of mapAccum. Together with the type signature, this is hopefully enough information to figure out how this function works.

Then again, I could just improve the documentation. :-) But I'm not entirely clear on how to do that short of pasting the source code. The second part of the result is easy to describe by the following equation

snd . mapAccum acc = accumB acc . fmap (. snd)

But the first part does not have such a nice equation.

I could write a description in words:

The function mapAccum accumulates a state of type acc by applying the functions contained in the second argument of type Event t (acc -> (x,acc)). The function returns an event whose occurrences are the values x and a behavior which keeps track of the accumulated state acc. Put differently, this is a Mealy machine, or state automaton.

but I'm not sure whether these words actually help.

Gazelle

Three comments, 1) I think it's great that the you, the author, are here answering questions. 2) Points free notation is hard to read if you are not sure what the function does because there are no names. 3) Where I got lost was in understanding that the acc given to the function in the input event was a good place to store history of events. I kept trying to put the value I was trying to find there instead, when that should have gone in the x part. – Ligurian

Answer 3

Note: I'm using an answer so I can write formatted code

Here is my attempt at documenting the function:

---

mapAccum ::                  acc -- Initial Accumulation Value
  ->   Event t (acc -> (x, acc)) -- Event stream that of functions that use the previous
                                 -- accumulation value to:
                                 -- a) produce a new resulting event (x) and,
                                 -- b) updates the accumulated value (acc)
  -> (Event t x, Behavior t acc) -- fst) a stream of events from of a) above
                                 -- snd) a behavior holding the accumulated values b) above

This function is the analog to the mapAccumL function from the Data.List module. It is an efficient combination of accumE and accumB. The resulting Behavior is useful for, among other things, for holding the history of previous events which might be needed to compute the values (x) of an event stream.

Example: compute the roling average of the last 5 events

rolingAverage :: forall t. Frameworks t => Event t Double -> Event t Double
rolingAverage inputStream = outputStream
  where
    funct x xs = (sum role / 5, role) where role = (x:init xs)
    functEvent = funct <$> inputStream -- NB: curries the first parameter in funct
    (outputStream,_) = mapAccum [0,0,0,0,0] functEvent  

Ligurian