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.
Ba × Bb ≅ Ba × b
Ea × Eb ≅ Ea + 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
(⊕) in place of
mplus. We’ll see in a moment that
mplus give a nicer symmetry.
To separate a sum event into two, use
joinMaybes ∷ MonadPlus m ⇒ m (Maybe a) → m a
unmixEither ∷ Event (Either c d) → (Event c, Event d)
unmixEither ecd = (filt left, filt right)
filt f = joinMaybes (liftM f ecd)
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
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.
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')
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)
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
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
(<*>) build on other generally useful combinators. In contrast, my previous
(<*>) definition is recursive and uses the representation of reactive values and events.