Copyright	Guillaume Sabbagh 2021
License	GPL-3
Maintainer	guillaumesabbagh@protonmail.com
Stability	experimental
Portability	portable
Safe Haskell	Safe-Inferred
Language	Haskell2010

CompositionGraph.CompositionGraph

Contents

Types for a graph
Types for a morphism of composition graph
Types for a composition graph
Construction
Error gestion
Insertion
Modification
Deletion
Utility functions

Description

A CompositionGraph is the free category generated by a multidigraph quotiented by an equivalence relation on the paths of the graphs. A multidigraph is a directed multigraph which means that edges are oriented and there can be multiple arrows between two objects.

The underlying multidigraph is given by a list of nodes and a list of arrows.

The equivalence relation is given by a function on paths of the inductive graph.

The function mkCompositionGraph checks the structure of the category and is the preferred way of instantiatiating the CompositionGraph type. If the check takes too long because the category is big, you can use the CompositionGraph if you're sure that the category structure is respected.

Morphisms from different composition graphs should not be composed or compared, if they are, the behavior is undefined.

When taking subcategories of a composition graph, the composition law might lead to morphisms not existing anymore. It is not a problem because they are equivalent, it is only counterintuitive for human readability.

Example.ExampleCompositionGraph provides an example of composition graph construction.

Synopsis

type Arrow a b = (a, a, b)
type Graph a b = ([a], [Arrow a b])
type RawPath a b = [Arrow a b]
type Path a b = (a, RawPath a b, a)
data CGMorphism a b = CGMorphism {
- path :: Path a b
- compositionLaw :: CompositionLaw a b
}
type CompositionLaw a b = AssociationList (RawPath a b) (RawPath a b)
data CompositionGraph a b = CompositionGraph {
- graph :: Graph a b
- law :: CompositionLaw a b
}
mkCompositionGraph :: (Eq a, Eq b, Show a) => Graph a b -> CompositionLaw a b -> Either (FiniteCategoryError (CGMorphism a b) a) (CompositionGraph a b)
mkEmptyCompositionGraph :: CompositionGraph a b
finiteCategoryToCompositionGraph :: (FiniteCategory c m o, Morphism m o, Eq m, Eq o) => c -> (CompositionGraph o m, Diagram c m o (CompositionGraph o m) (CGMorphism o m) o)
generatedFiniteCategoryToCompositionGraph :: (GeneratedFiniteCategory c m o, Morphism m o, Eq m, Eq o) => c -> (CompositionGraph o m, Diagram c m o (CompositionGraph o m) (CGMorphism o m) o)
data CompositionGraphError a b
- = InsertMorphismNonExistantSource {
  - faultyMorph :: b
  - faultySrc :: a
  }
- | InsertMorphismNonExistantTarget {
  - faultyMorph :: b
  - faultyTgt :: a
  }
- | IdentifyGenerator {
  - gen :: CGMorphism a b
  }
- | UnidentifyNonExistantMorphism {
  - morph :: CGMorphism a b
  }
- | ResultingCategoryError (FiniteCategoryError (CGMorphism a b) a)
- | ReplaceNonExistantObject {
  - faultyObj :: a
  }
- | ReplaceCompositeMorphism {
  - composite :: CGMorphism a b
  }
- | DeleteIdentity {
  - faultyIdentity :: CGMorphism a b
  }
- | DeleteCompositeMorph {
  - composite :: CGMorphism a b
  }
- | DeleteNonExistantObjectMorph {
  - neMorph :: CGMorphism a b
  }
- | DeleteNonExistantObject {
  - faultyObj :: a
  }
