Safe Haskell	None
Language	Haskell2010

Data.DAWG.Internal

Contents

DAWG type
Query
Construction
- Insertion
- Deletion
Conversion

Description

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.

Synopsis

data DAWG t a b = DAWG {
- graph :: !(Graph (Node t b))
- root :: !ID
}
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

data DAWG t a b Source #

A directed acyclic word graph with phantom type a representing type of alphabet elements.

Constructors

DAWG
Fields graph :: !(Graph (Node t b)) root :: !ID

Instances

(Show t, Show b) => Show (DAWG t a b) Source #
Instance details Defined in Data.DAWG.Internal Methods showsPrec :: Int -> DAWG t a b -> ShowS # show :: DAWG t a b -> String # showList :: [DAWG t a b] -> ShowS #
(MkNode t b, Binary t, Binary b) => Binary (DAWG t a b) Source #
Instance details Defined in Data.DAWG.Internal Methods put :: DAWG t a b -> Put # get :: Get (DAWG t a b) # putList :: [DAWG t a b] -> Put #

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.

Instances

(Ord (Node t a), Trans t) => MkNode t a Source #
Instance details Defined in Data.DAWG.Internal

Query

numStates :: DAWG t a b -> Int Source #

Number of states in the underlying graph.

lookup :: (Enum a, MkNode t b) => [a] -> DAWG t a b -> Maybe b Source #

Find value associated with the key.

Construction

empty :: MkNode t b => DAWG t a b Source #

Empty DAWG.

fromList :: (Enum a, MkNode t b) => [([a], b)] -> DAWG t a b Source #

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

fromListWith :: (Enum a, MkNode t b) => (b -> b -> b) -> [([a], b)] -> DAWG t a b Source #

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 b Source #

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

Deletion

delete :: (Enum a, MkNode t b) => [a] -> DAWG t a b -> DAWG t a b Source #

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.

keys :: (Enum a, MkNode t b) => DAWG t a b -> [[a]] Source #

Return all keys of the DAWG in ascending order.

elems :: MkNode t b => DAWG t a b -> [b] Source #

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