Idea: add a combinator to track when a behavior is a different value

[ChristopherKing42]

I suggest a combinator with the following type signature.

updates :: Eq a => Behavior a -> Event (a, a)

When b changes, updates b will fire and return (current, next), where current is the current value and next is the different value it is changing into. nexr should be used with caution to avoid infinite loops.

Note for example that updates (a <$ b) should never fire even if b changes, because a <$ b will never sample different values.

[luke-clifton]

Similar to changes. Which might be suitable depending on your use case.

Also, usually achievable with a Dynamic, which is essentially a tuple of an Event and a Behavior. The event has the new value, while the behaviour will hold the previous value at a given instant.

[ocharles]

Unfortunately I don't think such a combinator is actually permitted by the model. Recall that a Behavior a is morally a Time -> a function, and Event a is [(Time, a)]. I don't see a way to accurately transform Eq a => Time -> a to [(Time, (a, a))]. We'd need to answer this question before anything else. I think as @luke-clifton says, what you might want instead is Dynamic.

[ChristopherKing42]

Hmm, Time is discrete, right? So in the model you loop over every time value until it changes. If f(t) ≠ f(next t), then the event contains (t, (f(t), f(next t)).

[ocharles]

No, time is continuous. https://hackage.haskell.org/package/reactive-banana-1.3.1.0/docs/Reactive-Banana-Model.html states:

The FRP model used in this library is actually a model with continuous time. However, it can be shown that this model is observationally equivalent to a particular model with (seemingly) discrete time steps, which is implemented here

But I don't quite know what this means 🤔

[ChristopherKing42]

Like, the actual implementation of the model represents behaviors as lists. And as long as behaviors are piecewise constant, detecting updates is still semantically meaningful (it's the set of discontinuities).

[luke-clifton]

It is desirable that behaviours appear continuous. Breaking that breaks the model.

[ChristopherKing42]

@luke-clifton

Hmm, what about a function that detects isolated discontinuities?

discontinuities :: Eq a => Behavior a -> Event (a, a)

With the current implementation, it would be the same as updates since every definable behavior is piecewise continuous. But if a continuous behavior is ever added (like a clock) it wouldn't trigger discontinuities because like the name says, it is only triggered by discontinuous changes. In particular, it is triggered with (left limit, right limit) when they both exist and are different.

Another name could be jumps because it detects "jumps" in the function.

[luke-clifton]

The thing is, Reactive Banana only samples behaviors on events anyway. So, you already have that event lying around, you may as well just re-use it (which is what a Dynamic gives you). The model explicitly doesn't know anything about the discontinuities of raw behaviors.

Take, for example, the fromPoll function. You might build a behavior like fromPoll getCurrentTime. getCurrentTime has a discontinuity every second, but Reactive Banana is only going to poll it when some other event occurs in the network. Without the events, reactive banana has no idea that the above behavior has a discontinuity every second, and it would not know to generate an event.

If we just rely on internal events for sampling, and want our discontinuities function anyway, well, now the events generated depend on the sampling rate, i.e. on other events occurring in the network. If the network was busy, we would see a jittery event every second, but if the network was quiet, we would see no events. This would be a very surprising behavior (heh).

[luke-clifton]

(err, pretend that the getCurrentTime function, is accurate to the second, for my wording above, it's obviously even weirded with higher resolution clocks)

[ChristopherKing42]

Oh, I forgot about fromPoll. It's kind of cursed to think of there being a time function from a continuous domain to the pure (non-io) integer values, but that is how fromPoll timeInSecondsIO gets modeled. I have no idea how you'd implement discontinuities then. You can't sample an IO action continuously.

The only thing I can think of is you somehow knew the maximum sampling frequency of the RAM, maybe that would suffice (what IO action could update faster than that)? idk

[ChristopherKing42]

(for pure values I know infinite search is possible (see this) but I think fromPoll does kill the idea)

Unless maybe you change fromPoll's requirements, requiring it's argument's samples to be continuous in time? fromChanges could still be used for behaviors from IO that are discontinuous.

[luke-clifton]

So, even with pure behaviours things get tricky, and you would need to begin relying on numerical methods to find discontinuities. These methods would also rely on the sampling behaviour, and could miss short discontinuities.

Once you start down this road, you are no longer in interactive FRP, but more like an integration system based on FRP. I did have a prototype of such a library for modelling dynamical systems before, and the only way to trigger events was from zero crossings of the behaviour. It would also adjust the sampling frequency intelligently and perform a bisection search, jumping backwards in time as required to get within a desired accuracy of the root. While it's an interesting way of creating dynamical systems, one must always be on the lookout for tricky sample rate dependent gotchas.

The beauty of continuous time FRP is that you just do not have to worry about any of that ever.

Also, when sampling from the real world, it's kinda hard to guarantee anything. Using fromPoll to read an analogue signal (continuous!) from the output of a push button is a perfectly valid use case if you don't actually need an edge trigger, you might even debounce and round it and convert it to a bool inside the FRP network. But if you change your mind about the edge triggered thing, you might get upset to find that discontinuities only works on some behaviours.

[ChristopherKing42]

So, even with pure behaviours things get tricky, and you would need to begin relying on numerical methods to find discontinuities. These methods would also rely on the sampling behaviour, and could miss short discontinuities.
...
The beauty of continuous time FRP is that you just do not have to worry about any of that ever.

This post talks about exhaustive search, so you shouldn't be able to miss any discontinues, even the short ones. There is no sampling rate. It works very differently than a float or double based solution, since those are discrete types. (tl;dr, you have a function that constructs a potential solution that is correct if any solution exists. It works corecursively: it finds a potential solution that starts with zero, and if that solution fails, it returns the potential solution starting with one instead. Using this function, you can check if there is a solution by searching just one value, the potential solution from the function.)

That being said, it appears that both updates and discontinuities are incompatible with fromPoll, so I'm going to close this issue. I have a much better understanding of the problems with these type of combinators though (I was kind of wondering why it wasn't already in the library), thanks!

[ChristopherKing42]

@luke-clifton

But if you're curious about the details for how it would work for FRP without IO, here is the basic idea. I'll base it on this post, which is what the infinite search monad post was based on.

Time would be (Integer, Cantor), where the second part represents the binary expansion after the integer part (so (3, [\n -> cycle [Zero, One] !! n)) represents 3 and a third). A behavior is a function with this as the domain.

Then you get something like

updates :: Eq a => (Integer, Cantor) -> ((Integer, Cantor) -> a) -> [((Integer, Cantor), a)]
updates start behavior = case search of
    Just c -> [((fst start, c), behavior (fst start, c))] : updates (fst start, c) behavior
    Nothing -> updates (fst start + 1, const Zero)
    where
        start_val = behavior start
        next = search (\c -> if behavior (fst start, c) == start_val //search is defined in the blog post
then false
else c > snd start //`>` can be a given a definition that is total in this context since we know c ≠ snd start in this branch)

Note that search is much more efficient than brute force (which would take infinite time, but even for the finite analogues it's way faster) because it exploits laziness. It's faster if you use a more efficient find (such as find_viii).