Intro to Machines & Arrows (Part 1: Stream and Auto)
by Justin Le ♦
Source ♦ Markdown ♦ LaTeX ♦ Posted in Haskell, Ramblings ♦ Comments
So I’m going to be running a series soon on computation and (physical) simulations using AFRP (Arrowized Functional Reactive Programming) principles.
I consider (A)FRP to actually be a pretty game changing paradigm. It provides us with semantics by which to compose and build timevarying, reactive behaviors and completely changes the way we approach any sort of simulation/statelike project.
AFRP has its own elegant way of approaching problems, but to be able to properly use it for simulations, we’re going to have to start by learning about the fundamental abstraction behind its implementation: machines.^{1}
(This post will assume a somewhat basic knowledge of Haskell. I’ll try explaining concepts here and there if I feel that they might not be very commonly known. But if you have any questions, feel free to leave a comment or stop by freenode’s #haskell on irc!)
(A short disclaimer: this article has not too much to do with the great machines library by Rúnar Bjarnason and Edward Kmett)
Why FRP?
This series doesn’t directly deal with FRP, but implementing FRP is one of the motivating factors for what we are discussing.
So why do we even bother with FRP? Why not just just program imperatively and mutate a state? It’s just as easy in a functional/pure language (with a trivial State monad wrapper) as it is in an imperative language.
The answer is the full power of functional programming: composition. Anyone who has dabbled in functional programming (or who has even used Unix pipes) has had a glimpse into the power of composition. We start with simple, fundamental, selfcontained behaviors and compose them piecebypiece into a complex one.
So why FRP? FRP provides for us meaningful semantics by which to compose timevarying and reactive behaviors, and create complex ones from smaller ones. You reason about a selfcontained behavior “wire”…and then use tools to build complex behaviors from simple ones. You don’t specify what happens when, you specify how things should behave, from a topdown level. And then compose those behaviors.
So to proceed, in this post we are going to introduce Streams and (more importantly) Autos. In the next, we will be looking at Autos as a member of the powerful Category and Arrow typeclasses. In the final post, we’ll really be throwing in a lot of useful enhancements to the Auto
type in hopes that you may be prepared for anything you encounter in the real world involving it, including the popular AFRP library netwire.
Streams
(All the code for Streams can be downloaded from github and tried interactively online at FPComplete)
Let’s start with streams, one of the simpler of machines.
Streams are basically infinitely long linked lists.
data Stream b = SCons (b, Stream b)
(SCons
for “Stream cons”)
Compare that with the linked list data type, which is a Stream with an Ending (Nil
):
 source: https://github.com/mstksg/inCode/tree/master/codesamples/machines/Stream.hs#L7L7
 interactive: https://www.fpcomplete.com/user/jle/machines
data List a = Cons (a, List a)  Nil
or, as is more traditionally written:
data [a] = (:) a [a]  []
It’s pretty easy to build lists:
 source: https://github.com/mstksg/inCode/tree/master/codesamples/machines/Stream.hs#L36L37
 interactive: https://www.fpcomplete.com/user/jle/machines
myList :: List Int
= Cons ( 1, Cons ( 2, Cons (3, Nil) ) ) myList
which is just, in the more traditional (infix) form:
 source: https://github.com/mstksg/inCode/tree/master/codesamples/machines/Stream.hs#L40L41
 interactive: https://www.fpcomplete.com/user/jle/machines
myList' :: [Int]
= 1:(2:(3:[])) myList'
Let’s see if myList
does what we want: (a list from 1 to 3):
> let (Cons (x,xs)) = myList
ghci> x
ghci1
> :t xs
ghcixs :: List Int
> let (Cons (y,ys)) = xs
ghci> y
ghci2
> let (Cons (z,zs)) = ys
ghci> z
ghci3
> zs
ghciNil
Yes! Perfect. We can “traverse” down our linked list by repeatedly pattern matching out the “head” (the x
, the first part of the tuple) and the “tail” (the xs
, the second part of the tuple).
But how are we going to build a stream…? We don’t have access to Nil
, so do we have to manually type out an infinite stream?
Let’s try defining the stream [1..]
— a stream that contains every natural number starting from 1.
myStream' :: Stream Int
= SCons ( 1, SCons ( 2, SCons ( 3, ... ) ) ) myStream'
Hm. This is going to take a while. I wonder if there’s an easier way?
We can take advantage of Haskell’s “lazybydefault”ness and leave the “rest” of the stream as an unevaluated function call. And then we can recurse!
 source: https://github.com/mstksg/inCode/tree/master/codesamples/machines/Stream.hs#L46L50
 interactive: https://www.fpcomplete.com/user/jle/machines
myStream :: Stream Int
= streamFrom 1
myStream where
streamFrom :: Int > Stream Int
= SCons ( n, streamFrom (n+1) ) streamFrom n
Cool! Let’s see if this myStream
really does what we want, the same way we tested myList
:
> let (SCons (x, xs)) = myStream
ghci> x
ghci1
> :t xs
ghcixs :: Stream Int
> let (SCons (y, ys)) = xs
ghci> y
ghci2
> let (SCons (z, zs)) = ys
ghci> z
ghci3
> let (SCons (j,js)) = zs
ghci> j
ghci4
> let (SCons (k,ks)) = js
ghci> k
ghci5
Yes, it works perfectly! Just like in the case of List, we can “traverse” down the stream by pattern matching out the “head” of the stream (the first part of the tuple) and the “tail” of the stream (the second part of the tuple).
Note that we can have some fun with Haskell syntax Stream
by adding a record label to the first (and only) field:
data Stream b = SCons { runStream :: (b, Stream b) }
so that we can do fancy things like:
> :t runStream
ghcirunStream :: Stream b > (b, Stream b)
> let (x, xs) = runStream myStream
ghci> x
ghci1
Basically, we get for free the function runStream
, a function that yanks the tuple out of the stream.
One minor final touch — because Stream
has only one constructor and one field, we can make it a newtype
, which has similar usage patterns/syntax as a data
, but which the compiler can more easily optimize:
 source: https://github.com/mstksg/inCode/tree/master/codesamples/machines/Stream.hs#L10L10
 interactive: https://www.fpcomplete.com/user/jle/machines
newtype Stream b = SCons { runStream :: (b, Stream b) }
Automating Traversal
The repeated pattern matching we’ve been doing is kind of tedious, and it’ll only get more annoying over time, so let’s make a function that can automate the pattern matching for us really quickly so that we can test it more easily.
streamToList
will take a Stream and perform the very straightforward conversion into an infinite list.
 source: https://github.com/mstksg/inCode/tree/master/codesamples/machines/Stream.hs#L15L16
 interactive: https://www.fpcomplete.com/user/jle/machines
streamToList :: Stream b > [b]
SCons (x, xs)) = x : streamToList xs streamToList (
So now we can do:
> take 10 $ streamToList myStream
ghci1,2,3,4,5,6,7,8,9,10] [
Alternatively (and for reasons which will later become clear), we can also define testStream
, which takes a specified amount of elements and returns also the “resulting” stream after all of those steps, and testStream_
, which is the same thing except that we throw away the modified stream.
 source: https://github.com/mstksg/inCode/tree/master/codesamples/machines/Stream.hs#L20L30
 interactive: https://www.fpcomplete.com/user/jle/machines
testStream :: Stream b > Int > ([b], Stream b)
0 = ([] , strm )
testStream strm = (y:ys, final)
testStream strm n where
= runStream strm
(y , next ) = testStream next (n1)
(ys, final)
testStream_ :: Stream b > Int > [b]
= (fst .) . testStream testStream_
> testStream_ myStream 10
ghci1,2,3,4,5,6,7,8,9,10] [
Streams are nice
Streams are nice! If you’ve been using Haskell for any stretch of time, you’ll know that we use infinite lists all the time and to great usefulness for the ends of expressiveness and abstraction.
In mathematics, streams are known as a form of Moore machines (albeit with potentially infinite sets of state and output values). They are machines that basically internally progress from state to state to state to state. They just keep on marching on…like a machine. In myStream
, the initial state is 1. The next state is 2; the next is 3, etc. What is important is that the next state is a function of the current state.
This is made very apparent in our definition of streamFrom
:
 source: https://github.com/mstksg/inCode/tree/master/codesamples/machines/Stream.hs#L49L50
 interactive: https://www.fpcomplete.com/user/jle/machines
streamFrom :: Int > Stream Int
= SCons ( n, streamFrom (n+1) ) streamFrom n
The “current state” whenever we call streamFrom n
is n
…the “next state” (the “initial state” of the “tail”) is n+1
. We could have provided any function :: Int > Int
there (say, n+2
), that would be for us our “next state” function.
So myStream
is a Moorelike machine whose “next state” function is “the current state plus one”, and whose output is just the state itself.
State your purpose!
Did you catch that last sentence? It’s a subtle point. In general, streams can have outputs that are different than their states. As a trivial example, let’s have a stream whose state is an integer, yet whose output is a character:
 source: https://github.com/mstksg/inCode/tree/master/codesamples/machines/Stream.hs#L53L57
 interactive: https://www.fpcomplete.com/user/jle/machines
charStream :: Stream Char
= charStreamFrom 65
charStream where
charStreamFrom :: Int > Stream Char
= SCons ( chr n, charStreamFrom (n+1) ) charStreamFrom n
> take 10 $ streamToList charStream
ghci"ABCDEFGHIJ"
Wait, this is kind of weird. The type of our stream is Stream Char
…Char
is the type of output/elements in the stream, the “head” when we pattern match. But where is the Int
that is the state of our stream in the type Stream Char
…?
Can we even write a function getState :: Stream b > s
that works in general for all streams?
Hm. If the state of our stream can have a type totally unrelated to the type of the stream…that means that we probably can’t even know what it type is. And that even if we could “force” it out somehow, we would not even be able to work with it in a typesafe way!
In fact…couldn’t the state even vary dynamically as the stream progresses?
Continuing on
The problem with streams, as you might have guessed, is that you can’t really affect their progress once they start. Once you start myStream
, it’ll keep on marching on, and on, and on…you have no way to “influence” its progression during its march. The behavior of our stream can’t be influenced by the outside world in any way, once it has started. This is a bit limiting, because we want behaviors that we can have interact with each other.
And so, we have the natural generalization of streams (and the machine we will be spending the most time looking at): Auto.
Auto
(All the code for Autos can be downloaded from github and tried interactively online at FPComplete)
Let’s upgrade our streams, and introduce a way to affect how they progress. Let’s call it an Auto.
 source: https://github.com/mstksg/inCode/tree/master/codesamples/machines/Auto.hs#L12L12
 interactive: https://www.fpcomplete.com/user/jle/machines
newtype Auto a b = ACons { runAuto :: a > (b, Auto a b) }
Now, instead of an SCons
containing just a tuple (a headtails), an ACons
contains a function that produces your headtails tuple. Before, all of our runStreams
produced the same tuple no matter what. Now, our runAuto
can produce a different tuple based on an outside input.
This is cool!
Let’s look at the type signature of Auto before we go too much further.
In Auto a b
, b
is (just like for a Stream) the type of your “head” and the type of the items in your “tail”. It’s the type of your “stream”.
a
is the type of the “influencing input”.
So now, we basically have a Stream b
, except at every “step”, we can “influence” the Stream with something of type a
.
A Trivial Auto
Let’s look at a direct “port” of our myStream
:
 source: https://github.com/mstksg/inCode/tree/master/codesamples/machines/Auto.hs#L40L44
 interactive: https://www.fpcomplete.com/user/jle/machines
myStreamAuto :: Auto a Int
= streamAutoFrom 1
myStreamAuto where
streamAutoFrom :: Int > Auto a Int
= ACons $ \_ > ( n, streamAutoFrom (n+1) ) streamAutoFrom n
This is kind of a dumb example, but myStreamAuto
is just the exact same as myStream
. It’s an Auto, but it ignores its influencing input.
Let’s try it out.
> :t runAuto
ghcirunAuto :: Auto a b > (a > (b, Auto a b))
> let (x, xs) = runAuto myStreamAuto undefined
ghci> x
ghci1
> :t xs
ghcixs :: Auto a Int
> let (y, ys) = runAuto xs undefined
ghci> y
ghci2
> let (z, zs) = runAuto ys undefined
ghci> z
ghci3
Remember that we are really doing (runAuto myStreamAuto) undefined
, but because of how Haskell associates function calls, the parentheses are unnecessary. And hey, it kind of looks like runAuto
is a twoparameter function with an Auto as the first parameter and the “influence”/“input” as its second. Which, due to the magic of curryingbydefault, it basically is, in Haskell!
A Nontrivial Auto
Okay, that was fun I guess. But now let’s take a first look at an auto which can be influenced.
Let’s have a stream where at every step, we can choose to “reset” the counter to whatever integer we like.
We can do this by having the influence/input be a Maybe Int
. If we want the counter to progress normally, we pass in a Nothing
. If we want the counter to reset to a number n
of our choosing, we pass in a Just n
 source: https://github.com/mstksg/inCode/tree/master/codesamples/machines/Auto.hs#L48L54
 interactive: https://www.fpcomplete.com/user/jle/machines
settableAuto :: Auto (Maybe Int) Int
= counterFrom 1
settableAuto where
counterFrom :: Int > Auto (Maybe Int) Int
= ACons $ \reset >
counterFrom n let c = fromMaybe n reset
in ( c, counterFrom (c + 1) )
Remember that fromMaybe :: a > Maybe a > a
takes a “default” value, a Maybe value, and then returns the value inside the Maybe if it’s a Just
, or the default value if it’s a Nothing
.
So basically, when you runAuto
with the Auto, if you give it a Nothing
, it’ll give you ( n, counterFrom (n+1) )
. If you give it Just m
, it’ll give you ( m, counterFrom (m+1) )
.
Cool — let’s try it out.
> let (x, xs) = runAuto settableAuto Nothing
ghci> x
ghci1
> let (y, ys) = runAuto xs Nothing
ghci> y
ghci2
> let (z, zs) = runAuto ys (Just 10)
ghci> z
ghci10
> let (j, js) = runAuto zs Nothing
ghci> j
ghci11
> let (k, ks) = runAuto js Nothing
ghci> k
ghci12
> let (l, ls) = runAuto ks (Just (1))
ghci> l
ghci1
> let (m, ms) = runAuto ls Nothing
ghci> m
ghci0
And there ya go.
Automatic traversals for our Autos
Again, the manual pattern matching is a little tedious so let’s write us a function to automate “progressing” down an Auto.
Like our testStream
, testAuto
takes an Auto. But because every “step” needs an input, testAuto auto
takes a list that specifies the input for every step. testAuto
returns the resulting collection of results, and also the modified Auto. testAuto_
throws away the new Auto and just gives us the collection.
 source: https://github.com/mstksg/inCode/tree/master/codesamples/machines/Auto.hs#L17L25
 interactive: https://www.fpcomplete.com/user/jle/machines
testAuto :: Auto a b > [a] > ([b], Auto a b)
= ([] , auto )
testAuto auto [] :xs) = (y:ys, final)
testAuto auto (xwhere
= runAuto auto x
(y, next ) = testAuto next xs
(ys, final)
testAuto_ :: Auto a b > [a] > [b]
= fst . testAuto a testAuto_ a
Trying it out on settableAuto
:
ghci> testAuto_ settableAuto [ Nothing, Nothing, Just 10
, Nothing, Nothing, Just (1)
, Nothing ]
[1,2,10,11,12,1,0]
Alternatively, here is a fun way to test an Auto interactively, where you ask for input at each iteration from the user —
 source: https://github.com/mstksg/inCode/tree/master/codesamples/machines/Auto.hs#L27L32
 interactive: https://www.fpcomplete.com/user/jle/machines
interactAuto :: (Read a, Show b) => Auto a b > IO ()
= do
interactAuto a0 < getLine
inp let (x,a1) = runAuto a0 (read inp)
print x
interactAuto a1
> interactAuto settableAuto
ghci> Nothing
1
> Nothing
2
> Just 10
10
> Nothing
11
A Shift
Let’s shift our thinking a bit. Instead of seeing Autos as “streams you can influence”, we can think about them as “functions with state”. That is, they are functions that carry selfcontained encapsulated state inside themselves. They are still functions of some kind — you put in an “input” of type a
and get in an “output” (the head) of type b
. However, every “time” you do this, you get a different output depending on what you have already passed in and what the internal state is. As we will see, this internal state is completely opaque to the world. The world only has access to the “output”, the result.
(Remember that, because we’re in a functional language, nothing is technically actually really “mutable”. When we say that we have a stateful function, we really mean that every time we “call” the function, we get back an “updated” function with the new state that behaves differently when “called”).
To put it in terms of settableAuto
:
 The “input” of
settableAuto
is ourMaybe Int
by which we convey or decision to reset or allow to increment by one as normal.  The “output” of
settableAuto
is the “head” of theACons
that is returned — thex
,y
, etc. It’s theInt
, the counter.  The “state” of
settableAuto
is, in essence, then
ofcounterFrom n
. It’s the internal value by which the behavior is determined. The behavior ofrunAuto
depends on then
— it either yieldsn
itself and incrementsn
, or ignores it.
The opaque state
It’s a little tricky because the “output” and the “state” in our example function seem to be exactly the same (just like for myStream
), but let’s whip up a quick example where it’s a little more obvious that the state and the output are different things, and that the state is completely opaque and encapsulated.
 source: https://github.com/mstksg/inCode/tree/master/codesamples/machines/Auto.hs#L58L64
 interactive: https://www.fpcomplete.com/user/jle/machines
isEvenAuto :: Auto (Maybe Int) Bool
= isEvenAutoFrom 1
isEvenAuto where
isEvenAutoFrom :: Int > Auto (Maybe Int) Bool
= ACons $ \reset >
isEvenAutoFrom n let c = fromMaybe n reset
in ( even c, isEvenAutoFrom (c + 1) )
So isEvenAuto
is the same as settableCounterFrom
, except instead of “yielding”/“outputting” n
, it outputs even n
— True
if n
is even and False
if n
is odd.
Here is a demonstration of its behavior —
> testAuto isEvenAuto [ Nothing, Nothing, Just 10
ghciNothing, Nothing, Just (1)
, Nothing ]
, False,True,True,False,True] [
Note that there is in general really no way to ever access the n
internally (in fact, like we said before, it is in theory possible because we can’t even know its type). It is completely sealed off from the world, except by our explicit design. Here, we choose to only “offer” a way to “set” it using our input.
Now it the three distinct concepts — the input, output, and state — should be clear.
 The “input” again is a
Maybe Int
where we can choose to reset the march of the state.  The “output” here is now a
Bool
that says whether or not the internal state is even.  The “state” here is still that
n
(anInt
), and was the same as in the last example. But here it is more clear that the state is inaccessible in general. We can only modify it in ways that the Auto itself allows our “input” (in this case, a setter) to modify it. And we certainly can’t arbitrarily “read” it.
Autos are nice!
It should be clear now that Autos are a more or less straightforward extension of Streams.
In fact, you might see that every Stream b
is equivalent to Auto () b
, where the input is always unit.
Autos correspond loosely to the mathematical Mealy machine, but again with technically potentially infinitely many possible states, input, and output values.
Now, we have a way to model behaviors that can somehow interact with the outside world.
More on state
As we have seen, Auto’s carry all of the hiddeninternalstate features of Streams. The type of an Auto (Auto a b
) reveals the type of the “input” and the “ouput”…but it never reveals nor fixes the type of the “state”. The type of the state is not only unknown, by possibly dynamically changing over the course of the Auto’s progression.
What Auto offers over Stream is then a way for the outside world to access and modify the state if the Auto wants it to. Now, we can design Autos that, like we have seen with settableAuto
, we can offer limited ways to allow the world to modify the state on our own terms.
The Accumulator
Let’s try our hand at another Auto, but instead of looking at things as an influencable and eternally marching stream, we’re going to try to look at things as a function with state that affects its output.
How about an Auto that “accumulates” and “sums up” all of its incoming inputs, starting at 0? More correctly, an Auto that, given any int, “returns” the sum of that int with all of the previous ints it has received in its lifetime.
 source: https://github.com/mstksg/inCode/tree/master/codesamples/machines/Auto.hs#L67L73
 interactive: https://www.fpcomplete.com/user/jle/machines
summer :: Num a => Auto a a
= sumFrom 0
summer where
sumFrom :: Num a => a > Auto a a
= ACons $ \input >
sumFrom n let s = n + input
in ( s , sumFrom s )
> let (out1, auto1) = runAuto summer 10
ghci> out1
ghci10
> let (out2, auto2) = runAuto auto1 3
ghci> out2
ghci13
> testAuto_ auto2 [15,17,6,0,1]
ghci28,11,17,17,16] [
 The “input” is our incoming
Int
— 10, 3, 15, 17, etc.  The “output” is the accumulated sum/integral – 10, 13, 28, 11, etc.
 The “state” in this case is the accumulator, which in this case stays in sync with the output. But remember that this is not the case in general.
Just for kicks, let’s generalize this and make an Auto version of foldl
(technically, more like scanl
): give us an operator and an initial value, and we’ll “fold up” all of our inputs.
 source: https://github.com/mstksg/inCode/tree/master/codesamples/machines/Auto.hs#L78L84
 interactive: https://www.fpcomplete.com/user/jle/machines
autoFold :: forall a b. (b > a > b) > b > Auto a b
init = foldFrom init
autoFold op where
foldFrom :: b > Auto a b
= ACons $ \input >
foldFrom x let y = x `op` input
in ( y, foldFrom y )
(the forall
is used with the Scoped Type Variables extension to let us say that the b
we mention in the type of foldFrom
is the same as the b
in the type of autoFold
. If we leave off the type signature of foldFrom
, this is not necessary)
Note that summer
then is just autoFold (+) 0
.
You can probably imagine lots of different folds you can turn into autoFold
s…and indeed a lot of practical Autos are just autoFold
s. Here are some cute ones:
 source: https://github.com/mstksg/inCode/tree/master/codesamples/machines/Auto.hs#L92L107
 interactive: https://www.fpcomplete.com/user/jle/machines
accumulateIntoList :: Auto a [a]
= autoFold (flip (:)) []
accumulateIntoList
productor :: Num a => Auto a a
= autoFold (*) 1
productor
accumulateStrings :: Auto String String
= autoFold (++) ""
accumulateStrings
monoidAccum :: Monoid a => Auto a a
= autoFold mappend mempty monoidAccum
Cool, huh?
Parallels with list folds
Let’s look very carefully at a comparison between the type signature of Prelude’s foldl
and the type signature of autoFold
:
foldl :: (b > a > b) > b > ([a] > b)
autoFold :: (b > a > b) > b > Auto a b
Hm. Let’s do some rearranging. Remember that in Haskell, (>)
is just an infix type operator. So we can always rewrite a > b
as (>) a b
foldl :: (b > a > b) > b > ( (>) [a] b )
autoFold :: (b > a > b) > b > ( Auto a b )
Let’s get rid of some of the points, too:
foldl op initial :: (>) [a] b
initial :: Auto a b autoFold op
So both foldl
and autoFold
have very similar behaviors:
Give foldl
or autoFold
an accumulating function and an initial value, and they return a new “function thing”.
For foldl op initial
, this “function thing” takes a list of a
values and condenses them into a b
value.
For autoFold op initial
, the “function thing” takes one a
value and returns a b
value based on the previous a
’s it has seen.
The main point here is that autoFold
is a sort of “function” in a way…just like the others before it. It’s a….”functionlike thing”.
Aside
Here is a quick diversion, if you’re up for it. This doesn’t really have too much to do with the rest of the post, but it’ll help you test your intuition a bit with Autos.
As an exercise, compare (and contrast) these three functions of identical type signatures:
map f :: [a] > [b]
scanl op initial :: [a] > [b]
auto :: [a] > [b] testAuto_
(Assume that scanl
does not include the initial accumulator…that is, we are really talking about drop 1 . scanl op init
)
Compare what they do conceptually. Then, for fun, try implementing some of them in terms of the other. Which reimplementations are possible? Which ones aren’t?
More Auto examples
I’ve thrown up a few auto examples that you can run online so you can try it out and see how different ones work. Don’t get too attached to them, because we will later be reimplementing them as compositions of smaller, simpler building blocks.
 rollingAverage

rollingAverage n :: Fractional a => Auto a a
outputs a rolling average of the lastn
values it has encountered
> testAuto_ (rollingAverage 4) [2,8,4,5,1,8,3,5,1,1,8,3,5,9,2]
ghci2.0 ,5.0 ,4.67,4.75,4.5
[4.5 ,4.25,4.25,4.25,2.5
,3.75,3.25,4.25,6.25,4.75] ,
 onFor

onFor p i :: Auto a Bool
normally outputsFalse
…except whenever the input matches the given predicatep :: a > Bool
. Then it stays “on” (True
) fori
steps.
> :t onFor even 3
ghcieven 3 :: Auto Int Bool
onFor > testAuto_ (onFor even 3) [1,1,2,1,1,1,1,4,1,6,1,1,1,1]
ghciFalse, False, True , True , True
[ False, False, True , True , True
, True , True , False, False ] ,
 autoMap

autoMap cap :: Auto (Command k v) (Maybe v)
is a neat one. It internally holds a Map (a keyvalue store) — you can give it[Command][]
data types that tell it to insert, lookup, and delete values. However, it enforces a maximum of items.The main thing to note here is that you get to completely encapsulate your “state”, and allow it only to be “modified” or “viewed” under your own terms. In OOP terms, it is like exposing only a few public methods to modify your private state with discrimination. If you were passed an
autoMap
with items already inside, you would have no way to have full “access” to the map — you would never be able to perform general operations (such as getting a list of all of the keys).
> testAuto_ (autoMap 3)
ghci [ Insert "hello" 7
 , Insert "world" 10
 , Insert "foo" 12
 , Insert "bar" 15
 , Delete "baz"
 , Delete "world"
 , Insert "haskell" 19
 , Lookup "world"
 , Lookup "hello"
 ]
Just 7 , Just 10, Just 12
[ Nothing, Nothing, Just 10
, Just 19, Nothing, Just 7 ] ,
“Function Things”
Anyways, back to our main point of emphasis:
Autos are functionlike things.
They are functions…with (selfcontained) state.
Let’s do an analysis for isEvenAuto
like the one we did with foldAuto
. Our “input” was a Maybe Int
and our “output” was a Bool
.
You can think of isEvenAuto
as a “function thing” from Maybe Int
to Bool
.
Here’s another function from Maybe Int
to Bool
: (I’m going to be using the prefix form of (>)
a lot from now on)
 source: https://github.com/mstksg/inCode/tree/master/codesamples/machines/Auto.hs#L181L182
maybeIsEven :: (>) (Maybe Int) Bool
= even . fromMaybe 1 maybeIsEven
maybeIsEven
returns True
when value inside the Just
is even, or False
if the value is odd or it’s a Nothing
.
Compare that type signature to that of our isEvenAuto
maybeIsEven :: (>) (Maybe Int) Bool
isEvenAuto :: Auto (Maybe Int) Bool
maybeIsEven
and isEvenAuto
are both “functionlike things”. But whereas maybeIsEven
is “memoryless” (it’s the same every time you call it), isEvenAuto
has memory — it returns a different Boolean based on its history.
Contrast this with a Stream, which as we have seen is just an Auto () b
. Streams are then “function like things” analogous to some (>) () b
, or () > b
. We can call functions like () > b
“constants”, or “producers”. They are the same every time you call them or ask for them. Streams, however, “return” a potentially different b
value every time they are “asked for”. So, just like an Auto is a “function” that has memory, a Stream is like a “constant” that has memory. A stateful generator. A “constant” that returns something different every time you ask for it.
Anyway, you should be able to guess that, after vaguely using the phrase “function things” several times…I’m going to surprise you all with the revelation that the general class of these “function things” have a name! And maybe even…a typeclass?
Onward
So far we haven’t really made too convincing of an argument for the advantages of using machines (like Auto and the related Wire). Yeah, they provide encapsulation and a changing state…but these things come for free in most good ObjectOriented Programming languages. So what gives?
As it turns out, as we suggested before, Autos are potentially more “composable” than the objects of OOP. That is because, at their heart, they are just functions. And what do functions do best (as every functional programmer knows)? They compose! Complex object built seamlessly from simpler ones.
Now, I haven’t really been able to back this up so far. We’ve only scratched the surface, and we haven’t even considered functionlike things that can return other functionlike things. But in the next post, as we explore more the functionlike nature of these things, we will be able to witness more of the full power of machine composition. And we’ll even be able to reimplement many of the complex machines of this post with compositions of smaller, simpler Autos.
It is somewhat important to note here that the semantics of FRP do not inherently involve machines. We’ll learn more about this later. For now, remember that this series will chiefly study the lowlevel implementation of AFRP, which may or may not be related to the semantics/abstractions of FRP — in an ideal world we wouldn’t even have to worry about implementation and just work on the level of the abstractions. Unfortunately, we don’t live in an ideal world :(↩︎