dawg-0.7.1: Directed acyclic word graphs

Safe HaskellNone




Internal representation of automata nodes specialized to a version with unlabeled edges.


Basic types

type ID = IntSource

Node identifier.

type Sym = IntSource

Internal representation of the transition symbol.


data Node a Source


Since Leaf nodes are distinguished from Branch nodes, two values equal with respect to == function are always kept in one Leaf node in the graph. It doesn't change the fact that to all Branch nodes one value is assigned through the epsilon transition.

Invariant: the eps identifier always points to the Leaf node. Edges in the edgeMap, on the other hand, point to Branch nodes.




eps :: !ID

Epsilon transition.

edgeMap :: !(VMap ID)

Labeled edges outgoing from the node.



value :: !a


Eq a => Eq (Node a) 
Show a => Show (Node a) 
Binary a => Binary (Node a) 

onSym :: Sym -> Node a -> Maybe IDSource

Transition function.

trans :: Node a -> [(Sym, ID)]Source

List of symbol/edge pairs outgoing from the node.

edges :: Node a -> [ID]Source

List of outgoing edges.

subst :: Sym -> ID -> Node a -> Node aSource

Substitue edge determined by a given symbol.

reIdent :: (ID -> ID) -> Node a -> Node aSource

Assign new identifiers.