Functional reactive chatterbots
In a few recent posts, I’ve been writing about a new basis for functional reactive programming (FRP), embodied in the Reactive library. In those posts, events and reactive values are (first class) values. A reactive system able to produce outputs from inputs might have type Event a > Event b
or perhaps Reactive a > Reactive b
.
Although I’m mostly happy with the simplicity and expressiveness of this new formulation, I’ve also been thinking about arrowstyle formulations, as in Fruit and Yampa. Those systems expose signal functions in the programming interface, but relegate events and timevarying values (called “behaviors” in Fran and “signals” in Fruit and Yampa) to the semantics of signal functions.
If you’re not familiar with arrows in Haskell, you can find some gettingstarted information at the arrows page.
This post explores and presents a few arrowfriendly formulations of reactive systems.
Edits:
 20080206: Cleaned up the prose a bit.
 20080209: Simplified chatterbot filtering.
 20080209: Renamed for easier topic recognition (was “Invasion of the composable MutantBots”).
 20080210: Replaced
comps
by the simplerconcatMB
for sequential chatterbot composition.
Streambots
Let’s look at some possibilities for formulating reactive systems. The simplest formulation we might try is a function that maps an input stream to output stream. Fortunately, Ross Paterson’s arrows
package comes with an arrow transformer that adds stream inputs and outputs to any arrow. The instance definitions are very like MapTrans
in Arrows and computation.
newtype StreamArrow (~>) b c = Str (Stream b ~> Stream c)
instance Arrow (~>) => Arrow (StreamArrow (~>)) where ...
In our case, the function arrow suffices:
type StreamBot = StreamArrow (>)
Let’s assume for now that every input triggers exactly one output. In a while, we’ll see that this assumption is easily relaxed, so there’s really no loss of generality.
Other classes
Although, the main attraction is the Arrow
interface, Let’s look at some other classes as well.
Functor and Applicative
Functor
and Applicative
instances for StreamBot i
are immediate because StreamBot
is an arrow.^{1} Therefore, for streambots,
fmap :: (b > c) > StreamBot a b > StreamBot a c
pure :: o > StreamBot i o
(<*>) :: StreamBot i (a > b) > StreamBot i a > StreamBot i b
These interfaces may sometimes be convenient in place of the Arrow
interface.
What semantics do we get from the Functor
and Applicative
instances?
 In
fmap f bot
,f
gets applied to each output ofbot
 In
