This is a monadic graph rewriting library for port (hyper)graphs with a strong emphasis on nodes. It aims primarily at making it as convenient as possible to specify graph rewriting systems in Haskell and to experiment with them. There are a few aspects of the design to be pointed out:
- The graph structure is essentially representated as a collection of nodes. The nodes have a user-defined type, where each node features a list of
Ports to each of which an
Edgeis attached. Edges are unlabeled and can not exist autonomously, i.e. each edge is connected to at least one port. Two ports are connected if (and only if) they share the same edge. What is particularly convenient is how these ports can be modeled as constructor fields of a user-defined node type.
- An important abstraction used in this library is the multi-parameter type-class
View. It permits to expose a certain aspect of a node, allowing both to
updateit, while hiding the internal representation of the node. By that it is easy to specify the rewrite system in a way, that it can not only be applied to a graph with nodes of a fixed node type, but also to a
Graphwith polymorphic node type
n. The nodes merely have to expose values of type
vby means of defining a
Viewabstraction is also used to expose the nodes' ports (and therefore the graph structure) to this library.
Ruleare represented as
Patterns that return a
Patternis a branching scrutinisation of the graph that returns a result for every possible matching position in the graph. A
Ruleis essentially a
Patternthat returns a
Rewriteis a monadic modification of the graph structure. In a
Rewritepart can conveniently use the variables bound in the
For an example of a simple rewrite system, see the graph-rewriting-ski package, an implementation of SKI combinators. Together with the graph-rewriting-layout and the graph-rewriting-gl packages it is easy to build a graphical and interactive application to experiment with your rewrite system.
What the library does not (yet) offer are combinators to define strategies, since the emphasis of the project was to create an interactive graph-rewriting tool where rules and rewriting positions are selected manually.
mapping over nodes, graph creation, applying a
monadic graph scrutinisation
monadic graph modification
branching graph scrutinisation that keeps track of scrutinised nodes