In Functional reactive chatter-bots, I described a few arrow-friendly formulations of functional reactive programming (FRP). This post shows how to define accumulation combinators and gives a few simple examples of their use.
Accumulators on lists
The various types of bots from the previous post all have in common that they map streams to streams. If the bots were simply functions on lazy lists, we would probably use the
scanl :: (b -> a -> b) -> b -> [a] -> [b] scanl op b0 [a1, a2, ...] == [b0, b0 `op` a1, (b0 `op` a1) `op` a2, ...]
Our bots wait for input before producing output, so we’d want to drop the first element of the result (
b0). (In a future post, we’ll meet some more assertive bots.) If we didn’t already have
scanl, we might implement this new behavior as follows:
scanlTl :: (b -> a -> b) -> b -> [a] -> [b] scanlTl _ _  =  scanlTl f b (a:as) = let b' = f b a in b' : scanlTl f b' as
I often use a variation that successively applies functions from a function stream.
accum :: a -> [a->a] -> [a] accum _  =  accum a (f:fs) = a' : accum a' fs where a' = f a
accum = scanlTl (flip ($))
To see how to incorporate
scanl into BotWorld, let’s start with the simpler mutant-bots. The implementation directly follows
scanlTl, except that we drop the empty case, since we assume our input streams to be infinite.
scanlM :: (b -> a -> b) -> b -> MutantBot a b scanlM f b = Automaton $ a -> let b' = f b a in (b', scanlM f b')
We can then make a mutant-bot version of
accumM :: a -> MutantBot (a->a) a accumM = scanlM (flip ($))
A chatter-bot is represented as a (
newtype-wrapped) mutant-bot whose output values are lists. For accumulation, we’ll have singleton (
pure) lists coming out.
scanlC :: (b -> a -> b) -> b -> (a :~> b) scanlC f b = Chatter $ pure <$> scanlM f b accumC :: a -> ((a->a) :~> a) accumC = scanlC (flip ($))
Here are a few examples of
Keep a running count of inputs:
count :: a :-> Int count = scanlC ( b _ -> b + 1) 0
flipFlop :: a :-> Bool flipFlop = scanlC ( b _ -> not b) False
Add up inputs:
sum :: Num a => a :-> a sum = scanlC (+) 0
Count the odd inputs:
coundOdd :: Integral a => a :-> Int coundOdd = filterC odd >>> count
Increment/decrement a counter (possibly both or neither), depending on whether inputs satisfy each of two predicates.
upDown :: forall a. (a -> Bool) -> (a -> Bool) -> a :-> Int upDown isUp isDown = (up `mappend` down) >>> accumC 0 where up, down :: a :-> (Int -> Int) up = filterC isUp >>> replace (+ 1) down = filterC isDown >>> replace (subtract 1) -- Respond to each input with the same value replace :: Arrow (~>) => b -> a ~> b replace b = arr (const b)
How are we doing, and where are we going?
I’m encouraged with how simply accumulation works out. Most of the pieces of Reactive have chatter-bot counterparts now. The implementation doesn’t require multi-threading (as Reactive uses), so it was easy to get purely deterministic semantics.
Still to come:
- Snapshot a varying value whenever an event occurs.
- A clear notion of varying values (in progress).
- GUI examples.
- Source code release.
- Work out how to use the arrow-styled interface with TV, which uses currying and pairing (in progress).