Data.DAWG.Int

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.

Keys and values must provide an Enum instance; see the Ord module if you look for a more generic solution.

DAWG type

data DAWG a

A directed acyclic word graph with phantom type a representing the type of alphabet symbols. Type a must probide an Enum instance.

A DAWG is, semantically, a map from keys (sequences of as) to integral values (see Ord for a more generic version of DAWGs).

Instances

Eq (DAWG a)

Ord (DAWG a)

Show (DAWG a)

type ID = Int

Node identifier.

root :: DAWG a -> ID

Foot of the DAWG.

Query

lookup :: Enum a => [a] -> DAWG a -> Maybe Val

Find value associated with the key.

numStates :: DAWG a -> Int

Number of states in the automaton.

numEdges :: DAWG a -> Int

Number of edges in the automaton.

Traversal

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

Value stored in the given state.

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

A list of outgoing edges.

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

Follow the given transition from the given state.

Construction

empty :: DAWG a

Empty DAWG.

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

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

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

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 => [a] -> Val -> DAWG a -> DAWG a

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

insertWith :: Enum a => (Val -> Val -> Val) -> [a] -> Val -> DAWG a -> DAWG a

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 => [a] -> DAWG a -> DAWG a

Delete the key from the DAWG.

Conversion

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

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

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

Return all keys of the DAWG in ascending order.

elems :: DAWG a -> [Val]

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