Conal Elliott

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 combinator:

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

or just

accum = scanlTl (flip ($))

Mutant-bots

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 accum:

accumM :: a -> MutantBot (a->a) a
accumM = scanlM (flip ($))

Chatter-bots

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 ($))

Examples

Here are a few examples of scanlC and accumC.

Keep a running count of inputs:

count :: a :-> Int
count = scanlC ( b _ -> b + 1) 0

Flip-flop between False and True:

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

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