Understanding Haskell Arrows

1 Introduction

The concept of arrows is a generalized interface for structures of control, similar and related to monads. The arrow interface is more general, thus allowing some control structures, which cannot be expressed in the monadic framework. Also when using the common Glasgow Haskell Compiler (GHC) you can use the Arrows language extension, which gives you syntactic sugar inspired by do-notation.

This tutorial is an introduction to arrows and is aimed at the somewhat experienced Haskell programmer, who can write applications and understand monads at least as far as necessary to implement and use them. Particularly this is not an introduction to Haskell. I’m assuming that you understand:

Also note that this is not a quick-and-dirty tutorial. If you are under time pressure, you are wrong here. This introduction is for those, who want to understand and master arrows on a fundamental level.

I’m assuming a base library of version 4.0 or newer. Older base libraries had a slightly different arrow interface. Most notably they didn’t have the Control.Category module. Just get a recent version of the Haskell Platform, if you don’t have one already. You can also use your distribution’s package management system, if it provides somewhat up to date packages. GHC 6.12 should be enough.

Note: The source code of this tutorial is a Pandoc-compatible literate Haskell file. You can download it or view it online.

2 So what’s wrong with monads?

First let’s remind ourselves what a monad is. Roughly speaking a monad is an implementation of a certain control concept. You’ve got monads for computations, which

Monads are one of the most powerful abstractions used in Haskell. However, sometimes this power is a problem. To understand this we should get an idea of the relationship between monads and arrows first.

First of all, types with instances for the Category and Arrow type classes are arrows. For every monad there are trivial instances for these classes, so you can say that every monad can trivially be turned into an arrow (this requires a helper type, but let’s ignore that for now). The converse is false, so arrows are less expressive than monads, just like applicative functors are less expressive than monads. Then why in the world would we want to use arrows anyway? Or: What’s wrong with monads?

Well, nothing per se, if you do have a monad for your purpose, but not everything is a monad! Some useful control concepts cannot be expressed in the monadic framework. The problem is that monads need to provide the bind operation (>>=), for which there is no reasonable definition in some control concepts. We will concentrate on three of these concepts in depth in this tutorial:

We will use computations with some static meta-information attached to them as a motivating example for a control construct, which is powerful, but not a monad. The second example we will go into is automata, which form the basis of arrowized functional reactive programming (AFRP). Then we will turn all our arrows into arrow transformers, a generalization of monad transformers.

Finally by a small, notable change we will extend our automaton arrow transformer to become the wire arrow. This will lead us into the Netwire library, a powerful library for stateful declarative programming and functional reactive programming.

By the end of this tutorial you will have learned, when and how to write/use arrows. With automata and wires you will also have a powerful declarative concept for state-keeping without having to program imperatively.

3 Motivating example: Static information

To work with arrows you will want to import the Control.Arrow module, which comes with the base library. For defining custom arrows you should also import the Control.Category module. That module has generalized definitions of (.) and id, so you may want to import Prelude explicitly hiding the two. We also import some further modules and enable the Arrows extension for this tutorial:

{-# LANGUAGE Arrows #-}

module ArrowTutorial where

-- Minimum to work with arrows:
import Control.Arrow

-- You need these when defining your own arrows:
import Control.Category
import Prelude hiding ((.), id)

-- Further we need this for the tutorial:
import Control.Applicative

Please remember, this tutorial is written in literate Haskell, so we really need all of this here. If there is anything in the above code you don’t understand, just go with it for now.

The original motivation for arrows was static informations about parsers. While monadic parsers are reasonably fast, they lack an important feature: They cannot fail early, unless you (as the author of the parser) specifically program them to do so. It would be better, if the parser library could do this plumbing for you. It turns out that this is impossible in the monadic framework.

To illustrate this problem, we will use a simpler example: We will try to implement a special state monad: One that can tell, whether a given stateful computation is going to modify the state or not, i.e. whether it is going to use the put function. Even for a large composition of many stateful computations, it should still easily tell whether the composition has a put somewhere.

This information should be reliable and accessible without even having to run the stateful computation in question. Thus it should be static meta-information about the computation, which should not depend on the outcome of it. For our purposes we don’t require a compile time guarantee, just some way to get this information at run-time.

3.1 Nope, it’s not a monad

This is the traditional type for state monads:

newtype State' s a =
    State' { runState' :: s -> (a, s) }