pure x
, each input triggers anx
out.  In
fbot <*> xbot
, the same input stream is passed to each offbot
andxbot
. The functions coming out offbot
are applied to the corresponding arguments coming out ofxbot
.
Note: the semantics of (<*>)
is very different from (<*>)
on events in the Reactive library, as described in Reactive values from the future. Events work like lists, while bots work like streams.
Monad
I don’t know if there’s a useful or practical Monad
instance for StreamBot i
that is consistent with the Applicative
instance (i.e., with ap == (<*>)
). I think each new bot to come out of (>>=)
or join
would have to be fed the same, full input stream, which would lead to a tremendous timespace leaks.
Monoid
Applicative functors (AFs) give rise to monoids through lifting. A general declaration would be
instance (Applicative f, Monoid o) => Monoid (f o) where
mempty = pure mempty
mappend = liftA2 mappend
Such an instance would overlap tremendously, but you can use it as a template. For example (using f = StreamArrow (~>) i
),
instance Monoid o => Monoid (StreamArrow (~>) i o) where
mempty = pure mempty
mappend = liftA2 mappend
which applies to streambots as a special case.
So, mappend
runs two bots in parallel, giving them the same inputs and combining each pair of outputs with mappend
(on output values). Of course, it only works when the output type in a monoid.
Mutantbots
So far we’ve assumed that every input triggers exactly one output. This assumption is critical in ensuring that (<*>)
combines functions and arguments resulting from the same input. The same requirement arises with (***)
and even first
in the Arrow
instance.
Unfortunately, the streambased representation (Stream a > Stream b
) does not statically enforce the oneinputoneoutput property, i.e., it can represent bots that ignore some inputs and go ChattyCathy over others.
We could maintain a feverish vigilance watching for rogue StreamBots, perhaps post guards working in shifts around the clock. But fatigue sets in, and we could never be really confident. Rather than losing sleep, let’s look for a representation that guarantees wellbehaved bots.
What representation could we use instead? We want one output per input, so let’s make our bot be a function from a single value, producing a single value. After that input and output, we’d like another opportunity for an input, which would lead to another output and another opportunity for input, and so on:
a > (b, a > (b, a > (b, ...)))
or, in recursive form:
newtype MutantBot a b = Mutant (a > (b, MutantBot a b))
As this type definition shows, an input leads a possible bot mutation, as well as an output.
This bot formulation corresponds to a Mealy machine, a classic automaton style for string transducers.
Ross’s arrows
package already contains our mutantbots, again in generalized to an arrow transformer:
newtype Automaton (~>) a b =
Automaton (a ~> (b, Automaton (~>) a b))
instance Arrow (~>) => Arrow (Automaton (~>)) where ...
Because Automaton
is a stream transformer, the Functor
, Applicative
, and Monoid
instances mentioned above for StreamArrow
all apply to Automaton
as well.
So all that’s left for us is specializing:
type MutantBot = Automaton (>)
Choosy bots
Now that I’ve praised mutantbots for reliably producing a single output per input, I want to change the rules and drop that restriction. Let’s give our bots freedom to choose whether or not to respond to an input. Then we can formulate things like filtering (as in stream fusion). For instance, a bot might respond only to arrow keys.
Since we just dissed streambots for allowing this very freedom, we’ll want to proceed carefully. The streambots run all of the outputs together, but our choosybots will produce one optional output per input and then mutate. Instead of manufacturing a whole new bot line, we’ll ask the mutantbots to simulate choosybots. Rather than using Maybe
directly, we’ll use First
, which is a wrapper around Maybe
:
newtype ChoosyBot i o = Choosy (MutantBot i (First o))
newtype First a = First (Maybe a)  (in Data.Monoid)
Cooperation and disagreements
I mentioned above that MutantBot i
is a monoid, in which mappend
feeds inputs to two bots and merges their outputs with mappend
(on the output type). We’re in luck (or forethought)! Choosybots use First o
as output, which is a monoid for all o
types. Thus we can derive the Monoid
implementation automatically, simply by adding “deriving Monoid
” to the ChoosyBot
definition.
In this derived instance, mempty
stays silent, no matter what input, while botA `mappend` botB
reacts according to whichever of botA
or botB
has a response. In case both respond, mappend
favors the first bot. To favor botB
instead, we could have used Last
in place of First
in defining ChoosyBot
.
Chatterbots
When merged choosybots react to the same input, one response gets lost. The representation itelf insists on picking only one response. Instead of choosing, we can combine responses into a list. The Monoid
instance on lists does exactly the combination we want and can be lifted directly to chatterbots.
newtype ChatterBot i o = Chatter (MutantBot i [o]) deriving Monoid
We still have to show that ChatterBot
is an arrow.
instance Arrow ChatterBot where ...
To make an i > o
function into a chatterbot, just wrap up the outputs as singleton lists (with pure
on lists):
arr h = Chatter (arr (pure . h))
We can build first
out of the representation mutantbot’s first
, which makes a MutantBot (a,c) ([bs],c)
. Just share the c
with each b
in bs
.
first (Chatter f) = Chatter $
first f >>> arr ( (bs,c) > [(b,c)  b < bs])
The key for sequential composition is an operation that feeds a list of inputs to a mutantbot and collects the outputs and the final mutant.
steps :: ([i], MutantBot i o) > ([o], MutantBot i o)
steps (is,bot) =
first reverse $ foldl step ([], bot) is
where
step (os, Automaton f) i = first (:os) (f i)
With this utility, we can define a way to bundle up several multiresponses into one.
concatMB :: MutantBot b [c] > MutantBot [b] [c]
concatMB bot = Automaton $ bs >
(concat *** concatMB) (steps (bs,bot))
The concatMB
function is just what we need for sequential chatterbot composition:
Chatter ab >>> Chatter bc = Chatter (ab >>> concatMB bc)
Question: can comp
be generalized beyond lists? If so, maybe we could unify and generalize choosy and chatterbots.
I like these chatterbots so much that I’m giving them a prettier name:
type (:>) = ChatterBot
Filtering
Chatterbots can filter out values to which they don’t want to respond. One simple means is analogous to filter
on lists, taking a predicate saying which elements to keep:
filterC :: (a > Bool) > a :> a
Another filtering tool consumes Maybe
values:
justC :: Maybe a :> a
Each Nothing
gets dropped, and the Just
constructors are stripped off what’s left. The implementation is very simple. The underlying mutantbot converts Nothing
with []
and Just a
with [a]
. Luckily, there’s a standard function for that conversion.
justC = Chatter (arr maybeToList)
It’s then easy to define filterC
in terms of justC
.
filterC p = arr f >>> justC
where
f a  p a = Just a
 otherwise = Nothing
