This note continues an exploration of arrow-friendly formulations of functional reactive programming. I refine the previous representations into an interactive dance with dynamically interchanging roles of follow and lead. These two roles correspond to the events and reactive values in the (non-arrow) library Reactive described in a few previous posts. The post ends with some examples.
Dancing with Mealy machines
As mentioned in a previous post, Mealy-style automata (“bots”) can be given the following type:
a -> (b, a -> (b, a -> (b, ...)))
b are the types of inputs and outputs, respectively. The essence of Mealy machines is the alternation of consuming and producing values. The type ensures that exactly one output is delivered per input. In recursive form,
newtype a `MutantBot` b = Mutant (a -> (b, a `MutantBot` b))
which is a special case of Ross Paterson’s
Automaton arrow transformer.
These bots do nothing until prompted by an external partner. What kind of thing is that partner? Unlike our bots, it must have the ability to take initiative, i.e., to produce a value without itself being prompted. So we might say that the partner is leading, while the bot is following (or acting and reacting, or generative and receptive).
Once the partner has provided a value, the bot can then provide a reponse. After the bot’s reponse, there will be another value from the partner. Once this dance has begun, the roles of lead and follow are no longer static but rather trade back and forth fluidly.
We’ve seen the type of the bot:
a -> (b, a -> (b, a -> (b, ...)))
What is the type of the partner who can dance Lead to the bot’s Follow? Initially, while the bot waits for a value (follows), the partner provides one (leads). After that first step, the roles reverse.
(a, b -> (a, b -> (a, b -> ...)))
This Lead type matches the range of the Follow type, but with
b swapped. We can therefore type our bot friend as
a `Follow` b and its partner as
b `Lead` a, where
type a `Follow` b = a -> Lead a b type a `Lead` b = (b, Follow a b)
This formulation makes it clear that the bot and the partner are simply different phases of the same kind of process (though with swapped type parameters). While the bot is
a `Follow` b, the partner is
b `Lead` a; and while the bot is
a `Lead` b, the partner is
b `Follow` a.
Haskell won’t accept these mutually recursive types without at least one
data wrapper. We’ll use two.
newtype a `Follow` b = Follow (a -> Lead a b) newtype a `Lead` b = Lead (b, Follow a b)
Aside: I studied partner dancing pretty intensively a few years ago, during my mid-life sabbatical. One of my later teachers rocked my conception of dancing when he said that the roles of “lead” and “follow” are not rigid, but alternate fluidly between the parters. For instance the man (typically) initiates a movement (leads), which the woman (typically) responds to (follows). The roles then smoothly reverse: the man then follows her as she leads him through completion of the movement, when the roles reverse again.
Partially applied, both of these types are functors and applicative functors.
instance Functor (Follow a) where fmap f (Follow h) = Follow (fmap f . h) instance Applicative (Follow a) where pure b = Follow (const (pure b)) Follow h <*> Follow k = Follow $ a -> h a <*> k a instance Functor (Lead a) where fmap f (Lead (b, g)) = Lead (f b, fmap f g) instance Applicative (Lead a) where pure b = Lead (b, pure b) Lead (f,pf) <*> Lead (a,pa) = Lead (f a, pf <*> pa)
Since I’ve been playing with
Applicative and type compositions a lot lately, some patterns in this code jump out at me. It’s almost possible to get these four instances automatically, from very simple reformulations of
Lead. I’ll address those reformulations in another post.
Arrow instance for
Follow can be adapted easily from the
Arrow instance for
Automaton. I don’t think it’s possible to define an
Arrow instance for
Lead, however. Is it an instance of some other generic notion?
The type parameter order for
Lead is always received before generated. That order fits well with the type classes
Arrow, while the reversed parameter order would mesh with contra-variant functors. However, Control.Arrow provides its own contravariant map (and related goodies):
-- | Precomposition with a pure function. (^>>) :: Arrow (~>) => (b -> c) -> c ~> d -> b ~> d f ^>> a = arr f >>> a
By the way, I prefer infix operators over the traditional form (e.g.,
c ~> d vs
a c d). Keep in mind that “
->” binds less strongly than other infix operators.
Events and varying values
One of the puzzles I’ve had about arrow-based reactivity is how to distinguish between events and reactive values. The lead/follow dance provides an answer. Here are the definitions, from Reactive values from the future.
newtype Event b = Future (Reactive b) data Reactive b = Stepper b (Event b)
An event starts out in waiting mode–a sort of pregnant phase–until it gives birth to a reactive value. A reactive value initially has a value and then acts like an event. These two definitions are very like our
Reactive use futures, the arrow-based formulations have explicit inputs (of type
Now that I have this follow/lead perspective, I regret my choice of the name “
Reactive” for varying values. Now I see that events are initially reactive (receptive), while varying values are initially active (generative).
I’ve found it useful to allow any number of outputs in reaction to a single input. In particular, filtering eliminates outputs, and
mappend can combine outputs. This flexibility motivated chatter-bots. The implementation is simple: use a list-valued output type, rewrapping as another abstraction.
newtype a :>- b = Leads (Lead a [b]) newtype a :-> b = Follows (Follow a [b])
These types are also functors and applicative functors (when partially applied). The instances are boilerplate for any composition of applicative functors. The
Arrow instance is a straightforward adaption from the
ChatterBot instance given in Functional reactive chatter-bots.
Follow types are very similar to Fudgets-style stream processors, which provide output flexibility in a different way. I will compare these two approaches in an upcoming post.
The examples from Accumulation for functional reactive chatter-bots all work in the lead/follow setting, with changes to the function names. Those examples were follows, but are more useful as leads, which we can now do as well, thanks to lead versions of the accumulating combinators.
As another example, let’s maintain the product of two independently-changing numbers. In Reactive, we’d take two reactive (varying) values and return one:
Reactive Int -> Reactive Int -> Reactive Int
We’ll have to re-arrange this interface to fit into the
Arrow-style interface. As described earlier, a reactive value is simply a value and an event (analogous to a lead and a follow). A bit of currying, argument flipping, and uncurrying gives the type
(Int,Int) -> (Event Int, Event Int) -> Reactive Int
Next use the Event/pairing isomorphism:
(Int,Int) -> Event (Either Int Int) -> Reactive Int
which converts to a Lead:
prod :: (Int,Int) -> Either Int Int :>- Int
As first step, let’s decode the
Either-valued input into a pair-modifying function
updPair :: Either c d -> (c,d) -> (c,d) updPair (Left c') (_,d) = (c',d) updPair (Right d') (c,_) = (c,d')
Or, the functionally svelte
updPair = (first.const) `either` (second.const)
updPair, we can convert the
Either-encoded pair edits to editing functions, and then cumulatively apply those functions. (The
accumF function is like
accumC on chatter-bots.)
editPairF :: (c,d) -> Either c d :-> (c,d) editPairF cd = updPair ^>> accumF cd
We have all we need to make a Lead version of pair editing as well:
editPairL :: (c,d) -> Either c d :>- (c,d) editPairL cd = leads [cd] (editPairF cd)
Or, with some pointfree-fu,
editPairL = leads.pure <*> editPairF
leads is a convenience function:
leads :: [b] -> a :-> b -> a :>- b leads bs (Follows fol) = Leads (Lead (bs,fol))
prod example is now just a simple application of these generally useful pair editors.
prod = (fmap.fmap) (uncurry (*)) editPairL
fmap is for
(->) (Int,Int), and the second is for
(:>-) (Either Int Int).