Copyright	(c) Andrey Mokhov 2016-2022
License	MIT (see the file LICENSE)
Maintainer	[email protected]
Stability	experimental
Safe Haskell	Safe-Inferred
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 Source # maxBound :: Alphabet Source #
Enum Alphabet Source #
Instance details Defined in Algebra.Graph.Labelled.Example.Automaton Methods succ :: Alphabet -> Alphabet Source # pred :: Alphabet -> Alphabet Source # toEnum :: Int -> Alphabet Source # fromEnum :: Alphabet -> Int Source # enumFrom :: Alphabet -> [Alphabet] Source # enumFromThen :: Alphabet -> Alphabet -> [Alphabet] Source # enumFromTo :: Alphabet -> Alphabet -> [Alphabet] Source # enumFromThenTo :: Alphabet -> Alphabet -> Alphabet -> [Alphabet] Source #
Show Alphabet Source #
Instance details Defined in Algebra.Graph.Labelled.Example.Automaton Methods showsPrec :: Int -> Alphabet -> ShowS Source # show :: Alphabet -> String Source # showList :: [Alphabet] -> ShowS Source #
Eq Alphabet Source #
Instance details Defined in Algebra.Graph.Labelled.Example.Automaton Methods (==) :: Alphabet -> Alphabet -> Bool Source # (/=) :: Alphabet -> Alphabet -> Bool Source #
Ord Alphabet Source #
Instance details Defined in Algebra.Graph.Labelled.Example.Automaton Methods compare :: Alphabet -> Alphabet -> Ordering Source # (<) :: Alphabet -> Alphabet -> Bool Source # (<=) :: Alphabet -> Alphabet -> Bool Source # (>) :: Alphabet -> Alphabet -> Bool Source # (>=) :: Alphabet -> Alphabet -> Bool Source # max :: Alphabet -> Alphabet -> Alphabet Source # min :: Alphabet -> Alphabet -> Alphabet Source #

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 Source # maxBound :: State Source #
Enum State Source #
Instance details Defined in Algebra.Graph.Labelled.Example.Automaton Methods succ :: State -> State Source # pred :: State -> State Source # toEnum :: Int -> State Source # fromEnum :: State -> Int Source # enumFrom :: State -> [State] Source # enumFromThen :: State -> State -> [State] Source # enumFromTo :: State -> State -> [State] Source # enumFromThenTo :: State -> State -> State -> [State] Source #
Show State Source #
Instance details Defined in Algebra.Graph.Labelled.Example.Automaton Methods showsPrec :: Int -> State -> ShowS Source # show :: State -> String Source # showList :: [State] -> ShowS Source #
Eq State Source #
Instance details Defined in Algebra.Graph.Labelled.Example.Automaton Methods (==) :: State -> State -> Bool Source # (/=) :: State -> State -> Bool Source #
Ord State Source #
Instance details Defined in Algebra.Graph.Labelled.Example.Automaton Methods compare :: State -> State -> Ordering Source # (<) :: State -> State -> Bool Source # (<=) :: State -> State -> Bool Source # (>) :: State -> State -> Bool Source # (>=) :: State -> State -> Bool Source # max :: State -> State -> State Source # min :: State -> State -> State Source #

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