git.iko.soy/elk
on 63243ca help sign in
elk/libraries/Automaton.elm.hidden
123 lines 3.9 kB history raw
1module Automaton ( pure, state, hiddenState, run, step
2 , (<<<), (>>>), combine, count, average
3 ) where
5{-| This library is a way to package up dynamic behavior. It makes it easier to
6dynamically create dynamic components. See the [original release
7notes](http://elm-lang.org/blog/announce/0.5.0.elm) on this library to get a feel for how
8it can be used.
10# Create
11@docs pure, state, hiddenState
13# Evaluate
14@docs run, step
16# Combine
17@docs (>>>), (<<<), combine
19# Common Automatons
20@docs count, average
21-}
23import open Basics
24import Signal (lift,foldp,Signal)
25import open List
26import Maybe (Just, Nothing)
28data Automaton a b = Step (a -> (Automaton a b, b))
30{-| Run an automaton on a given signal. The automaton steps forward whenever the
31input signal updates.
32-}
33run : Automaton a b -> b -> Signal a -> Signal b
34run auto base inputs =
35 let step a (Step f, _) = f a
36 in lift (\(x,y) -> y) (foldp step (auto,base) inputs)
38{-| Step an automaton forward once with a given input. -}
39step : a -> Automaton a b -> (Automaton a b, b)
40step a (Step f) = f a
42{-| Compose two automatons, chaining them together. -}
43(>>>) : Automaton a b -> Automaton b c -> Automaton a c
44f >>> g =
45 Step (\a -> let (f', b) = step a f
46 (g', c) = step b g
47 in (f' >>> g', c))
49{-| Compose two automatons, chaining them together. -}
50(<<<) : Automaton b c -> Automaton a b -> Automaton a c
51g <<< f = f >>> g
53{-| Combine a list of automatons into a single automaton that produces a
54list.
55-}
56combine : [Automaton a b] -> Automaton a [b]
57combine autos =
58 Step (\a -> let (autos', bs) = unzip (map (step a) autos)
59 in (combine autos', bs))
61{-| Create an automaton with no memory. It just applies the given function to
62every input.
63-}
64pure : (a -> b) -> Automaton a b
65pure f = Step (\x -> (pure f, f x))
68{-| Create an automaton with state. Requires an initial state and a step
69function to step the state forward. For example, an automaton that counted
70how many steps it has taken would look like this:
72 count = Automaton a Int
73 count = state 0 (\\_ c -> c+1)
75It is a stateful automaton. The initial state is zero, and the step function
76increments the state on every step.
77-}
78state : b -> (a -> b -> b) -> Automaton a b
79state s f = Step (\x -> let s' = f x s
80 in (state s' f, s'))
82{-| Create an automaton with hidden state. Requires an initial state and a
83step function to step the state forward and produce an output.
84-}
85hiddenState : s -> (a -> s -> (s,b)) -> Automaton a b
86hiddenState s f = Step (\x -> let (s',out) = f x s
87 in (hiddenState s' f, out))
89{-| Count the number of steps taken. -}
90count : Automaton a Int
91count = state 0 (\_ c -> c + 1)
93type Queue t = ([t],[t])
94empty = ([],[])
95enqueue x (en,de) = (x::en, de)
96dequeue q = case q of
97 ([],[]) -> Nothing
98 (en,[]) -> dequeue ([], reverse en)
99 (en,hd::tl) -> Just (hd, (en,tl))
101{-| Computes the running average of the last `n` inputs. -}
102average : Int -> Automaton Float Float
103average k =
104 let step n (ns,len,sum) =
105 if len == k then stepFull n (ns,len,sum)
106 else ((enqueue n ns, len+1, sum+n), (sum+n) / (toFloat len+1))
107 stepFull n (ns,len,sum) =
108 case dequeue ns of
109 Nothing -> ((ns,len,sum), 0)
110 Just (m,ns') -> let sum' = sum + n - m
111 in ((enqueue n ns', len, sum'), sum' / toFloat len)
112 in hiddenState (empty,0,0) step
115{-- TODO(evancz): See the following papers for ideas on how to make this
116library faster and better:
118- Functional Reactive Programming, Continued
119- Causal commutative arrows and their optimization
121Speeding things up is a really low priority. Language features and
122libraries with nice APIs and are way more important!
123--}