insertObject :: (Eq a, Eq b) => CompositionGraph a b -> a -> (CompositionGraph a b, PartialFunctor (CompositionGraph a b) (CGMorphism a b) a)
insertMorphism :: (Eq a, Eq b) => CompositionGraph a b -> a -> a -> b -> Either (CompositionGraphError a b) (CompositionGraph a b, PartialFunctor (CompositionGraph a b) (CGMorphism a b) a)
identifyMorphisms :: (Eq a, Eq b) => CompositionGraph a b -> CGMorphism a b -> CGMorphism a b -> Either (CompositionGraphError a b) (CompositionGraph a b, PartialFunctor (CompositionGraph a b) (CGMorphism a b) a)
unidentifyMorphism :: (Eq a, Eq b) => CompositionGraph a b -> CGMorphism a b -> Either (CompositionGraphError a b) (CompositionGraph a b, PartialFunctor (CompositionGraph a b) (CGMorphism a b) a)
replaceObject :: (Eq a, Eq b) => CompositionGraph a b -> a -> a -> Either (CompositionGraphError a b) (CompositionGraph a b, PartialFunctor (CompositionGraph a b) (CGMorphism a b) a)
replaceMorphism :: (Eq a, Eq b) => CompositionGraph a b -> CGMorphism a b -> b -> Either (CompositionGraphError a b) (CompositionGraph a b, PartialFunctor (CompositionGraph a b) (CGMorphism a b) a)
deleteObject :: (Eq a, Eq b) => CompositionGraph a b -> a -> Either (CompositionGraphError a b) (CompositionGraph a b, PartialFunctor (CompositionGraph a b) (CGMorphism a b) a)
deleteMorphism :: (Eq a, Eq b) => CompositionGraph a b -> CGMorphism a b -> Either (CompositionGraphError a b) (CompositionGraph a b, PartialFunctor (CompositionGraph a b) (CGMorphism a b) a)
isGen :: Eq a => CGMorphism a b -> Bool
isComp :: Eq a => CGMorphism a b -> Bool
getLabel :: Eq a => CGMorphism a b -> Maybe b

Types for a graph

type Arrow a b = (a, a, b) Source #

An Arrow is a source node, a target node and an identifier (for example a unique label).

type Graph a b = ([a], [Arrow a b]) Source #

A Graph is a list of nodes and a list of arrows.

Types for a morphism of composition graph

type RawPath a b = [Arrow a b] Source #

A RawPath is a list of arrows.

type Path a b = (a, RawPath a b, a) Source #

A Path is a RawPath with a source and a target specified.

An empty path is an identity in a free category. Therefore, it is useful to keep the source and the target when the path is empty because there is one identity for each node of the graph. (We need to differentiate identites for each node.)

data CGMorphism a b Source #

The type CGMorphism is the type of composition graph morphisms.

It is a path with a composition law, it is necessary to keep the composition law of the composition graph in every morphism of the graph because we need it to compose two morphisms and the morphisms compose independently of the composition graph.

Constructors

CGMorphism
Fields path :: Path a b compositionLaw :: CompositionLaw a b

Instances

Instances details

(Eq a, Eq b) => Eq (CGMorphism a b) Source #
Instance details Defined in CompositionGraph.CompositionGraph Methods (==) :: CGMorphism a b -> CGMorphism a b -> Bool (/=) :: CGMorphism a b -> CGMorphism a b -> Bool
(Show a, Show b) => Show (CGMorphism a b) Source #
Instance details Defined in CompositionGraph.CompositionGraph Methods showsPrec :: Int -> CGMorphism a b -> ShowS show :: CGMorphism a b -> String showList :: [CGMorphism a b] -> ShowS
(PrettyPrintable a, PrettyPrintable b, Eq a, Eq b) => PrettyPrintable (CGMorphism a b) Source #
Instance details Defined in CompositionGraph.CompositionGraph Methods pprint :: CGMorphism a b -> String Source #
(Eq a, Eq b) => Morphism (CGMorphism a b) a Source #
Instance details Defined in CompositionGraph.CompositionGraph Methods (@) :: CGMorphism a b -> CGMorphism a b -> CGMorphism a b Source # source :: CGMorphism a b -> a Source # target :: CGMorphism a b -> a Source #
(Eq a, Eq b) => GeneratedFiniteCategory (CompositionGraph a b) (CGMorphism a b) a Source #
Instance details Defined in CompositionGraph.CompositionGraph Methods genAr :: CompositionGraph a b -> a -> a -> [CGMorphism a b] Source # decompose :: CompositionGraph a b -> CGMorphism a b -> [CGMorphism a b] Source # genArrows :: CompositionGraph a b -> [CGMorphism a b] Source #
(Eq a, Eq b) => FiniteCategory (CompositionGraph a b) (CGMorphism a b) a Source #
Instance details Defined in CompositionGraph.CompositionGraph Methods ob :: CompositionGraph a b -> [a] Source # identity :: CompositionGraph a b -> a -> CGMorphism a b Source # ar :: CompositionGraph a b -> a -> a -> [CGMorphism a b] Source # arrows :: CompositionGraph a b -> [CGMorphism a b] Source #

