Safe Haskell | None |
---|---|
Language | Haskell2010 |
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.
See the Data.DAWG.Ord module if you look for a more generic
solution (which, for the moment, lacks some of the functionality provided
here, e.g. the delete
function).
Synopsis
- data DAWG
- type ID = Int
- type Sym = Int
- type Val = Int
- root :: DAWG -> ID
- lookup :: [Sym] -> DAWG -> Maybe Val
- numStates :: DAWG -> Int
- numEdges :: DAWG -> Int
- value :: ID -> DAWG -> Maybe Val
- edges :: ID -> DAWG -> [(Sym, ID)]
- follow :: ID -> Sym -> DAWG -> Maybe ID
- empty :: DAWG
- fromList :: [([Sym], Val)] -> DAWG
- fromListWith :: (Val -> Val -> Val) -> [([Sym], Val)] -> DAWG
- fromLang :: [[Sym]] -> DAWG
- insert :: [Sym] -> Val -> DAWG -> DAWG
- insertWith :: (Val -> Val -> Val) -> [Sym] -> Val -> DAWG -> DAWG
- delete :: [Sym] -> DAWG -> DAWG
- assocs :: DAWG -> [([Sym], Val)]
- keys :: DAWG -> [[Sym]]
- elems :: DAWG -> [Val]
DAWG type
A directed acyclic word graph (DAWG), which can be seen as a map
from keys (sequences of Sym
's) to values Val
.
See Data.DAWG.Ord for a more generic version of DAWGs.
Query
Traversal
follow :: ID -> Sym -> DAWG -> Maybe ID Source #
Follow a transition with the given symbol from the given state.
Construction
fromListWith :: (Val -> Val -> Val) -> [([Sym], Val)] -> DAWG Source #
Construct DAWG from the list of (key, value) pairs with a combining function. The combining function is applied strictly.
fromLang :: [[Sym]] -> DAWG Source #
Make DAWG from the list of words (by annotating each word with a dummy value).
Insertion
insertWith :: (Val -> Val -> Val) -> [Sym] -> Val -> DAWG -> DAWG Source #
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).