This library is for structuring reactive code. The key concepts come directly from Arrowized FRP. It is not yet clear how valuable this is, so it is a great domain for experimentation and iteration to see if we can make it a really useful tool.
This library aims to be a simple and minimal API that will help you get started with Arrowized FRP (AFRP), which can be very hard to understand from just the academic papers. From there, let us know on the mailing list if you wrote a larger program with it or have ideas of how to extend the API.
Think of an automaton as a little robot. It takes in a
values and spits
out b
values. These robots can also remember stuff. If you put two of these
robots next to each other you can do fancier stuff.
Create an automaton with no memory. It just applies the given function to every input.
burnCoal : Coal -> Energy
powerPlant : Automaton Coal Energy
powerPlant = pure burnCoal
The term pure refers to the fact that the same input will always result in the same output.
Create an automaton with state. Requires an initial state and a step function to step the state forward. For example, an automaton that counted how many steps it has taken would look like this:
count = Automaton a Int
count = state 0 (\_ c -> c+1)
It is a stateful automaton. The initial state is zero, and the step function increments the state on every step.
Create an automaton with hidden state. Requires an initial state and a step function to step the state forward and produce an output.
type Feelings = Happy | Sad
stepPerson : Action -> Feelings -> (Reaction, Feelings)
person : Automaton Action Reaction
person = hiddenState Happy stepPerson
Notice that a person
has feelings, but like the
Behaviorists, we do not need to
worry about that as an outside observer.
Step an automaton forward once with a given input.
Say we start with the count
automaton, which begins with the counter at zero.
When we run step 42 count
we get back a new automaton with the counter at
1 and the value 1. The original count
automaton is unchanged, so we need to
use the new automaton to use the latest state.
Take a single input and branch it out into two different results.
buildShip : Automaton Wood Ship
buildHouse : Automaton Wood House
build : Automaton Wood (Ship,House)
build = branch buildShip buildHouse
Combine two independent automatons. The new automaton takes a pair of inputs and produces a pair of outputs. In this case we convert two separate values into two separate piles of wood:
tsunami : Automaton Ship Wood
tornado : Automaton House Wood
disaster : Automaton (Ship,House) (Wood,Wood)
disaster = pair tsunami tornado
Create an automaton that takes a branched input and merges it into a single output.
disaster : Automaton (Ship,House) (Wood,Wood)
pileWood : Wood -> Wood -> Wood
disasterRelief : Automaton (Ship,House) Wood
disasterRelief = disaster >>> merge pileWood
It may be helpful to notice that merge is just a variation of pure
:
merge plieWood == pure (\(logs,sticks) -> pileWood logs sticks)
Create an automaton that takes in a tuple and returns a tuple, but only transform the first thing in the tuple.
build : Automaton Wood (Ship,House)
upgradeShip : Automaton Ship Yacht
buildNicer : Automaton Wood (Yacht,House)
buildNicer = build >>> first upgradeShip
It may be helpful to know about the following equivalence:
first upgradeShip == pair upgradeShip (pure identity)
Create an automaton that takes in a tuple and returns a tuple, but only transform the second thing in the tuple.
build : Automaton Wood (Ship,House)
upgradeHouse : Automaton House Palace
buildNicer : Automaton Wood (Ship,Palace)
buildNicer = build >>> second upgradeHouse
It may be helpful to know about the following equivalence:
second upgradeHouse == pair (pure identity) upgradeHouse
Combine a list of automatons into a single automaton that produces a list.
Turn an automaton into a loop, feeding some of its output back into itself! This is how you make a stateful automaton the hard way.
type Feelings = Happy | Sad
stepPerson : (Action, Feelings) -> (Reaction, Feelings)
person : Automaton Action Reaction
person = loop Happy (pure stepPerson)
This example is equivalent to using hiddenState
to create a person
, but the
benefit of loop is that you can add state to any automaton. We used
(pure stepPerson)
in our example, but something more complex such as
(branch f g >>> merge h)
would work just as well with loop
.
Count the number of steps taken.
Computes the running average of the last n
inputs.
module Automaton
exposing
( Automaton
, pure
, state
, hiddenState
, step
, (>>>)
, (<<<)
, branch
, pair
, merge
, first
, second
, combine
, loop
, count
, average
)
{-| This library is for structuring reactive code. The key concepts come
directly from [Arrowized FRP][afrp]. It is not yet clear how
valuable this is, so it is a great domain for experimentation and iteration
to see if we can make it a really useful tool.
This library aims to be a simple and minimal API that will help you get
started with Arrowized FRP (AFRP), which can be very hard to understand
from just the academic papers. From there, let us know on [the mailing
list](https://groups.google.com/forum/#!forum/elm-discuss) if you wrote
a larger program with it or have ideas of how to extend the API.
[afrp]: http://haskell.cs.yale.edu/wp-content/uploads/2011/02/workshop-02.pdf
# Automatons
@docs Automaton
# Create
@docs pure, state, hiddenState
# Evaluate
@docs step
# Combine
@docs (>>>), (<<<), branch, pair, merge, first, second, combine, loop
# Common Automatons
@docs count, average
-}
{-| Think of an automaton as a little robot. It takes in `a` values and spits
out `b` values. These robots can also remember stuff. If you put two of these
robots next to each other you can do fancier stuff.
-}
type Automaton a b
= Step (a -> ( Automaton a b, b ))
{-| Step an automaton forward once with a given input.
Say we start with the `count` automaton, which begins with the counter at zero.
When we run `step 42 count` we get back a new automaton with the counter at
1 and the value 1. The original `count` automaton is unchanged, so we need to
use the new automaton to use the latest state.
-}
step : i -> Automaton i o -> ( Automaton i o, o )
step a (Step f) =
f a
{-| Compose two automatons into a pipeline. For example, lets say we have a way
to gather wood from the trees and a way to build a ship out of wood.
gatherWood : Automaton Trees Wood
buildShip : Automaton Wood Ship
createShip : Automaton Trees Ship
createShip = gatherWood >>> buildShip
-}
(>>>) : Automaton i inner -> Automaton inner o -> Automaton i o
(>>>) f g =
Step <|
\a ->
let
( f_, b ) =
step a f
( g_, c ) =
step b g
in
( f_ >>> g_, c )
{-| Compose two automatons into a pipeline. For example, lets say we have a way
to gather wood from the trees and a way to build a ship out of wood.
gatherWood : Automaton Trees Wood
buildShip : Automaton Wood Ship
createShip : Automaton Trees Ship
createShip = buildShip <<< gatherWood
-}
(<<<) : Automaton inner o -> Automaton i inner -> Automaton i o
(<<<) g f =
Step <|
\a ->
let
( f_, b ) =
step a f
( g_, c ) =
step b g
in
( g_ <<< f_, c )
{-| Take a single input and branch it out into two different results.
buildShip : Automaton Wood Ship
buildHouse : Automaton Wood House
build : Automaton Wood (Ship,House)
build = branch buildShip buildHouse
-}
branch : Automaton i o1 -> Automaton i o2 -> Automaton i ( o1, o2 )
branch f g =
Step <|
\a ->
let
( f_, b ) =
step a f
( g_, c ) =
step a g
in
( branch f_ g_, ( b, c ) )
{-| Combine two independent automatons. The new automaton takes a pair of
inputs and produces a pair of outputs. In this case we convert two separate
values into two separate piles of wood:
tsunami : Automaton Ship Wood
tornado : Automaton House Wood
disaster : Automaton (Ship,House) (Wood,Wood)
disaster = pair tsunami tornado
-}
pair : Automaton i1 o1 -> Automaton i2 o2 -> Automaton ( i1, i2 ) ( o1, o2 )
pair f g =
Step <|
\( a, b ) ->
let
( f_, c ) =
step a f
( g_, d ) =
step b g
in
( pair f_ g_, ( c, d ) )
{-| Create an automaton that takes in a tuple and returns a tuple, but only
transform the *first* thing in the tuple.
build : Automaton Wood (Ship,House)
upgradeShip : Automaton Ship Yacht
buildNicer : Automaton Wood (Yacht,House)
buildNicer = build >>> first upgradeShip
It may be helpful to know about the following equivalence:
first upgradeShip == pair upgradeShip (pure identity)
-}
first : Automaton i o -> Automaton ( i, extra ) ( o, extra )
first auto =
Step <|
\( i, ex ) ->
let
( f, o ) =
step i auto
in
( first f, ( o, ex ) )
{-| Create an automaton that takes in a tuple and returns a tuple, but only
transform the *second* thing in the tuple.
build : Automaton Wood (Ship,House)
upgradeHouse : Automaton House Palace
buildNicer : Automaton Wood (Ship,Palace)
buildNicer = build >>> second upgradeHouse
It may be helpful to know about the following equivalence:
second upgradeHouse == pair (pure identity) upgradeHouse
-}
second : Automaton i o -> Automaton ( extra, i ) ( extra, o )
second auto =
Step <|
\( ex, i ) ->
let
( f, o ) =
step i auto
in
( second f, ( ex, o ) )
{-| Create an automaton that takes a branched input and merges it into a single
output.
disaster : Automaton (Ship,House) (Wood,Wood)
pileWood : Wood -> Wood -> Wood
disasterRelief : Automaton (Ship,House) Wood
disasterRelief = disaster >>> merge pileWood
It may be helpful to notice that merge is just a variation of `pure`:
merge plieWood == pure (\(logs,sticks) -> pileWood logs sticks)
-}
merge : (i1 -> i2 -> o) -> Automaton ( i1, i2 ) o
merge f =
pure (uncurry f)
{-| Turn an automaton into a loop, feeding some of its output back into itself!
This is how you make a stateful automaton the hard way.
type Feelings = Happy | Sad
stepPerson : (Action, Feelings) -> (Reaction, Feelings)
person : Automaton Action Reaction
person = loop Happy (pure stepPerson)
This example is equivalent to using `hiddenState` to create a `person`, but the
benefit of loop is that you can add state to *any* automaton. We used
`(pure stepPerson)` in our example, but something more complex such as
`(branch f g >>> merge h)` would work just as well with `loop`.
-}
loop : state -> Automaton ( i, state ) ( o, state ) -> Automaton i o
loop state auto =
Step <|
\input ->
let
( auto_, ( output, state_ ) ) =
step ( input, state ) auto
in
( loop state_ auto_, output )
{-| Combine a list of automatons into a single automaton that produces a
list.
-}
combine : List (Automaton i o) -> Automaton i (List o)
combine autos =
Step <|
\a ->
let
( autos_, bs ) =
List.unzip (List.map (step a) autos)
in
( combine autos_, bs )
{-| Create an automaton with no memory. It just applies the given function to
every input.
burnCoal : Coal -> Energy
powerPlant : Automaton Coal Energy
powerPlant = pure burnCoal
The term *pure* refers to the fact that [the same input will always result in
the same output](http://en.wikipedia.org/wiki/Pure_function).
-}
pure : (a -> b) -> Automaton a b
pure f =
Step (\x -> ( pure f, f x ))
{-| Create an automaton with state. Requires an initial state and a step
function to step the state forward. For example, an automaton that counted
how many steps it has taken would look like this:
count = Automaton a Int
count = state 0 (\_ c -> c+1)
It is a stateful automaton. The initial state is zero, and the step function
increments the state on every step.
-}
state : b -> (a -> b -> b) -> Automaton a b
state s f =
Step <|
\x ->
let
s_ =
f x s
in
( state s_ f, s_ )
{-| Create an automaton with hidden state. Requires an initial state and a
step function to step the state forward and produce an output.
type Feelings = Happy | Sad
stepPerson : Action -> Feelings -> (Reaction, Feelings)
person : Automaton Action Reaction
person = hiddenState Happy stepPerson
Notice that a `person` has feelings, but like [the
Behaviorists](http://en.wikipedia.org/wiki/Behaviorism), we do not need to
worry about that as an outside observer.
-}
hiddenState : s -> (i -> s -> ( o, s )) -> Automaton i o
hiddenState s f =
Step <|
\x ->
let
( s_, out ) =
f x s
in
( hiddenState out f, s_ )
{-| Count the number of steps taken.
-}
count : Automaton a Int
count =
state 0 (\_ c -> c + 1)
type alias Queue t =
( List t, List t )
empty =
( [], [] )
enqueue x ( en, de ) =
( x :: en, de )
dequeue q =
case q of
( [], [] ) ->
Nothing
( en, [] ) ->
dequeue ( [], List.reverse en )
( en, hd :: tl ) ->
Just ( hd, ( en, tl ) )
{-| Computes the running average of the last `n` inputs.
-}
average : Int -> Automaton Float Float
average k =
let
step n ( ns, len, sum ) =
if len == k then
stepFull n ( ns, len, sum )
else
( (sum + n) / (toFloat len + 1), ( enqueue n ns, len + 1, sum + n ) )
stepFull n ( ns, len, sum ) =
case dequeue ns of
Nothing ->
( 0, ( ns, len, sum ) )
Just ( m, ns_ ) ->
let
sum_ =
sum + n - m
in
( sum_ / toFloat len
, ( enqueue n ns_, len, sum_ )
)
in
hiddenState ( empty, 0, 0 ) step
{--TODO(evancz): See the following papers for ideas on how to make this
library faster and better:
- Functional Reactive Programming, Continued
- Causal commutative arrows and their optimization
Speeding things up is a really low priority. Language features and
libraries with nice APIs and are way more important!
--}