Data.DAWG.Ord

A version of Data.DAWG.Int adapted to keys and values with Ord instances.

DAWG type

data DAWG a b

A directed acyclic word graph (DAWG) with type a representing the type of alphabet symbols (over which keys are constructed) and type b -- the type of values.

A DAWG can be seen as a map from keys (sequences of a's) to values b.

Instances

(Eq a, Eq b) => Eq (DAWG a b)

Defined in Data.DAWG.Ord.Dynamic

Methods

(==) :: DAWG a b -> DAWG a b -> Bool

(/=) :: DAWG a b -> DAWG a b -> Bool

(Ord a, Ord b) => Ord (DAWG a b)

Defined in Data.DAWG.Ord.Dynamic

Methods

compare :: DAWG a b -> DAWG a b -> Ordering

(<) :: DAWG a b -> DAWG a b -> Bool

(<=) :: DAWG a b -> DAWG a b -> Bool

(>) :: DAWG a b -> DAWG a b -> Bool

(>=) :: DAWG a b -> DAWG a b -> Bool

max :: DAWG a b -> DAWG a b -> DAWG a b

min :: DAWG a b -> DAWG a b -> DAWG a b

(Show a, Show b) => Show (DAWG a b)

Defined in Data.DAWG.Ord.Dynamic

Methods

showsPrec :: Int -> DAWG a b -> ShowS

show :: DAWG a b -> String

showList :: [DAWG a b] -> ShowS

type ID = Int

Identifier of a DAWG node (automaton state).

root :: DAWG a b -> ID

The root (start state) of the DAWG.

Query

lookup :: Ord a => [a] -> DAWG a b -> Maybe b

Find value associated with the key.

numStates :: DAWG a b -> Int

Number of states in the underlying automaton.

numEdges :: DAWG a b -> Int

Number of transitions in the underlying automaton.

Traversal

value :: ID -> DAWG a b -> Maybe b

Value stored in the given automaton state.

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

A list of outgoing edges (automaton transitions).

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

Follow a transition with the given symbol from the given state.

Construction

empty :: DAWG a b

Empty DAWG.

fromList :: (Ord a, Ord b) => [([a], b)] -> DAWG a b

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

fromLang :: Ord a => [[a]] -> DAWG a ()

Make DAWG from the list of words (annotate each word with the () value).

Insertion

insert :: (Ord a, Ord b) => [a] -> b -> DAWG a b -> DAWG a b

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

Conversion

assocs :: DAWG a b -> [([a], b)]

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

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

Return all keys of the DAWG in ascending order.

elems :: DAWG a b -> [b]

Return all elements of the DAWG in the ascending order of their keys.