Types for a composition graph

type CompositionLaw a b = AssociationList (RawPath a b) (RawPath a b) Source #

A CompositionLaw is a Map that maps raw paths to smaller raw paths in order to simplify paths so that they don't compose infinitely many times when there is a cycle.

length (law ! p) <= length p

data CompositionGraph a b Source #

A composition graph is a graph with a composition law. Use mkCompositionGraph to instantiate it unless it takes too long.

Constructors

CompositionGraph
Fields graph :: Graph a b law :: CompositionLaw a b

Instances

Instances details

(Eq a, Eq b) => Eq (CompositionGraph a b) Source #
Instance details Defined in CompositionGraph.CompositionGraph Methods (==) :: CompositionGraph a b -> CompositionGraph a b -> Bool (/=) :: CompositionGraph a b -> CompositionGraph a b -> Bool
(Show a, Show b) => Show (CompositionGraph a b) Source #
Instance details Defined in CompositionGraph.CompositionGraph Methods showsPrec :: Int -> CompositionGraph a b -> ShowS show :: CompositionGraph a b -> String showList :: [CompositionGraph a b] -> ShowS
(PrettyPrintable a, PrettyPrintable b, Eq a, Eq b) => PrettyPrintable (CompositionGraph a b) Source #
Instance details Defined in CompositionGraph.CompositionGraph Methods pprint :: CompositionGraph a b -> String Source #
(Eq a, Eq b) => GeneratedFiniteCategory (CompositionGraph a b) (CGMorphism a b) a Source #
Instance details Defined in CompositionGraph.CompositionGraph Methods genAr :: CompositionGraph a b -> a -> a -> [CGMorphism a b] Source # decompose :: CompositionGraph a b -> CGMorphism a b -> [CGMorphism a b] Source # genArrows :: CompositionGraph a b -> [CGMorphism a b] Source #
(Eq a, Eq b) => FiniteCategory (CompositionGraph a b) (CGMorphism a b) a Source #
Instance details Defined in CompositionGraph.CompositionGraph Methods ob :: CompositionGraph a b -> [a] Source # identity :: CompositionGraph a b -> a -> CGMorphism a b Source # ar :: CompositionGraph a b -> a -> a -> [CGMorphism a b] Source # arrows :: CompositionGraph a b -> [CGMorphism a b] Source #

Construction

mkCompositionGraph :: (Eq a, Eq b, Show a) => Graph a b -> CompositionLaw a b -> Either (FiniteCategoryError (CGMorphism a b) a) (CompositionGraph a b) Source #

Constructs a CompositionGraph from a Graph and a CompositionLaw.

This is the preferred way of instantiating a CompositionGraph with mkEmptyCompositionGraph. This function checks the category structure, that is why it can return a FiniteCategoryError if the graph and the composition law provided don't produce a valid category. If this function takes too much time, use the CompositionGraph constructor at your own risk (it is your responsability to check the the category structure is valid).

mkEmptyCompositionGraph :: CompositionGraph a b Source #

Constructs an empty CompositionGraph.

Use insertObject, insertMorphism and identifyMorphisms to build a CompositionGraph from it.

finiteCategoryToCompositionGraph :: (FiniteCategory c m o, Morphism m o, Eq m, Eq o) => c -> (CompositionGraph o m, Diagram c m o (CompositionGraph o m) (CGMorphism o m) o) Source #

Transforms any FiniteCategory into a composition graph.

The composition graph will take more space in memory compared to the original category because the composition law is stored as a Data.Map.

Returns the CompositionGraph and an isofunctor as a Diagram.

generatedFiniteCategoryToCompositionGraph :: (GeneratedFiniteCategory c m o, Morphism m o, Eq m, Eq o) => c -> (CompositionGraph o m, Diagram c m o (CompositionGraph o m) (CGMorphism o m) o) Source #

Transforms any GeneratedFiniteCategory into a composition graph.

The composition graph will take more space in memory compared to the original category because the composition law is stored as a Data.Map.

Returns the CompositionGraph and an isofunctor as a Diagram.

Error gestion

data CompositionGraphError a b Source #

The datatype for composition graph construction errors.

Constructors

