dawg-0.5.0: Directed acyclic word graphs

Safe HaskellNone

Data.DAWG

Contents

Description

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.

Synopsis

DAWG type

data DAWG a Source

A Graph with one root from which all other graph nodes should be accesible.

Constructors

DAWG 

Fields

graph :: !(Graph (Maybe a))
 
root :: !Id
 

Instances

Eq a => Eq (DAWG a) 
(Eq (DAWG a), Ord a) => Ord (DAWG a) 
Show a => Show (DAWG a) 
(Ord a, Binary a) => Binary (DAWG a) 

Query

numStates :: DAWG a -> IntSource

Number of states in the underlying graph.

lookup :: String -> DAWG a -> Maybe aSource

Find value associated with the key.

Construction

empty :: Ord a => DAWG aSource

Empty DAWG.

Insertion

insert :: Ord a => String -> a -> DAWG a -> DAWG aSource

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

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

delete :: Ord a => String -> DAWG a -> DAWG aSource

Delete the key from the DAWG.

Conversion

elems :: DAWG a -> [a]Source

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

keys :: DAWG a -> [String]Source

Return all keys of the DAWG in ascending order.

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.

fromLang :: [String] -> DAWG ()Source

Make DAWG from the list of words. Annotate each word with the () value.