For every state type s, the type State' s is a state monad. Then State' s a is the type for a computation that receives a state value of type s and returns some result of type a. Along with the result it also returns a possibly changed state value of type s. So this is a function from s to the tuple (a, s) (if you don’t understand this, really just look at the definition of State').

We will add our desired meta-information as a second argument to the State constructor.

data State s a =
    State {
      usesPut  :: Bool,
      runState :: s -> (a, s)
    }

Unlike regular state monads this one’s constructor takes an additional Bool value, which will tell whether the given function will actually modify the state. Let’s write computations for setting and retrieving the current state:

get :: State s s
get = State False (\s -> (s, s))

This computation just returns the current state without modifying it, so the boolean argument is False. The computation for setting the current state, however, does modify it, so it is True for put:

put :: s -> State s ()
put s = State True (\_ -> ((), s))

One thing to notice here is that put is not a State computation in itself. It is a function, which produces a State computation. This might sound like I’m hairsplitting, but this difference is key to the problem we will run into, when trying to turn this thing into a monad.

Let’s turn our State into a functor. Using fmap on a stateful computation does not change its state-setting behaviour, so we just take the boolean value from the argument computation:

instance Functor (State s) where
    fmap f (State m c) =
        State m $ \s' ->
            let (x, s) = c s'
            in (f x, s)

Now we will define an Applicative instance. A pure computation never changes the state; it just results in a certain value. The <*> operator combines two stateful computations. If either of them modifies the state, then their combination modifies the state, too:

instance Applicative (State s) where
    pure x = State False (\s -> (x, s))

    State mf cf <*> State mx cx =
        State (mf || mx) $ \s'' ->
            let (f, s') = cf s''
                (x, s) = cx s'
            in (f x, s)

And finally we will crash straight into the big problem with monads. Let’s try to define the Monad instance:

instance Monad (State s) where
    return = pure

    State mf cf >>= f =
        State (mf || undefined) $ \s'' ->
            let (x', s') = cf s''
            in runState (f x') s'

Do you see the undefined value for the usesPut boolean? We know that if the source computation (the left argument to >>=) modifies the state, then certainly the composition also modifies it. What if it doesn’t?

In this case we can’t in fact tell whether the composition is going to modify the state or not. The problem here is that the f argument to >>= is an opaque function. Its result is a State computation that may or may not modify the state. It can be anything.

The argument to f is produced by the source computation (or more exactly its underlying function, which we called cf in the code above). This is the only way to generate a (not undefined) argument to f, because the argument’s type is fully polymorphic. We only know that it matches the result type of the source computation.

So if the source computation doesn’t already modify the state, then it depends entirely on the outcome of the source computation, whether the target computation to the right hand side of >>= modifies its state. It is impossible to tell without actually trying out the state-modifying function, and it may depend on what initial state value you pass into that function.

In other words: What we want here looks a lot like a monad, but as we have seen it’s not. The meta-information isn’t as meta as we would like it to be, because it doesn’t only depend on the compositional structure. It also depends on what happens at run-time.

But heck, it sure must be possible to tell statically whether we have used a put computation anywhere in the composition, no?

3.2 Arrows to the rescue

Again what I have presented above is not a monad. It makes the impression to be a monad, because we know traditional state functions to form a monad. In fact without the static information (the Bool argument), there would be no difficulty implementing the monadic interface. However, in presence of the static information we are unable to write an implementation for (>>=). The problem here is that the second argument to (>>=) is a function, and functions are completely opaque in Haskell. Of course this is what makes monads very expressive, and we don’t want to give them up.

What we have seen though is that it was possible to write an Applicative instance and get an applicative functor out of it. We could just use the applicative interface for our purposes. However, there is a problem. Applicative functors are not as composable as monads. There is no way to feed the result of one computation to another. We can only sequence computations and combine their results with a pure function. This is not very useful for a state monad. We really want to have expressive composability while retaining the static information.

So what we really need is something between applicative functors and monads. This is where arrows come in. The arrow interface is similar to the monadic interface, but does not require opaque functions for composition and yet retains most of the expressiveness.

4 The arrow interface

Let’s have a second look on our broken State monad above:

getMult :: Num s => s -> State s s
getMult f = State False $ \s -> (f*s, s)

This function does not modify the state. It just returns the current state multiplied by the given factor f. However, getMult is not a monadic computation in its own right. It is a function resulting in a computation and we have seen that this leads to problems.

So apparently our problem is that we cannot express input-dependent computations without functions. Whenever a computation depends on some input, we have to write an opaque function to represent it.

Solution: Make the input type explicit, so that we can write input-dependent computations, which are not functions. Unlike monads an arrow takes two type arguments, an input type and an output type. In other words, an arrow computation corresponds to a function from argument to result, while a monadic computation corresponds to a result only:

data StateArrow s a b =
    StateA {
      usesPutA      :: Bool,
      runStateArrow :: (a, s) -> (b, s)
    }

The type StateArrow s is an arrow. The first type argument a is the input type and b is the output type. Now we can have state-transforming functions that provide meta-information before application:

getMultA :: Num s => StateArrow s s s
getMultA = StateA False $ \(f, s) -> (f*s, s)

As you can see, getMultA is not a function. We can extract the meta-information using the usesPutA field without having to apply the underlying state function. Let’s also define getA and putA:

getA :: StateArrow s a s
getA = StateA False $ \(_, s) -> (s, s)

putA :: StateArrow s s ()
putA = StateA True $ \(s, _) -> ((), s)

These two utilities are not functions either. You can extract the meta-information in both cases without caring for the underlying function. The only missing thing is a generic way to compose such computations. For arrows there are two type classes for such an interface: Category and Arrow.

4.1 Category type class

The Category type class will give us the ability to compose arrow computations like functions. It also gives us an arrow computation corresponding to the identity function.

class Category cat where
    id  :: cat a a
    (.) :: cat b c -> cat a b -> cat a c

Note that these names clash with the predefined ones from the Prelude. That’s the reason why we imported Prelude hiding the two explicitly:

import Prelude hiding ((.), id)

Now don’t worry about losing functionality here. The function type constructor (->) is a category, too, so what we are importing with Control.Category is in fact a generalization of (.) and id.

Let’s define a Category instance for our StateArrow:

instance Category (StateArrow s) where
    id = StateA False id

    {- ... to be continued ... -}

Obviously the identity state function does not modify the state. It just gives its input right back as output. Note that we are dealing with two different instances of id here. We are defining the id computation for the StateArrow s category. Inside that definition we are using the id computation from the (->) category, which is simply the identity function. So this expands to:

    id = StateA False (\(x, s) -> (x, s))

Next let’s define the composition operator:

    {- ... continued ... -}

    StateA m2 f2 . StateA m1 f1 =
        StateA (m1 || m2) $ f2 . f1

This is interesting. We can pass the result of one state transforming function to another while retaining the meta-information. If either of the two state functions modifies the state, then their composition modifies it, too.

This gives us much of the expressive power of state monads. In essence it gives us back a tool slightly less powerful than (>>=) from the monadic toolbox: the (<=<) combinator. It also gives us back return: The id computation corresponds to the return function from the monadic interface. We have just moved the input type to be an argument to the arrow:

return :: a -> m a
id     :: a `cat` a

(.)    :: (b `cat` c) -> (a `cat` b) -> (a `cat` c)
(<=<)  :: (b -> m c)  -> (a -> m b)  -> (a -> m c)

There are two important laws, which must hold for categories:

a . id = id . a = a
a . (b . c) = (a . b) . c

The first law basically states that id is a proper identity and neutral element with respect to composition. More importantly from this follows that id cannot have arrow-specific side effects, because otherwise the first law would be broken. The second law states that composition is associative. This will be most useful when we start using arrow notation in the next chapter.

Apparently these laws hold for our state arrow. We won’t prove this here, but it’s easy to do, so give it a shot!

To see this in action, we have to define some StateArrow computations:

stateFunc :: (a -> b) -> StateArrow s a b
stateFunc f = StateA False $ \(x, s) -> (f x, s)

This function turns a regular function into a StateArrow computation. Such a function ignores the state and just transforms its input. Using it we can write a state modification function:

modifyState :: (s -> s) -> StateArrow s a ()
modifyState f = putA . stateFunc f . getA

We are using our newly defined (.) combinator to compose three state computations. However, our set of tools lack some expressive power. Let’s have a look at a computation using a traditional state monad:

do x <- someComp
   y <- someFunc x
   return (x+y)

This computation gets the result of someComp calling it x, then passes x to someFunc calling its result y. Finally it returns the sum of x and y. We cannot express this computation in terms of what we have right now. We are approaching arrows.

4.2 Arrow type class

The problem with the (.) combinator is that it doesn’t allow us to keep results across computations:

c3 . c2 . c1

The only way for c3 to receive the result of c1 is to have a fair c2, which returns part of its input unchanged. So if c2 has the type

c2 :: cat a b

we basically need a function to turn it to

fairC2 :: cat (a, c) (b, c)

The fairC2 computation is a version of c2, which accepts an input argument of type a and returns a result of type b. It also has a side channel for a value of type c, which it returns unchanged.

Further it turns out that lifting functions to arrow computations is something we will want to do a lot, so we would like to include a combinator for that one as well.

These two features together, a side-stepping combinator and a function lifting combinator, turn a category into an arrow. This is the arrow type class (simplified to its minimal complete definition):

class Arrow arrow where
    arr   :: (a -> b) -> arrow a b
    first :: arrow a b -> arrow (a, c) (b, c)

For our state arrow the arr combinator is our stateFunc combinator, which lifts a regular function to the arrow. The first combinator is more interesting. It turns any state computation into a fair one by attaching a side channel for values of type c to it.

The computation first c takes a tuple as input and performs whatever c would perform on the first value. The second value is passed unchanged.

Let’s define the Arrow instance for our state arrow:

instance Arrow (StateArrow s) where
    arr f = StateA False $ \(x, s) -> (f x, s)

    first (StateA m f) =
        StateA m $ \((x', y), s') ->
            let (x, s) = f (x', s')
            in ((x, y), s)

With these combinators we can write an arrow version of the monadic computation shown above. Let’s see it again:

do x <- someComp
   y <- someFunc x
   return (x+y)

Now here is the arrow version:

sideChannel =
    arr (\(y, x) -> y + x) .
    first someFunc .
    arr (\x -> (x, x)) .
    someComp

It is important to read this from bottom to top. The resulting computation is the following composition:

When using first you usually need a computation to duplicate a value. You also need a computation to combine the values of the resulting tuple. These computations are usually just regular functions lifted. Hence most of the time arr is really essential for first to be useful. Without arr you would have to write arrow-specific combinators like stateFunc to lift functions.

Arrows obey some laws, too, but unlike monads there are a lot of them. We will only go into two of them here, and they should be fairly self-explanatory:

arr id        = id
arr f . arr g = arr (f . g)

The first law states that the identity function lifted is the identity computation. This should be fairly self-explanatory. The second law is more interesting: It basically says that if you compose two lifted functions, that’s the same as lifting two composed functions. From this follows that arr cannot have side effects.

As noted there are lots of arrow laws, most of them quite intuitive. For an overview of all laws, read John Hughes’ Generalizing Monads to Arrows.

4.3 The function arrow

As noted earlier, functions form an arrow themselves, the function arrow. The type constructor (->) takes two type arguments, the input type and the output type. The resulting type is the type for functions from the given input type to the given output type. This is obviously a category:

instance Category (->) where
    id    = \x -> x
    f . g = \x -> f (g x)

As it turns out (->) is also an arrow:

instance Arrow (->) where
    arr f   = f
    first f = \(x, y) -> (f x, y)

Lifting a regular function to the function arrow is simply the regular function itself. The first combinator attaches a side channel to a regular function. The result is a function, which takes a tuple and applies the given regular function only to the first value of that tuple. The second value is just returned unchanged.

The function arrow acts as the identity arrow in a certain sense, which we will explore later in the section about arrow transformers.

4.4 More category combinators

For categories there are two convenience combinators defined in the Control.Category module. They are called (<<<) and (>>>):

(<<<) :: Category cat => cat b c -> cat a b -> cat a c
(<<<) = (.)

(>>>) :: Category cat => cat a b -> cat b c -> cat a c
(>>>) = flip (.)

The (<<<) combinator is defined to be the same as (.). You can just use that one, which saves you from having to import Prelude explicitly. There is also (>>>), which is a version of (.) with the arguments flipped. That way you can write code in a left-to-right top-to-bottom fashion:

sideChannel =
    someComp >>>
    arr (\x -> (x, x)) >>>
    first someFunc >>>
    arr (\(y, x) -> y + x)

These two combinators are also exported from Control.Arrow, so in general when using arrows there is no need to import Control.Category or Prelude. It’s only useful, when defining arrows.

Note: The combinators presented in this section are not part of the Category type class, so you can’t define an arrow in terms of, for example, (>>>) and id.

4.5 More arrow combinators

As indicated earlier there are more combinators for arrows. The simplified Arrow type class presented above has been reduced to its minimal complete definition. The full arrow class has the following five combinators:

class Arrow arrow where
    arr    :: (a -> b) -> arrow a b
    first  :: arrow a b -> arrow (a, c) (b, c)
    second :: arrow a b -> arrow (c, a) (c, b)
    (&&&)  :: arrow a b -> arrow a c -> arrow a (b, c)
    (***)  :: arrow a b -> arrow c d -> arrow (a, c) (b, d)

The three latter combinators can be easily derived from arr and first, but you may want to give explicit definitions for efficiency. While the first combinator attaches a side channel to the right of the given computation, the second combinator attaches it to the left.

The (&&&) combinator combines two computations to one, which passes its input to both computations and returns their results in a tuple.

The (***) combinator makes a side-by-side combination. The resulting computation takes a tuple, passes its first value to the first computation and its second value to the second. The resulting tuple contains the two results.

With these combinators we can refine our implementation of the sideChannel computation:

sideChannel =
    someComp >>>
    someFunc &&& id >>>
    arr (\(y, x) -> y + x)

Since lifted functions in an arrow composition are so common, there are special combinators for this pattern:

(^>>) :: Arrow arrow => (a -> b)  -> arrow b c -> arrow a c
(>>^) :: Arrow arrow => arrow a b -> (b -> c)  -> arrow a c

(<<^) :: Arrow arrow => arrow b c -> (a -> b)  -> arrow a c
(^<<) :: Arrow arrow => (b -> c)  -> arrow a b -> arrow a c

The definitions are simply:

f ^>> c = arr f >>> c
c >>^ f = c >>> arr f

c <<^ f = c <<< arr f
f ^<< c = arr f <<< c

With those we can add a final refinement to our sideChannel computation:

sideChannel =
    someComp >>>
    someFunc &&& id >>^
    uncurry (+)

Finally there is a predefined computation called returnA:

returnA :: Arrow arrow => arrow b b
returnA = arr id

By definition this is equivalent to id. We will use it a lot in the following chapters. We could use id, too, but returnA does not clash with Prelude names.

5 Basics of arrow notation

Once you use side channels arrow code can become quite tedious quickly. While monadic code written with the (>>=) and (>>) combinators usually doesn’t look much worse than the equivalent code in do-notation, arrow code with the heavy function lifting and explicit side channels can be difficult to read and write.

For this reason there is a language extension called Arrows, which helps you to write much more readable arrow code much more easily. It completely hides the side channel machinery from you. The Glasgow Haskell Compiler implements the extension directly, whereas for other compilers you can add a preprocessor. I’m assuming GHC here, so we will just switch the language extension on (you can also use the -XArrows command line flag, but the pragma is preferred):

{-# LANGUAGE Arrows #-}

Unlike the simple monadic do-notation the arrow notation is complicated and really needs a series of chapters to explain. This is the first one. In this chapter we will rewrite our sideChannel computation in a syntax resembling the monadic do-notation. Let’s review it:

sideChannel =
    someComp >>>
    someFunc &&& id >>^
    uncurry (+)

5.1 Proc notation

The foundation for arrow notation is the proc construct. It is very simple and is really just a syntactic version of (<<^) encapsulating an underlying computation:

proc x -> comp -< x + 1

The x part to the left of -> specifies the input to the computation. The x + 1 part to the right of -< specifies an expression, which will be the input to the underlying computation. And finally the comp part between -> and -< specifies the underlying computation receiving the expression as input.

This translates to:

comp <<^ (+1)

The key difference is that we have named the input explicitly. We gave it the name x. The arrow combinators force you to write everything in point-free style. In essence, proc gives you arrow lambdas. This goes beyond simple naming, because proc takes a pattern, just like the lambda construct:

proc (x, y) -> comp -< x + y

This only allows us to write components of an arrow composition. Particularly proc alone doesn’t help us at all getting rid of explicit side channels.

5.2 Do notation

To get rid of explicit side channels we first need to get rid of explicit composition. For this we need to add some more syntax: do-notation for arrows:

proc x0 -> do
    x1 <- comp1 -< x0
    x2 <- comp2 -< x1
    comp3 -< x2

This translates to:

comp3 . comp2 . comp1

Again the key difference is that we have named all inputs and outputs to all computations explicitly. We will call them arrow variables. The input to the entire computation is the arrow variable x0, which is passed to comp1. Its result is an arrow variable called x1 and passed to comp2. Its result is an arrow variable named x2, which is finally passed to comp3. We don’t (and can’t) name the result of comp3. This is a restriction you already know from monadic do-notation: The last computation is the one returning the end result.

Now the really useful feature of this syntax is that the output of a computation is in scope for everything following it. That means that x0 is in scope in the entire computation and x1 is in scope for comp2 and comp3. When you use variables from earlier computations, side channels are created as needed. For example there is nothing wrong with returning all three results:

proc x0 -> do
    x1 <- comp1 -< x0
    x2 <- comp2 -< x1
    x3 <- comp3 -< x2
    returnA -< (x1, x2, x3)

Here we use the predefined returnA computation. As we learned in the last chapter, it is equivalent to id, and id resembles the monadic return function. This code should make it clear why. It is a computation, which by definition does not have side effects and just returns the input value unchanged.

You need side channels to remember x1 and x2, because they are the results of earlier computations. The arrow notation compiler takes care of that for you, so the resulting code is equivalent to something like this:

comp1 >>>
(comp2 &&& id) >>>
(comp3 . fst &&& id) >>^
(\(x3, (x2, x1)) -> (x1, x2, x3))

Our sideChannel computation from before looks like this:

sideChannel =
    proc x' -> do
        x <- someComp -< x'
        y <- someFunc -< x
        returnA -< y + x

Just like with the simple proc notation you are allowed to have arbitrary expressions to the right of -<. Functions are lifted for you as needed. Also you are allowed to have arbitrary patterns to the left of <- and ->.

One important thing to note is that arrow variables are only in scope to the right of -<. The reason is precisely that we are not dealing with monads here, but with arrows. Unlike with monads the structure of the computation cannot depend on arrow variables. We will see later how to get some of that expressive power back without the shortcomings of the monadic framework.

6 The automaton arrow

We have turned our state monad into a state arrow, both concepts to have implicit state. Side effects, state monads and explicit recursion are the most common ways to write stateful computations in Haskell. In all three cases you are mutating variables. Particularly the first two have a problem in common: they force you to program imperatively, essentially destructively modifying a mutable variable, be it an explicit one through side effects or an implicit one through a state monad. Even though a state monad does not require real mutable variables or other side effects, you are still programming imperatively by acting like you use such.

A cleaner, more declarative approach to keeping state is to let the computation itself mutate. This is cleaner, because it allows you to write a fully declarative description of the starting state, which then mutates all by itself — like an automaton. The manifestation of this concept is the automaton arrow Auto.

What does it mean for a computation to mutate? Not much actually. Of course Haskell, being referentially transparent, does not allow functions to mutate. However, you can write a function, which takes an argument and returns a result along with a new version of itself. Hence it does not mutate, but just asks you to call a different function the next time. We call such functions automata and here is their type:

newtype Auto a b =
    Auto {
      stepAuto :: a -> (b, Auto a b)
    }

It takes an input value and returns an output value. Along with the output value it returns another automaton, a new version of itself.

Obviously you are supposed to call this function in a loop. What exactly that loop does depends on your application. For example it could print the result value or draw a picture described by the result value. At each iteration the function returns a new version of itself, which is called in the next iteration. Let’s write a simple test function for automata, which just prints the output of the current version and repeats with the new version. All versions receive the same input x':

testAuto :: Show b => a -> Auto a b -> IO ()
testAuto x' auto = do

    -- Calculate the output and the new version.
    let (x, newAuto) = stepAuto auto x'

    -- Print the output of the current version.
    print x

    putStrLn "Press enter to continue"
    getLine

    -- Repeat with the new version.
    testAuto x' newAuto

In order to see this in action, we should write an actual automaton. An automaton can just act like a regular function, if it never mutates, i.e. always returns itself as the next automaton:

plusOne :: Num b => Auto b b
plusOne =
    Auto $ \x -> (x + 1, plusOne)

The plusOne automaton really just acts like (+ 1). Let’s try it out (for example in GHCi):

testAuto 1 plusOne

Until you abort with Ctrl-C this will repeatedly print 2 as the output. The plusOne automaton is a so-called stateless automaton. It never mutates. Now let’s have a look at a slightly more interesting automaton, a counter:

countFrom :: Num b => b -> Auto b b
countFrom x0 =
    Auto $ \dx -> (x0, countFrom (x0 + dx))

And test it right away (in GHCi):

testAuto 1 (countFrom 10)

In the first iteration this will print 10, in the next it will print 11, then 12, and so on. The countFrom function produces an automaton, which results in the argument value in this instant. The automaton for the next instant will be the same as this one, but with the input value added to the argument. This acts like a counter. It’s a stateful automaton, because it mutates.

Since our outer loop, the testAuto function, always passes the same input value to the automaton, it will be a linear counter. In our example it always adds 1 to the current value. Our outer loop could of course pass different inputs at different iterations, but a more intriguing idea is to get the input for one automaton from another automaton, and let both evolve individually. This sounds a lot like Category and indeed it is:

instance Category Auto where
    id = Auto $ \x -> (x, id)

    auto2' . auto1' =
        Auto $ \x'' ->
            let (x', auto1) = stepAuto auto1' x''
                (x, auto2)  = stepAuto auto2' x'
            in (x, auto2 . auto1)

The identity automaton just returns its input unchanged and never mutates. A composition of the two automata will pass the input through the first automaton, forwarding that one’s result to the second automaton. Both automata will return a new version of themselves and the new version of the composition is then the composition of those two new versions.

Now we can write a composition of two counters. The first one always receives the input 1 from testAuto, while the second one receives the output of the first one. Hence the first counter will grow linearly (1, 2, 3, 4, …), while the second one grows superlinearly (1, 2, 4, 7, …):

testAuto 1 (countFrom 1 . countFrom 1)

The output of the composition is the superlinear output of the second automaton (the one to the left of the . operator), so when running this we will see the sequence 1, 2, 4, 7, etc. Let’s walk through the composition from initial input to final output:

1.  1 >- countFrom 1 -> 1 >- countFrom 1 -> 1
             |                   |
2.  1 >- countFrom 2 -> 2 >- countFrom 2 -> 2
             |                   |
3.  1 >- countFrom 3 -> 3 >- countFrom 4 -> 4
             |                   |
4.  1 >- countFrom 4 -> 4 >- countFrom 7 -> 7
             |                   |
5.       countFrom 5         countFrom 11

All this together lets us write a special kind of stateful computations. The state of the computation is not a simple computation-global value anymore, but the current mutation of the computation itself. So far we have not seen the advantage over state monads yet, but there is a conceptual difference, which is key to the hidden advantage: We have composed two automata, which don’t know anything about each other, yet keep their own individual state. They have local state.

TO DO!