Safe Haskell | None |
---|
The module provides implementation of directed acyclic word graphs (DAWGs) also known as minimal acyclic finite-state automata. The implementation provides fast insert and delete operations which can be used to build the DAWG structure incrementaly.
- data DAWG a = DAWG {}
- numStates :: DAWG a -> Int
- lookup :: String -> DAWG a -> Maybe a
- empty :: Ord a => DAWG a
- insert :: Ord a => String -> a -> DAWG a -> DAWG a
- insertWith :: Ord a => (a -> a -> a) -> String -> a -> DAWG a -> DAWG a
- delete :: Ord a => String -> DAWG a -> DAWG a
- elems :: DAWG a -> [a]
- keys :: DAWG a -> [String]
- assocs :: DAWG a -> [(String, a)]
- fromList :: Ord a => [(String, a)] -> DAWG a
- fromListWith :: Ord a => (a -> a -> a) -> [(String, a)] -> DAWG a
- fromLang :: [String] -> DAWG ()
DAWG type
A Graph
with one root from which all other graph nodes should
be accesible.
Query
Construction
Insertion
insertWith :: Ord a => (a -> a -> a) -> String -> a -> DAWG a -> DAWG aSource
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
Conversion
assocs :: DAWG a -> [(String, a)]Source
Return all key/value pairs in the DAWG in ascending key order.
fromList :: Ord a => [(String, a)] -> DAWG aSource
Construct DAWG from the list of (word, value) pairs.
fromListWith :: Ord a => (a -> a -> a) -> [(String, a)] -> DAWG aSource
Construct DAWG from the list of (word, value) pairs with a combining function. The combining function is applied strictly.