haskell - Can reactive-banana handle cycles in the network?

Question

We have code like this:

 guiState :: Discrete GuiState
 guiState = stepperD (GuiState []) $
   union (mkGuiState <$> changes model) evtAutoLayout

 evtAutoLayout :: Event GuiState
 evtAutoLayout = fmap fromJust . filterE isJust . fmap autoLayout $ changes guiState

You can see that evtAutoLayout feeds into guiState which feeds into evtAutoLayout--so there is a cycle there. This is deliberate. Auto layout adjusts the gui state until it reaches an equilibrium and then it returns Nothing and so it should stop the loop. A new model change can kick it off again, of course.

When we put this together, though, we run into an infinite loop on the compile function call. Even if autoLayout = Nothing, it still results in a stack overflow during compile.

If I remove the union call in guiState and remove evtAutoLayout out of the picture...

 guiState :: Discrete GuiState
 guiState = stepperD (GuiState []) $ mkGuiState <$> changes model

it works fine.

Any suggestions?

Answer 1

The question

Does the reactive-banana library support recursively defined events?

has not only one, but three answers. The short answers are: 1. generally no, 2. sometimes yes, 3. with workaround yes.

Here the long answers.

1. The semantics of reactive-banana do not support defining an Event directly in terms of itself.

   This is a decision that Conal Elliott made in his original FRP semantics and I've decided to stick to it. Its main benefit is that the semantics remain very simple, you can always think in terms of

   type Behavior a = Time -> a
   type Event    a = [(Time,a)]
   

   I have provided a module Reactive.Banana.Model that implements almost precisely this model, you can consult its source code for any questions concerning the semantics of reactive-banana. In particular, you can use it to reason about your example: a calculation with pen & paper or trying it in GHCi (with some mock data) will tell you that the value evtAutoLayout is equal to _|_, i.e. undefined.

   The latter may be surprising, but as you wrote it, the example is indeed undefined: the GUI state only changes if an evtAutoLayout event happens, but it can only happen if you know whether the GUI state changes, which in turn, etc. You always need to break the strangulating feedback loop by inserting a small delay. Unfortunately, reactive-banana doesn't currently offer a way to insert small delays, mainly because I don't know how to describe small delays in terms of the [(Time,a)] model in a way that allows recursion. (But see answer 3.)

2. It is possible and encouraged to define an Event in terms of a Behavior that refers to the Event again. In other words, recursion is allowed as long as you go through a Behavior.

   A simple example would be

   import Reactive.Banana.Model
   
   filterRising :: (FRP f, Ord a) => Event f a -> Event f a
   filterRising eInput = eOutput
       where
       eOutput  = filterApply (greater <$> behavior) eInput
       behavior = stepper Nothing (Just <$> eOutput)
   
       greater Nothing  _ = True
       greater (Just x) y = x < y
   
   example :: [(Time,Int)]
   example = interpretTime filterRising $ zip [1..] [2,1,5,4,8,9,7]
   -- example = [(1.0, 2),(3.0, 5),(5.0, 8),(6.0, 9)]
   

   Given an event stream, the function filterRising returns only those events that are greater than the previously returned. This is hinted at in the documentation for the stepper function.

   However, this is probably not the kind of recursion you desire.

3. Still, it is possible to insert small delays in reactive-banana, it's just not part of the core library and hence doesn't come with any guaranteed semantics. Also, you do need some support from your event loop to do that.

   For instance, you can use a wxTimer to schedule an event to happen right after you've handled the current one. The Wave.hs example demonstrates the recursive use of a wxTimer with reactive-banana. I don't quite know what happens when you set the timer interval to 0, though, it might execute too early. You probably have to experiment a bit to find a good solution.

Hope that helps; feel free to ask for clarifications, examples, etc.

Disclosure: I'm the author of the reactive-banana library.