The post “Reactive values from the future” presented a simple formulation of functional events and reactive values, built on a functional notion of future values. In the current post, I’ll describe some of the implementation of events and reactive values*.
As mentioned previously, the
stepper function corresponds directly to the representation of
data Reactive a = Stepper a (Event a) stepper :: a -> Event a -> Reactive a stepper = Stepper
The representation of all other functions must therefore produce their result in terms of
stepper, which thereby serves as a kind of reactive normal form (RNF). The implementation can be understood as a set of rewrite rules that convert arbitrary reactive expressions into RNF. (These rewrite rules are all provably correct based on a simple semantics of events and reactive values.)
The more general switching form can be expressed in terms of
switcher and (monadic)
switcher :: Reactive a -> Event (Reactive a) -> Reactive a r `switcher` er = join (r `stepper` er)
We’ll see below how to reduce
join to a
As a simple example,
fmap f applies a function
f to a reactive value pointwise, which is equivalent to applying
f to the initial value and to each occurrence value.
instance Functor Reactive where fmap f (a `Stepper` e) = f a `stepper` fmap f e
Event functor is also easily defined. Recall that an event is a future reactive value:
newtype Event = Future (Reactive a)
We want to map a given function over that reactive value, which we can do by combining
instance Functor Event where fmap f (Event fut) = Event ((fmap.fmap) f fut)
Functor definitions for
Event are straightforward, because the
Stepper structure is easily preserved. A more challenging case is
instance Applicative Reactive where ...
First the easy part. A pure value
a becomes reactive by using
a as the initial value and
mempty as the (never-occuring) change event:
pure a = a `stepper` mempty
Consider next applying a reactive function to a reactive argument:
rf@(f `Stepper` Event futf) <*> rx@(x `Stepper` Event futx) = f x `stepper` Event fut where ...
The initial value is
f x, and the change event occurs each time either the function or the argument changes. If the function changes first, we will (in the future) apply a new reactive function to an old argument:
fmap ( rf' -> rf' <*> rx) futf
Similarly, if the argument changes first, we will apply an old reactive function and a new argument:
fmap ( rx' -> rf <*> rx') futx
Combining these two futures as alternatives:
... fut = fmap ( rf' -> rf' <*> rx ) futf `mappend` fmap ( rx' -> rf <*> rx') futx
A wonderful thing about this
(<*>) definition for Reactive is that it automatically caches the previous value of the function or argument when the argument or function changes. This caching property is especially handy in nested applications of
(<*>), which can arise either explicitly or through
liftA3, etc. Consider
u == liftA2 f r s or, equivalently,
u == pure f <*> r <*> s, where
s are reactive values, with initial values
s0, respectively. (The
(<*>) operator is associates to the left.) The initial value
f r0 s0. If
r changes from
r1, then the new value of
pure f <*> r will be
f r1, which then gets applied to
u1 == f r1 s0. However, if instead
s changes from
u1 == f r0 s1. In this latter case, the old value
f r0 of
pure f <*> r is passed on without having to be recomputed. The savings is significant for functions that do some work based partial applications.
Above we saw a simple definition of
r `switcher` er = join (r `stepper` er)
join work for
Reactive? Rather than using the standard definition of
join in terms of
(>>=), let’s do the reverse:
r >>= h = joinR (fmap h r)
join for reactive values:
joinR :: Reactive (Reactive a) -> Reactive a
joinR is similar to
(<*>) above. For a reactive-reactive value
rr or the reactive value that is the initial value of
rr changes first.
joinR ((a `Stepper` Event fut) `Stepper` e'@(Event fut')) = a `stepper` Event fut'' where -- If fut arrives first, switch and continue waiting for e'. -- If fut' arrives first, abandon fut and keep switching with new -- reactive values from fut'. fut'' = fmap (`switcher` e') fut `mappend` fmap join fut'
Operations on events and reactive values dynamically re-optimize themselves. For instance, the reactive value
fmap f r is known to quiesce (stop changing) when
r quiesces, which is knowable because futures have a special representation for the future that never comes. (Really, only easy common cases are optimized. An example of a hard-to-detect never-occuring event would be filtering out first the odd numbers and then the even numbers from an
Int-valued event.) Similarly, the reactive value
liftA2 f r s quiesces once both
s quiesce. Once reactive values quiesce, no more computational resource is devoted to them.
The definitions above are mainly for reactive values. What about functional events?
Events form a monoid:
mempty is the never-occurring event, which is represented by the never-occuring future, while
e `mempty` e' is an event consisting of all occurrences from
instance Monoid (Event a) where mempty = Event mempty Event fut `mappend` Event fut' = Event (fut `merge` fut')
merge operation combines two
Future streams into one.
merge :: Future (Reactive a) -> Future (Reactive a) -> Future (Reactive a) Never `merge` fut = fut fut `merge` Never = fut u `merge` v = (onFut (`merge` v) <$> u) `mappend` (onFut (u `merge`) <$> v) where onFut f (a `Stepper` Event t') = a `stepper` Event (f t')
mappend used in the definition of
merge is from
Future. It picks the earlier future and abandons the other. Thus the first of the two events to occur will contribute an occurrence value (
a), leaving a residual event, which is combined with the not-yet-occurring event.
Applicative and Monad
Monad instances for events are like those for lists, and unlike those for reactive values (given above). For instance, the occurrences of
ef <*> ex consist of
f x for all occurrences
ef and occurrences
ex. See the source code for details.
I’m happy with the simplicity of this new functional formulation of events and reactive values. While most previous FRP implementations used polling, Reactive is change-driven and so has the can be much more efficient. It also uses a dynamically self-optimizing representation.