## Pairs, sums, and reactivity

I’ve been noodling over a difference between behaviors (functions of time) and events (sequences of time/value pairs). A product of behaviors is isomorphic to a behavior of products, but a product of events is isomorphic to an event of *sums*.

*B*_{a} × *B*_{b} ≅ *B*_{a × b}

*E*_{a} × *E*_{b} ≅ *E*_{a + b}

A similar property has been noted for Fudgets-like stream processors.

Behaviors (or "reactive values") and events are inter-related. In particular, we can make a behavior from an initial value and an event, using the `stepper`

function. If we want to use `stepper`

with a pair value, we’d have to use a pair-valued event. However, it’s often more convenient and efficient to work with pair of separate change events, or (using the event pair/sum isomorphism) a sum-valued event.

This post plays with another perspective on sum types for events and stream processors. It can also apply to bots.

### Pairs and sums

Let’s take a look at the event pair/sum isomorphism. To mix two events into a single sum event, simply left- or right-tag the events and merge them:

`mixEither ∷ (Event c, Event d) → Event (Either c d)`

mixEither (ec,ed) = liftM Left ec `mplus` liftM Right ed

In this definition, I could have used `fmap`

in place of `liftM`

and/or `(⊕)`

in place of `mplus`

. We'll see in a moment that `liftM`

and `mplus`

give a nicer symmetry.

To separate a sum event into two, use `joinMaybes`

.

`joinMaybes ∷ MonadPlus m ⇒ m (Maybe a) → m a`

`unmixEither ∷ Event (Either c d) → (Event c, Event d)`

unmixEither ecd = (filt left, filt right)

where

filt f = joinMaybes (liftM f ecd)

The functions `left`

and `right`

are `Maybe`

-valued extractors for sum types.

`left ∷ Either c d → Maybe c`

right ∷ Either c d → Maybe d

The mixer and unmixer actually have much more general types:

`mixEither ∷ MonadPlus m ⇒ (m a, m b) → m (Either a b)`

`unmixEither ∷ MonadPlus m ⇒ m (Either c d) → (m c, m d)`

The simplicity and symmetry these typings motivated my choice of `liftM`

and `mplus`

above.

In this more general setting, `mixEither ∘ unmixEither`

might not be the identity. For lists, all of the lefts will end up before all of the rights. Even for events, `mixEither ∘ unmixEither`

can re-order simultaneous occurrences. I don't know how to get a genuine isomorphism.

### Pair editors

When using `stepper`

, the event argument indicates a *change* to the varying value. When the varying value is a pair, we'll often have change events for each pair member. Let's see how to weave those two events into a single pair-valued event.

The pair/sum isomorphism above says that a pair of events is equivalent to a sum-valued event. But what do we do with the sum event? The key idea is noted in *Functional reactive partner dancing*: convert the sum into a *pair editor*:

`updPair ∷ Either c d → (c,d) → (c,d)`

`updPair (Left c') (_,d) = (c',d)`

updPair (Right d') (c,_) = (c,d')

Equivalently,

`updPair = (first∘const) `either` (second∘const)`

Now we can go from a pair of events to an event of *pair editors*:

`pairEditE ∷ (Event c, Event d) → Event ((c,d) → (c,d))`

pairEditE = liftM updPair ∘ mixEither

If we want, we can also short-cut the whole sum business:

`pairEditE (ce,de) =`

liftM (first∘const) ce `mplus` liftM (second∘const) de

With either of these definitions, we have a much more general type:

`pairEditE ∷ MonadPlus m ⇒ (m c,m d) → m ((c,d) → (c,d))`

The next step is to apply successive functions from the pair-changing event, using an accumulation combinator. We'll need an initial value for the pair:

`pairE ∷ (c,d) → (Event c, Event d) → Event (c,d)`

cd `pairE` cde = cd `accumE` pairEditE cde

There's another way to dice up `pairE`

. A reactive value is determined by an initial value and change event, so we can restructure the arguments of `pairE`

into two reactive values. We also have an initial value for the combination, so we may as well produce a reactive value.

`pairR ∷ Reactive c → Reactive d → Reactive (c,d)`

(c `Stepper` ce) `pairR` (d `Stepper` de) =

(c,d) `stepper` pairE (c,d) (ce,de)

or, more directly:

`(c `Stepper` ce) `pairR` (d `Stepper` de) =`

(c,d) `accumR` pairEditE (ce,de)

Lovely!

### Pair editing and applicative functors

In a sense, we've gone to a lot of work for nothing. Since `Reactive`

is an applicative functor, we can also give this trivially easy and much more general definition:

`pairR ∷ Applicative f ⇒ f c → f d → f (c,d)`

pairR = liftA2 (,)

On the other hand, the `(<*>)`

method in the `Applicative`

instance given in *Reactive normal form* was tricky. We can now replace it with a simple definition in terms of `pairR`

(assuming we don't define `pairR`

in terms of `liftA2`

). Use `pairR`

to turn a reactive function and a reactive argument into a reactive function/argument pair. Then map uncurried function application to get `(<*>)`

:

`rf <*> rx = uncurry ($) <$> (rf `pairR` rx)`

I like how these new definitions of `pairR`

and `(<*>)`

build on other generally useful combinators. In contrast, my previous `(<*>)`

definition is recursive and uses the representation of reactive values and events.

## BMeph:

Uh, you have a minor typo on your second Reactive pair rewrite:

(c,d)

`accumR`

pairEditE (ce,de)still, very nice catch – thank you for the write-up!

17 February 2008, 10:15 pm## conal:

Fixed. Thanks!

17 February 2008, 10:19 pm