## Reactive normal form

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*.

## Reactive values

### Switching

As mentioned previously, the `stepper` function corresponds directly to the representation of `Reactive`.

``````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) `join`:

``````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 `stepper`.

### Functor

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
``````

The `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 `fmap` on `Future` with `fmap` on `Reactive`.

``````instance Functor Event where
fmap f (Event fut) = Event ((fmap.fmap) f fut)
``````

### Applicative

The `Functor` definitions for `Reactive` and `Event` are straightforward, because the `Stepper` structure is easily preserved. A more challenging case is `Applicative`.

``````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 `liftA2`, `liftA3`, etc. Consider `u == liftA2 f r s` or, equivalently, `u == pure f <*> r <*> s`, where `r` and `s` are reactive values, with initial values `r0` and `s0`, respectively. (The `(<*>)` operator is associates to the left.) The initial value `u0` of `u` is `f r0 s0`. If `r` changes from `r0` to `r1`, then the new value of `pure f <*> r` will be `f r1`, which then gets applied to `s0`, i.e., `u1 == f r1 s0`. However, if instead `s` changes from `s0` to `s1`, then `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 `switcher`:

``````r `switcher` er = join (r `stepper` er)
``````

How does `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)
``````

where `joinR` is `join` for reactive values:

``````joinR :: Reactive (Reactive a) -> Reactive a
``````

Defining `joinR` is similar to `(<*>)` above. For a reactive-reactive value `rr`, either `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'
``````

## Dynamic optimization

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 `r` and `s` quiesce. Once reactive values quiesce, no more computational resource is devoted to them.

## Events

The definitions above are mainly for reactive values. What about functional events?

### Monoid

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 `e` and `e'`.

``````instance Monoid (Event a) where
mempty  = Event mempty
Event fut `mappend` Event fut' = Event (fut `merge` fut')
``````

This `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')
``````

The `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.

The `Applicative` and `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 `f` of `ef` and occurrences `x` of `ex`. See the source code for details.

## Conclusion

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.