## Functional reactive partner dancing

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:

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

Next use the Event/pairing isomorphism:

which converts to a Lead:

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

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.

The first `fmap`

is for `(->) (Int,Int)`

, and the second is for `(:>-) (Either Int Int)`

.

## Conal Elliott » Blog Archive » Applicative bots:

[...] About « Functional reactive partner dancing [...]

12 February 2008, 10:30 pm## Finite State Machines | Engineer Sphere:

[...] Conal Elliott » Functional reactive partner dancing [...]

6 October 2009, 8:35 pm