algebraic-graphs-0.6.1: A library for algebraic graph construction and transformation
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

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 #

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 #

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 #

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 #

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 #

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 #

coffeeTeaAutomaton :: Automaton Alphabet State Source #

An example automaton for ordering coffee or tea. 

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

reachability :: Map State [ State ] Source #

The map of State reachability. 

reachability = Map.fromList $ map (s -> (s, reachable s order)) [Choice ..]

Or, when evaluated: 

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