One could also define justC
in terms of filterC
.
These two functions correspond to filterMP
and joinMaybes
discussed in “A handy generalized filter“.
Comparing arrow and nonarrow approaches
Philosophically, I like that the arrow approach formalizes not only the output half of a behavior but also the input (sensory) half. I’ve long believed this formalization offers to solve the spatial/temporal modularity problems of the original Fran (inherited from TBAG). (I experimented with these issues in Fran but didn’t write it up, and I don’t think they’ve been addressed meanwhile. Subject for another post.) It also has implementation benefits.
When using the arrow style, I miss flexibility and compositionity of types. For instance, in Reactive, I can use Reactive a > Reactive b > Reactive c
for a reactive system with two input sources. As far as I know, arrows force me to encode every interface into a transformation of a single input source to a single output source. In this case, I can use the (un)currying isomorphism and then the isomorphism of (Reactive a, Reactive b)
with Reactive (a,b)
. For events instead of reactive values, that latter isomorphism does not hold. Instead, (Event a, Event b)
is isomorphic to Event (Either a b)
. (Magnus Carlsson noted the mismatch between arrows and fudgets, remarking that “We need arrows that use sums as products”.)
I also miss the flexibility to choose between events and reactive values. Though similar, they have some very useful differences in their instances of Applicative
and Monad
. For instance, for Event
, (<*>)
combines all pairs of occurrences (like the list instance), while for Reactive
, (<*>)
samples the function and argument for the same time (like the function instance).
The bots described above mix some semantics from events and some from reactive values. The synchronous Applicative
corresponds to reactive values, while the monoid is like that of Event
.
One thing I like a lot about the implementations in this post, compared with Reactive, is that they do not need any concurrency, and so it’s easy to achieve deterministic semantics. I don’t quite know how to do that for Reactive, as mentioned in “Future values via multithreading.”
Finally, I wonder how efficient these bots are at not reacting to inputs. In Reactive, if an event occurrence gets filtered out, propagation stops. Chatterbots continue to propagate empty values lists and bot nonmutations.

A template for arrowbased functors and applicative functors:
 Standard Functor & Applicative instances for arrows. instance Arrow (~>) => Functor ((~>) i) where fmap = (^<<) instance Arrow (~>) => Applicative ((~>) i) where pure x = arr (const x) fbot <*> xbot = fbot &&& xbot >>> arr (uncurry ($))
The
WrappedArrow
type wrapper uses essentially these instances. ↩
Conal Elliott » Blog Archive » Accumulation for functional reactive chatterbots:
[…] About « Functional reactive chatterbots […]
9 February 2008, 9:47 pmConal Elliott » Blog Archive » Functional reactive partner dancing:
[…] The code described (with documentation and examples) here may be found in the new, experimental library Bot (which also covers mutantbots and chatterbots). […]
11 February 2008, 10:16 pmConal Elliott » Blog Archive » Pairs, sums, and reactivity:
[…] Functional reactive chatterbots […]
17 February 2008, 10:18 pm