Conal Elliott

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)

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