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 arrow-style formulations, as in Fruit and Yampa. Those systems expose signal functions in the programming interface, but relegate events and time-varying 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 getting-started information at the arrows page.
This post explores and presents a few arrow-friendly formulations of reactive systems.
- 2008-02-06: Cleaned up the prose a bit.
- 2008-02-09: Simplified chatter-bot filtering.
- 2008-02-09: Renamed for easier topic recognition (was “Invasion of the composable Mutant-Bots”).
- 2008-02-10: Replaced
compsby the simpler
concatMBfor sequential chatter-bot composition.
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.
Although, the main attraction is the
Arrow interface, Let’s look at some other classes as well.
Functor and Applicative
Applicative instances for
StreamBot i are immediate because
StreamBot is an arrow.1 Therefore, for stream-bots,
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
What semantics do we get from the
fmap f bot,
fgets applied to each output of
pure x, each input triggers an
fbot <*> xbot, the same input stream is passed to each of
xbot. The functions coming out of
fbotare applied to the corresponding arguments coming out of
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
join would have to be fed the same, full input stream, which would lead to a tremendous time-space leaks.
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 stream-bots as a special case.
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.
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
Unfortunately, the stream-based representation (
Stream a -> Stream b) does not statically enforce the one-input-one-output property, i.e., it can represent bots that ignore some inputs and go Chatty-Cathy 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 well-behaved 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.
arrows package already contains our mutant-bots, again in generalized to an arrow transformer:
newtype Automaton (~>) a b = Automaton (a ~> (b, Automaton (~>) a b)) instance Arrow (~>) => Arrow (Automaton (~>)) where ...
Automaton is a stream transformer, the
Monoid instances mentioned above for
StreamArrow all apply to
Automaton as well.
So all that’s left for us is specializing:
type MutantBot = Automaton (->)
Now that I’ve praised mutant-bots 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 stream-bots for allowing this very freedom, we’ll want to proceed carefully. The stream-bots run all of the outputs together, but our choosy-bots will produce one optional output per input and then mutate. Instead of manufacturing a whole new bot line, we’ll ask the mutant-bots to simulate choosy-bots. Rather than using
Maybe directly, we’ll use
First, which is a wrapper around
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)! Choosy-bots 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
In this derived instance,
mempty stays silent, no matter what input, while
botA `mappend` botB reacts according to whichever of
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
When merged choosy-bots 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 chatter-bots.
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 chatter-bot, 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 mutant-bot’s
first, which makes a
MutantBot (a,c) ([bs],c). Just share the
c with each
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 mutant-bot 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 multi-responses into one.
concatMB :: MutantBot b [c] -> MutantBot [b] [c] concatMB bot = Automaton $ bs -> (concat *** concatMB) (steps (bs,bot))
concatMB function is just what we need for sequential chatter-bot composition:
Chatter ab >>> Chatter bc = Chatter (ab >>> concatMB bc)
comp be generalized beyond lists? If so, maybe we could unify and generalize choosy- and chatter-bots.
I like these chatter-bots so much that I’m giving them a prettier name:
type (:->) = ChatterBot
Chatter-bots 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
justC :: Maybe a :-> a
Nothing gets dropped, and the
Just constructors are stripped off what’s left. The implementation is very simple. The underlying mutant-bot converts
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
filterC p = arr f >>> justC where f a | p a = Just a | otherwise = Nothing
One could also define
justC in terms of
These two functions correspond to
joinMaybes discussed in “A handy generalized filter“.
Comparing arrow and non-arrow 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
Monad. For instance, for
(<*>) combines all pairs of occurrences (like the list instance), while for
(<*>) 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
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 multi-threading.”
Finally, I wonder how efficient these bots are at not reacting to inputs. In Reactive, if an event occurrence gets filtered out, propagation stops. Chatter-bots continue to propagate empty values lists and bot non-mutations.
A template for arrow-based 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 ($))
WrappedArrowtype wrapper uses essentially these instances. ↩