dawg-ord-0.3: Directed acyclic word graphs

Safe HaskellNone
LanguageHaskell98

Data.DAWG.Ord

Contents

Description

A version of Int adapted to words with Ord instances.

Synopsis

DAWG type

data DAWG a Source

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

Instances

Eq a => Eq (DAWG a) Source 
Ord a => Ord (DAWG a) Source 
Show a => Show (DAWG a) Source 

type ID = Int Source

Node identifier.

root :: DAWG a -> ID Source

Root of the DAWG.

Query

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

Find value associated with the key.

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

Value stored in the given node.

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

A list of outgoing edges.

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

Follow the given transition from the given state.

Construction

empty :: DAWG a Source

Empty DAWG.

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

Construct DAWG from the list of (word, value) pairs.

Insertion

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

Insert the (key, value) pair into the DAWG.

Conversion

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

Return all key/value pairs in the DAWG in ascending key order.