Algebra.Graph.Labelled.Example.Automaton

Alga is a library for algebraic construction and manipulation of graphs in Haskell. See this paper for the motivation behind the library, the underlying theory, and implementation details.

This module contains a simple example of using edge-labelled graphs defined in the module Algebra.Graph.Labelled for working with finite automata.

Documentation

data Alphabet

The alphabet of actions for ordering coffee or tea.

Constructors

Coffee

Order coffee

Tea

Order tea

Cancel

Cancel payment or order

Pay

Pay for the order

Instances

Bounded Alphabet

Defined in Algebra.Graph.Labelled.Example.Automaton

Methods

minBound :: Alphabet

maxBound :: Alphabet

Enum Alphabet

Defined in Algebra.Graph.Labelled.Example.Automaton

Methods

succ :: Alphabet -> Alphabet

pred :: Alphabet -> Alphabet

toEnum :: Int -> Alphabet

fromEnum :: Alphabet -> Int

enumFrom :: Alphabet -> [Alphabet]

enumFromThen :: Alphabet -> Alphabet -> [Alphabet]

enumFromTo :: Alphabet -> Alphabet -> [Alphabet]

enumFromThenTo :: Alphabet -> Alphabet -> Alphabet -> [Alphabet]

Eq Alphabet

Defined in Algebra.Graph.Labelled.Example.Automaton

Methods

(==) :: Alphabet -> Alphabet -> Bool

(/=) :: Alphabet -> Alphabet -> Bool

Ord Alphabet

Defined in Algebra.Graph.Labelled.Example.Automaton

Methods

compare :: Alphabet -> Alphabet -> Ordering

(<) :: Alphabet -> Alphabet -> Bool

(<=) :: Alphabet -> Alphabet -> Bool

(>) :: Alphabet -> Alphabet -> Bool

(>=) :: Alphabet -> Alphabet -> Bool

max :: Alphabet -> Alphabet -> Alphabet

min :: Alphabet -> Alphabet -> Alphabet

Show Alphabet

Defined in Algebra.Graph.Labelled.Example.Automaton

Methods

showsPrec :: Int -> Alphabet -> ShowS

show :: Alphabet -> String

showList :: [Alphabet] -> ShowS

data State

The state of the order.

Constructors

Choice

Choosing what to order

Payment

Making the payment

Complete

The order is complete

Instances

Bounded State

Defined in Algebra.Graph.Labelled.Example.Automaton

Methods

minBound :: State

maxBound :: State

Enum State

Defined in Algebra.Graph.Labelled.Example.Automaton

Methods

succ :: State -> State

pred :: State -> State

toEnum :: Int -> State

fromEnum :: State -> Int

enumFrom :: State -> [State]

enumFromThen :: State -> State -> [State]

enumFromTo :: State -> State -> [State]

enumFromThenTo :: State -> State -> State -> [State]

Eq State

Defined in Algebra.Graph.Labelled.Example.Automaton

Methods

(==) :: State -> State -> Bool

(/=) :: State -> State -> Bool

Ord State

Defined in Algebra.Graph.Labelled.Example.Automaton

Methods

compare :: State -> State -> Ordering

(<) :: State -> State -> Bool

(<=) :: State -> State -> Bool

(>) :: State -> State -> Bool

(>=) :: State -> State -> Bool

max :: State -> State -> State

min :: State -> State -> State

Show State

Defined in Algebra.Graph.Labelled.Example.Automaton

Methods

showsPrec :: Int -> State -> ShowS

show :: State -> String

showList :: [State] -> ShowS

coffeeTeaAutomaton :: Automaton Alphabet State

An example automaton for ordering coffee or tea.

coffeeTeaAutomaton = overlays [ Choice  -<[Coffee, Tea]>- Payment
                              , Payment -<[Pay        ]>- Complete
                              , Choice  -<[Cancel     ]>- Complete
                              , Payment -<[Cancel     ]>- Choice ]

reachability :: Map State [State]

The map of State reachability.

reachability = Map.fromList $ map (id &&& reachable skeleton) [Choice ..]
  where
    skeleton = emap (Any . not . isZero) coffeeTeaAutomaton

Or, when evaluated:

reachability = Map.fromList [ (Choice  , [Choice  , Payment, Complete])
                            , (Payment , [Payment , Choice , Complete])
                            , (Complete, [Complete                   ]) ]