dawg-ord-0.3.1: Directed acyclic word graphs

Safe HaskellNone
LanguageHaskell98

Data.DAWG.Int

Contents

Description

The module implements directed acyclic word graphs (DAWGs) internaly represented as /minimal acyclic deterministic finite-state automata/. The implementation provides a fast insert operation which can be used to build the DAWG structure incrementaly.

Alphabet symbols must have an Enum instance; see Ord if you look for a more generic solution.

Synopsis

DAWG type

data DAWG a Source

A directed acyclic word graph with phantom type a representing the type of alphabet elements.

Instances

type ID = Int Source

Node identifier.

root :: DAWG a -> ID Source

Foot of the DAWG.

Query

member :: Enum a => [a] -> DAWG a -> Bool Source

Is the word a member of the DAWG?

numStates :: DAWG a -> Int Source

Number of states in the automaton.

numEdges :: DAWG a -> Int Source

Number of edges in the automaton.

Traversal

accept :: ID -> DAWG a -> Bool Source

Does the identifer represent an accepting state?

edges :: Enum a => ID -> DAWG a -> [(a, ID)] Source

A list of outgoing edges.

follow :: Enum a => ID -> a -> DAWG a -> Maybe ID Source

Follow the given transition from the given state.

Construction

empty :: DAWG a Source

Empty DAWG.

fromList :: Enum a => [[a]] -> DAWG a Source

Construct DAWG from the list of words.

Insertion

insert :: Enum a => [a] -> DAWG a -> DAWG a Source

Insert the word into the DAWG.

Conversion

keys :: Enum a => DAWG a -> [[a]] Source

Return all keys in the DAWG in ascending key order.