Conal Elliott

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.

The code described (with documentation and examples) here may be found in the new, experimental library Bot (which also covers mutant-bots and chatter-bots).

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, ...)))

where a and 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 a and 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 newtype or 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.

Class instances

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 Functor and 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 Follow and Lead. I’ll address those reformulations in another post.

An 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 Follow and Lead is always received before generated. That order fits well with the type classes Functor, Applicative, and 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 Follow and Lead. Where Event and Reactive use futures, the arrow-based formulations have explicit inputs (of type a).

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

Getting chatty

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.

The Lead and 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.

Examples

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)

Using 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

where leads is a convenience function:

leads :: [b] -> a :-> b -> a :>- b
leads bs (Follows fol) = Leads (Lead (bs,fol))

Our prod example is now just a simple application of these generally useful pair editors.

prod = (fmap.fmap) (uncurry (*)) editPairL

The first fmap is for (->) (Int,Int), and the second is for (:>-) (Either Int Int).

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