## Applicative bots

In Functional reactive partner dancing, I mentioned that (a) the partially applied leading and following types have boilerplate `Applicative`

instances, and (b) the leading type corresponds to varying (reactive) values. Today I realized that those boilerplate instances are not very useful, and that they *do not* correspond to the `Applicative`

instance of `Reactive`

. In this post, I give a useful `Applicative`

instance that does correspond to the `Reactive`

instance. The instance definition is expressed in terms of the pair editor bot shown at the end of the “dancing” post, which seems to have a variety of applications.

The `Applicative`

instance has one awkward aspect that suggests a tweak to the formulation of leading. I give simplified versions of pair editing and `Applicative`

for the revised type. This change is in version 0.1 of the Bot libary.

*Edit 2008-02-15*: added FRP tags; prose tweak.

### Oops

The multi-output versions of leading and following are formulated simply as the single-output versions, with a list-valued output type:

```
newtype a :-> b = Follows (Follow a [b])
newtype a :>- b = Leads (Lead a [b])
```

Partially applied, each of these types is a sort of composition of type constructors. For instance, `(:->) a`

is the type composition of `Follow a`

and `[]`

. Since both of those type constructors are applicative functors, there are standard definitions of `Functor`

and `Applicative`

.

```
instance Functor ((:->) i) where
fmap f (Follows z) = Follows ((fmap.fmap) f z)
instance Applicative ((:->) i) where
pure x = Follows ((pure.pure) x)
Follows f <*> Follows x = Follows (liftA2 (<*>) f x)
```

and similarly for `(:>-) i`

.

In fact, these instance templates are abstracted into instances for the type composition operator `(:.)`

found in TypeCompose, so we can get the four instances for free if we define

```
type (:->) a = Follow a :. []
type (:>-) a = Lead a :. []
```

While the `Functor`

instances work fine, the rub (which I didn’t realize when writing the “dancing” post) is that the `Applicative`

instances are not what I want. They delegate to the `Applicative`

instances for `Follow a`

and for `[]`

. The result is that each output of `lf <*> lx`

is the list of `f x`

for all `f`

in the (list-valued) `lf`

output at that point and all `x`

in the (list-valued) `lx`

output. In particular, the `lf <*> lx`

will have an output only when *both* `lf`

and `lx`

have simultaneous outputs.

Instead, I’d like `lf <*> lx`

to have an output whenever *either* `lf`

or `lx`

has an output. If `lf`

has an output `f`

, I want to output `f x`

, where `x`

is the most recent `lx`

output. Similarly, if `lx`

has an output, I want to output `f x`

, where `f`

is the most recent `lf`

output. This behavior is exactly how `Applicative`

works for `Reactive`

, as described in reactive-normal-form.

### A solution and a problem

At the end of Functional reactive partner dancing, I showed a tool that is related to the desired `Applicative`

behavior.

```
editPairF :: (c,d) -> Either c d :-> (c,d)
```

Given an initial pair, `editPairF`

accepts replacements of either the first or second element and produces updated pairs, remembering the previous values. Since memory is involved, `editPairL`

is defined in terms of the generic accumulation combinator `accumF`

.

Let’s put `editPairF`

to work, to pair up two follows into a pair-valued follow. A new pair is output whenever either element gets output.

```
pairF :: (b,c) -> a:->b -> a:->c -> a:->(b,c)
pairF bc ab ac = (Left <$> ab) `mappend` (Right <$> ac) >>> editPairF bc
```

We had to supply the initial pair here, because follows don’t have initial values. Leads do, however, so the lead-pairing function has a simpler-looking type:

```
pairL :: a:>-b -> a:>-c -> a:>-(b,c)
```

The definition of `pairL`

works in terms of `pairF`

. The extra work involves disassembling and reassembling leads into and from initial values and follows.

```
ab `pairL` ac =
leads (liftA2 (,) bs cs) $ pairF (b,c) abf acf
where
(bs,abf) = splitL ab
(cs,acf) = splitL ac
-- Oh dear. b & c might not be well-defined
b = last bs
c = last cs
```

The awkward bit here is that, as formulated, a multi-lead (`a :>- b`

) could have multiple values even initially. For that reason, I (a) use a cross product (`liftA2 (,)`

) for the initial pairs, and (b) extract a single value from each lead to use in the pair-valued lead’s initial value. This second consideration is worse than awkward; it will fail if either initial value list is empty.

Is it really useful for a lead to have an initial *list* of values? Not that I know of. I allowed the flexibility because it made the type definitions so simple and uniform, which I’ve found has a decisive impact on the simplicity of code that works on the type.

Placing the initial-list problem aside for now, here is the simple and useful Applicative instance for leads. The `pure`

method makes a lead with an initial value an no future reponses. The `(<*>)`

method uses `pairL`

above to make a lead whose outputs are function/argument pairs, and then maps uncurried function application onto the pairs to get out the results.

```
instance Applicative ((:>-) i) where
pure x = leads [x] mempty
lf <*> lx = uncurry ($) <$> (lf `pairL` lx)
```

What about `(:->)`

(following)? I don’t think an `Applicative`

instance like the leading one can exist, due to lack of initial values. Perhaps there is an `Applicative`

instance corresponding to the one on Event (combining all pairs of occurrences over time).

### A tweak, and we’re back to safe & elegant

The difficulty with `pairL`

comes from a feature of dubious value, namely having an initial list of values rather than exactly one initial value. Let’s consider removing that flexibility. Replace

```
newtype a :>- b = Leads (Lead a [b])
```

with

```
newtype a :>- b = Leads (b, a :-> b)
```

The pairing combinator for leads is now simpler. It’s also bomb-proof, since it has initial single values instead of lists:

```
pairL :: a:>-b -> a:>-c -> a:>-(b,c)
Leads (a,fa) `pairL` Leads (b,fb) =
Leads ((a,b), pairF (a,b) fa fb)
```

And we have simple and (I think) trouble-free instances:

```
instance Functor ((:>-) i) where
fmap f (Leads (b,fol)) = Leads (f b, fmap f fol)
instance Applicative ((:>-) i) where
pure x = Leads (x,mempty)
lf <*> lx = uncurry ($) <$> (lf `pairL` lx)
```

## Leave a comment