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.
Transition backend has to be specified by a type signature. You can import the desired transition type and define your own dictionary construction function.
import Data.DAWG import Data.DAWG.Trans.Map (Trans) mkDict :: (Enum a, Ord b) => [([a], b)] -> DAWG Trans a b mkDict = fromList
- data DAWG t a b
- class (Ord (Node t a), Trans t) => MkNode t a
- numStates :: DAWG t a b -> Int
- lookup :: (Enum a, MkNode t b) => [a] -> DAWG t a b -> Maybe b
- empty :: MkNode t b => DAWG t a b
- fromList :: (Enum a, MkNode t b) => [([a], b)] -> DAWG t a b
- fromListWith :: (Enum a, MkNode t b) => (b -> b -> b) -> [([a], b)] -> DAWG t a b
- fromLang :: (Enum a, MkNode t ()) => [[a]] -> DAWG t a ()
- insert :: (Enum a, MkNode t b) => [a] -> b -> DAWG t a b -> DAWG t a b
- insertWith :: (Enum a, MkNode t b) => (b -> b -> b) -> [a] -> b -> DAWG t a b -> DAWG t a b
- delete :: (Enum a, MkNode t b) => [a] -> DAWG t a b -> DAWG t a b
- assocs :: (Enum a, MkNode t b) => DAWG t a b -> [([a], b)]
- keys :: (Enum a, MkNode t b) => DAWG t a b -> [[a]]
- elems :: MkNode t b => DAWG t a b -> [b]
DAWG type
A directed acyclic word graph with phantom type a
representing
type of alphabet elements.
class (Ord (Node t a), Trans t) => MkNode t a Source
Is t a valid transition map within the context of a-valued automata nodes? All transition implementations provided by the library are instances of this class.
Query
lookup :: (Enum a, MkNode t b) => [a] -> DAWG t a b -> Maybe bSource
Find value associated with the key.
Construction
fromList :: (Enum a, MkNode t b) => [([a], b)] -> DAWG t a bSource
Construct DAWG from the list of (word, value) pairs.
fromListWith :: (Enum a, MkNode t b) => (b -> b -> b) -> [([a], b)] -> DAWG t a bSource
Construct DAWG from the list of (word, value) pairs with a combining function. The combining function is applied strictly.
fromLang :: (Enum a, MkNode t ()) => [[a]] -> DAWG t a ()Source
Make DAWG from the list of words. Annotate each word with
the ()
value.
Insertion
insert :: (Enum a, MkNode t b) => [a] -> b -> DAWG t a b -> DAWG t a bSource
Insert the (key, value) pair into the DAWG.
insertWith :: (Enum a, MkNode t b) => (b -> b -> b) -> [a] -> b -> DAWG t a b -> DAWG t 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).
Deletion
delete :: (Enum a, MkNode t b) => [a] -> DAWG t a b -> DAWG t a bSource
Delete the key from the DAWG.
Conversion
assocs :: (Enum a, MkNode t b) => DAWG t a b -> [([a], b)]Source
Return all key/value pairs in the DAWG in ascending key order.