Optimize Discrete data type by calming simultaneous events

[HeinrichApfelmus]

(This issue was kindly brought to my attention by Andrew Richards.)

Consider the following program:

import Reactive.Banana
import Debug.Trace

main = do
  (inputAH, inputTrigger) <- newAddHandler
  network <- compile $ do
    evt <- fromAddHandler inputAH
    let g = stepperD 0 evt
    let out = f <$> g <*> g
    reactimate $ print <$> changes out
  actuate network
  inputTrigger 3
  inputTrigger 4

f :: Int -> Int -> Int
f x y = trace ("f: " ++ show (x, y)) $ x + y

The function f is called more than once per update of the single input, even though it is unnecessary to call it more than once. Is it possible to optimize the Discrete type to avoid this?

Most likely yes, but I don't know how to perform this kind of optimization in the push-based implementation I currently have (version 0.4).

Basically, Discrete is implemented as a pair

type Discrete a = (Behavior a , Event a).

of a behavior (for recursion) and an update event. By duplicating g, the update event is also duplicated, resulting in two simultaneous update event occurrences for the event out. What's currently missing from reactive-banana is a combinator

calm :: Event a -> Event a

that removes all but the last event occurrence from a bunch of simultaneous events. This would allow us to optimize the Discrete data type. The combinator seems to be safe from a semantic point of view.

[gcross]

Just to clarify, you are saying here that your intent is not merely to optimize Discrete while keeping its current semantics, but rather to change its semantics in a significant (though honestly, probably better) way as part of the process of optimizing it, right?

[gcross]

By-the-way, the more I have been thinking about the possible consequences of simultaneous events in my own event networks, the more that calm seems like it would be a very helpful combinator. :-)

[HeinrichApfelmus]

Just to clarify, you are saying here that your intent is not merely to optimize Discrete while keeping its current semantics, but rather to change its semantics in a significant (though honestly, probably better) way as part of the process of optimizing it, right?

Well, I foreshadowed the intended semantics in the documentation: "Simultaneous events may be pruned for efficiency reasons." But yes, the changes event will only contain the latest update in the next version. This is what you would expect from a Behavior, anyway.

[gcross]

That's fine, I was just making sure I understood this properly because it is a very significant change, as at the moment I have to code very cautiously using Discretes or in some cases avoid them altogether precisely because events are fired with "intermediate" results, and after your change I would not have to worry about this anymore. :-)

[HeinrichApfelmus]

Done! Commit 78bd983 in the development branch now contains the desired functions collect and spill.

[HeinrichApfelmus]

There, now it's done. The Discrete type will probably be merged into the Behavior type as issue #22 suggests, but it can't hurt to do it anyway.