git.iko.soy/elk
on c19ccfe help sign in
elk/libraries/Automaton.elm
100 lines 3.6 kB history raw
1-- This library is a way to package up dynamic behavior. It makes it easier to
2-- dynamically create dynamic components. See the [original release
3-- notes](/blog/announce/version-0.5.0.elm) on this library to get a feel for how
4-- it can be used.
5module Automaton where
7import Signal (lift,foldp)
8import List (reverse)
9import Maybe (Just, Nothing)
11data Automaton a b = Step (a -> (Automaton a b, b))
13-- Run an automaton on a given signal. The automaton steps forward
14-- whenever the input signal updates.
15run : Automaton a b -> b -> Signal a -> Signal b
16run auto base inputs =
17 let step a (Step f, _) = f a
18 in lift (\(x,y) -> y) <| foldp step (auto,base) inputs
20-- Step an automaton forward once with a given input.
21step : a -> Automaton a b -> (Automaton a b, b)
22step a (Step f) = f a
24-- Compose two automatons, chaining them together.
25(>>>) : Automaton a b -> Automaton b c -> Automaton a c
26f >>> g =
27 Step (\a -> let (f', b) = step a f
28 (g', c) = step b g
29 in (f' >>> g', c))
31-- Compose two automatons, chaining them together.
32(<<<) : Automaton b c -> Automaton a b -> Automaton a c
33g <<< f = f >>> g
35-- Combine a list of automatons into a single automaton that produces a list.
36combine : [Automaton a b] -> Automaton a [b]
37combine autos =
38 Step (\a -> let (autos', bs) = unzip $ map (step a) autos
39 in (combine autos', bs))
41-- Create an automaton with no memory. It just applies the given function to
42-- every input.
43pure : (a -> b) -> Automaton a b
44pure f = Step (\x -> (pure f, f x))
46-- Create an automaton with state. Requires an initial state and a step
47-- function to step the state forward. For example, an automaton that counted
48-- how many steps it has taken would look like this:
49--
50-- count = Automaton a Int
51-- count = state 0 (\\_ c -> c+1)
52--
53-- It is a stateful automaton. The initial state is zero, and the step function
54-- increments the state on every step.
55state : b -> (a -> b -> b) -> Automaton a b
56state s f = Step (\x -> let s' = f x s
57 in (state s' f, s'))
59-- Create an automaton with hidden state. Requires an initial state and a
60-- step function to step the state forward and produce an output.
61hiddenState : s -> (a -> s -> (s,b)) -> Automaton a b
62hiddenState s f = Step (\x -> let (s',out) = f x s
63 in (hiddenState s' f, out))
65-- Count the number of steps taken.
66count : Automaton a Int
67count = state 0 (\_ c -> c + 1)
69type Queue t = ([t],[t])
70empty = ([],[])
71enqueue x (en,de) = (x::en, de)
72dequeue q = case q of
73 ([],[]) -> Nothing
74 (en,[]) -> dequeue ([], reverse en)
75 (en,hd::tl) -> Just (hd, (en,tl))
77-- Computes the running average of the last `n` inputs.
78average : Int -> Automaton Float Float
79average k =
80 let step n (ns,len,sum) =
81 if len == k then stepFull n (ns,len,sum)
82 else ((enqueue n ns, len+1, sum+n), (sum+n) / (len+1))
83 stepFull n (ns,len,sum) =
84 case dequeue ns of
85 Nothing -> ((ns,len,sum), 0)
86 Just (m,ns') -> let sum' = sum + n - m
87 in ((enqueue n ns', len, sum'), sum' / len)
88 in hiddenState (empty,0,0) step
91{-- TODO(evancz): See the following papers for ideas on how to make this
92library faster and better:
94- Functional Reactive Programming, Continued
95- Causal commutative arrows and their optimization
97Speeding things up is a really low priority. Language features and
98libraries with nice APIs and are way more important!
99--}