InsertMorphismNonExistantSource
Fields faultyMorph :: b faultySrc :: a
InsertMorphismNonExistantTarget
Fields faultyMorph :: b faultyTgt :: a
IdentifyGenerator
Fields gen :: CGMorphism a b
UnidentifyNonExistantMorphism
Fields morph :: CGMorphism a b
ResultingCategoryError (FiniteCategoryError (CGMorphism a b) a)
ReplaceNonExistantObject
Fields faultyObj :: a
ReplaceCompositeMorphism
Fields composite :: CGMorphism a b
DeleteIdentity
Fields faultyIdentity :: CGMorphism a b
DeleteCompositeMorph
Fields composite :: CGMorphism a b
DeleteNonExistantObjectMorph
Fields neMorph :: CGMorphism a b
DeleteNonExistantObject
Fields faultyObj :: a

Insertion

insertObject :: (Eq a, Eq b) => CompositionGraph a b -> a -> (CompositionGraph a b, PartialFunctor (CompositionGraph a b) (CGMorphism a b) a) Source #

Inserts an object in a CompositionGraph, returns the new CompositionGraph and a PartialFunctor which is the insertion functor.

insertMorphism :: (Eq a, Eq b) => CompositionGraph a b -> a -> a -> b -> Either (CompositionGraphError a b) (CompositionGraph a b, PartialFunctor (CompositionGraph a b) (CGMorphism a b) a) Source #

Inserts a morphism in a CompositionGraph, returns the new CompositionGraph and a PartialFunctor which is the insertion functor if it can, returns Nothing otherwise.

This function fails if the two nodes provided as source and target for the new morphism are not both in the composition graph.

The result may not be a valid CompositionGraph (the new morphism might close a loop creating infinitely many morphisms). You can use the function identifyMorphisms to transform it back into a valid CompositionGraph.

Modification

identifyMorphisms :: (Eq a, Eq b) => CompositionGraph a b -> CGMorphism a b -> CGMorphism a b -> Either (CompositionGraphError a b) (CompositionGraph a b, PartialFunctor (CompositionGraph a b) (CGMorphism a b) a) Source #

Identify two morphisms if it is possible, if not returns an error in a Left member.

You can only identify a composite morphism to another morphism.

If the resulting composition graph is not associative, it returns Left CompositionNotAssociative.

unidentifyMorphism :: (Eq a, Eq b) => CompositionGraph a b -> CGMorphism a b -> Either (CompositionGraphError a b) (CompositionGraph a b, PartialFunctor (CompositionGraph a b) (CGMorphism a b) a) Source #

Unidentify a morphism if it is possible, if not returns an error in a Left member.

Unidentifying a morphism means removing all entries in the composition law with results the morphism.

replaceObject :: (Eq a, Eq b) => CompositionGraph a b -> a -> a -> Either (CompositionGraphError a b) (CompositionGraph a b, PartialFunctor (CompositionGraph a b) (CGMorphism a b) a) Source #

Replaces an object with a new one, if the object to replace is not in the composition graph, returns Nothing.

It is different from deleting the object and inserting the new one because deleting an object deletes all leaving and coming arrows.

replaceMorphism :: (Eq a, Eq b) => CompositionGraph a b -> CGMorphism a b -> b -> Either (CompositionGraphError a b) (CompositionGraph a b, PartialFunctor (CompositionGraph a b) (CGMorphism a b) a) Source #

Replaces a generating morphism with a new one, if the morphism to replace is not a generator of the composition graph, returns Nothing.

It is different from deleting the morphism and inserting the new one because deleting an object deletes related composition law entries.

Deletion

deleteObject :: (Eq a, Eq b) => CompositionGraph a b -> a -> Either (CompositionGraphError a b) (CompositionGraph a b, PartialFunctor (CompositionGraph a b) (CGMorphism a b) a) Source #

Deletes an object and all morphism coming from it or leaving it.

deleteMorphism :: (Eq a, Eq b) => CompositionGraph a b -> CGMorphism a b -> Either (CompositionGraphError a b) (CompositionGraph a b, PartialFunctor (CompositionGraph a b) (CGMorphism a b) a) Source #

Deletes a generating morphism if it can, the generator should not be an identity.

Utility functions

isGen :: Eq a => CGMorphism a b -> Bool Source #

Optimized version of isGenerator for CompositionGraph.

isComp :: Eq a => CGMorphism a b -> Bool Source #

Optimized version of isComposite for CompositionGraph.

getLabel :: Eq a => CGMorphism a b -> Maybe b Source #

Returns the label of a generator arrow which is not an identity.