Safe Haskell	None
Language	Haskell2010

Data.DAWG.Int

Contents

DAWG type
Query
Traversal
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.

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

data DAWG Source #

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.

Instances

Eq DAWG Source #
Instance details Defined in Data.DAWG.Int.Dynamic.Internal Methods (==) :: DAWG -> DAWG -> Bool # (/=) :: DAWG -> DAWG -> Bool #
Ord DAWG Source #
Instance details Defined in Data.DAWG.Int.Dynamic.Internal Methods compare :: DAWG -> DAWG -> Ordering # (<) :: DAWG -> DAWG -> Bool # (<=) :: DAWG -> DAWG -> Bool # (>) :: DAWG -> DAWG -> Bool # (>=) :: DAWG -> DAWG -> Bool # max :: DAWG -> DAWG -> DAWG # min :: DAWG -> DAWG -> DAWG #
Show DAWG Source #
Instance details Defined in Data.DAWG.Int.Dynamic.Internal Methods showsPrec :: Int -> DAWG -> ShowS # show :: DAWG -> String # showList :: [DAWG] -> ShowS #

type ID = Int Source #

Identifier of a DAWG node (automaton state).

type Sym = Int Source #

A transition symbol.

type Val = Int Source #

A type of DAWG values, stored in accept states.

root :: DAWG -> ID Source #

The root (start state) of the DAWG.

Query

lookup :: [Sym] -> DAWG -> Maybe Val Source #

Find value associated with the key.

numStates :: DAWG -> Int Source #

Number of states in the automaton.

numEdges :: DAWG -> Int Source #

Number of transitions in the automaton.

Traversal

value :: ID -> DAWG -> Maybe Val Source #

Value stored in the given automaton state.

edges :: ID -> DAWG -> [(Sym, ID)] Source #

A list of outgoing edges (automaton transitions).

follow :: ID -> Sym -> DAWG -> Maybe ID Source #

Follow a transition with the given symbol from the given state.

Construction

empty :: DAWG Source #

Empty DAWG.

fromList :: [([Sym], Val)] -> DAWG Source #

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

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

insert :: [Sym] -> Val -> DAWG -> DAWG Source #

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

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

Deletion

delete :: [Sym] -> DAWG -> DAWG Source #

Delete the key from the DAWG.

Conversion

assocs :: DAWG -> [([Sym], Val)] Source #

Return all key/value pairs in the DAWG in ascending key order.

keys :: DAWG -> [[Sym]] Source #

Return all keys of the DAWG in ascending order.

elems :: DAWG -> [Val] Source #

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