Data.DAWG.Node

Internal representation of automata nodes.

Basic types

type ID = Int

Node identifier.

type Sym = Int

Internal representation of the transition symbol.

Node

data Node a b

Two nodes (states) belong to the same equivalence class (and, consequently, they must be represented as one node in the graph) iff they are equal with respect to their values and outgoing edges.

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.

Constructors

Branch

Fields

eps :: !ID

Epsilon transition.

edgeMap :: !(VMap b)

Labeled edges outgoing from the node.

Leaf

Fields

value :: !a

Instances

(Eq a, Eq b, Unbox b) => Eq (Node a b)

(Eq (Node a b), Ord a, Ord b, Unbox b) => Ord (Node a b)

(Show a, Show b, Unbox b) => Show (Node a b)

(Unbox b, Binary a, Binary b) => Binary (Node a b)

onSym :: Unbox b => Sym -> Node a b -> Maybe b

Transition function.

trans :: Unbox b => Node a b -> [(Sym, b)]

List of symbol/edge pairs outgoing from the node.

edges :: Unbox b => Node a b -> [b]

List of outgoing edges.

subst :: Unbox b => Sym -> b -> Node a b -> Node a b

Substitue edge determined by a given symbol.

toGeneric :: Node a -> Node a (Edge ())

Yield generic version of a specialized node.

Edge

type Edge a = (ID, a)

Edge with label.

to :: Edge a -> ID

Destination ID.

label :: Edge a -> a

Edge label.

annotate :: a -> Edge b -> Edge a

Annotate edge wit a new label.

labeled :: a -> ID -> Edge a

Construct edge annotated with a given label.