Data.DAWG.Dynamic

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

DAWG type

data DAWG a b

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

Instances

Eq b => Eq (DAWG a b)

Ord b => Ord (DAWG a b)

Show b => Show (DAWG a b)

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

Query

lookup :: (Enum a, Ord b) => [a] -> DAWG a b -> Maybe b

Find value associated with the key.

numStates :: DAWG a b -> Int

Number of states in the automaton.

numEdges :: DAWG a b -> Int

Number of edges in the automaton.

Construction

empty :: Ord b => DAWG a b

Empty DAWG.

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

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

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

Construct DAWG from the list of (word, value) pairs with a combining function. The combining function is applied strictly.

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

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

Insertion

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

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

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

Insert with a function, combining new value and old value. insertWith f key value d will insert the pair (key, value) into d if key does not exist in the DAWG. If the key does exist, the function will insert the pair (key, f new_value old_value).

Deletion

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

Delete the key from the DAWG.

Conversion

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

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

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

Return all keys of the DAWG in ascending order.

elems :: Ord b => DAWG a b -> [b]

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