Copyright	(c) Andrey Mokhov 2016-2022
License	MIT (see the file LICENSE)
Maintainer	andrey.mokhov@gmail.com
Stability	experimental
Safe Haskell	None
Language	Haskell2010

Algebra.Graph.Labelled.Example.Automaton

Description

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.

Synopsis

data Alphabet
- = Coffee
- | Tea
- | Cancel
- | Pay
data State
- = Choice
- | Payment
- | Complete
coffeeTeaAutomaton :: Automaton Alphabet State
reachability :: Map State [State]

Documentation

data Alphabet Source #

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

Instances details

Bounded Alphabet Source #
Instance details Defined in Algebra.Graph.Labelled.Example.Automaton Methods minBound :: Alphabet # maxBound :: Alphabet #
Enum Alphabet Source #
Instance details 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 Source #
Instance details Defined in Algebra.Graph.Labelled.Example.Automaton Methods (==) :: Alphabet -> Alphabet -> Bool # (/=) :: Alphabet -> Alphabet -> Bool #
Ord Alphabet Source #
Instance details 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 Source #
Instance details Defined in Algebra.Graph.Labelled.Example.Automaton Methods showsPrec :: Int -> Alphabet -> ShowS # show :: Alphabet -> String # showList :: [Alphabet] -> ShowS #

data State Source #

The state of the order.

Constructors

Choice	Choosing what to order
Payment	Making the payment
Complete	The order is complete

Instances

Instances details

Bounded State Source #
Instance details Defined in Algebra.Graph.Labelled.Example.Automaton Methods minBound :: State # maxBound :: State #
Enum State Source #
Instance details 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 Source #
Instance details Defined in Algebra.Graph.Labelled.Example.Automaton Methods (==) :: State -> State -> Bool # (/=) :: State -> State -> Bool #
Ord State Source #
Instance details 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 Source #
Instance details Defined in Algebra.Graph.Labelled.Example.Automaton Methods showsPrec :: Int -> State -> ShowS # show :: State -> String # showList :: [State] -> ShowS #

coffeeTeaAutomaton :: Automaton Alphabet State Source #

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] Source #

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                   ]) ]