Safe Haskell | None |
---|

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.

- data DAWG a b
- lookup :: (Enum a, Ord b) => [a] -> DAWG a b -> Maybe b
- numStates :: DAWG a b -> Int
- numEdges :: DAWG a b -> Int
- empty :: Ord b => DAWG a b
- fromList :: (Enum a, Ord b) => [([a], b)] -> DAWG a b
- fromListWith :: (Enum a, Ord b) => (b -> b -> b) -> [([a], b)] -> DAWG a b
- fromLang :: Enum a => [[a]] -> DAWG a ()
- insert :: (Enum a, Ord b) => [a] -> b -> DAWG a b -> DAWG a b
- insertWith :: (Enum a, Ord b) => (b -> b -> b) -> [a] -> b -> DAWG a b -> DAWG a b
- delete :: (Enum a, Ord b) => [a] -> DAWG a b -> DAWG a b
- assocs :: (Enum a, Ord b) => DAWG a b -> [([a], b)]
- keys :: (Enum a, Ord b) => DAWG a b -> [[a]]
- elems :: Ord b => DAWG a b -> [b]

# DAWG type

A directed acyclic word graph with phantom type `a`

representing
type of alphabet elements.

# Query

# Construction

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

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

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

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 ()Source

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 bSource

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

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

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).