packages feed

dawg-ord 0.3.1 → 0.4

raw patch · 10 files changed

+282/−180 lines, 10 filesdep ~basedep ~containers

Dependency ranges changed: base, containers

Files

dawg-ord.cabal view
@@ -1,15 +1,17 @@ name:               dawg-ord-version:            0.3.1+version:            0.4 synopsis:           Directed acyclic word graphs description:-    The library implements /directed acyclic word graphs/ (DAWGs)-    internally represented as /minimal acyclic deterministic-    finite-state automata/.+    The library implements /directed acyclic word graphs/ (DAWGs) internally+    represented as /minimal acyclic deterministic finite-state automata/.+    The implemented version of DAWG is, semantically, a map from+    sequences of alphabet symbols (keys) to values.     .-    The library allows to build DAWGs from words over any alphabet-    providing an `Ord` instance.+    The library allows to build DAWGs over any symbols and values+    provided that the both have `Ord` instances (see the+    `Data.DAWG.Ord` module).     It also provides a fast insert operation which can be used to-    build DAWGs on-the-fly.+    construct DAWGs on-the-fly. license:            BSD3 license-file:       LICENSE cabal-version:      >= 1.6
src/Data/DAWG/Gen/Trans/Vector.hs view
@@ -13,7 +13,7 @@   import Prelude hiding (lookup)--- import Control.Applicative ((<$>))+import Control.Applicative ((<$>)) -- import Data.Binary (Binary) -- import Data.Vector.Binary () import qualified Data.IntMap as M
src/Data/DAWG/Gen/Types.hs view
@@ -3,6 +3,7 @@ module Data.DAWG.Gen.Types ( ID , Sym+, Val ) where  -- | Node identifier.@@ -10,3 +11,6 @@  -- | Internal representation of an alphabet element. type Sym = Int++-- | Internal representation of an automaton value.+type Val = Int
src/Data/DAWG/Gen/Util.hs view
@@ -9,19 +9,19 @@ , combine ) where --- import Control.Applicative ((<$>))+import Control.Applicative ((<$>)) import Data.Bits (shiftR, xor) import Data.Vector.Unboxed (Unbox) import qualified Control.Monad.ST as ST import qualified Data.Vector.Unboxed as U import qualified Data.Vector.Unboxed.Mutable as UM --- | Given a vector of length @n@ strictly ascending with respect to a given--- comparison function, find an index at which the given element could be--- inserted while preserving sortedness.--- The 'Left' result indicates, that the 'EQ' element has been found,--- while the 'Right' result means otherwise.  Value of the 'Right'--- result is in the [0,n] range.+-- | Given a vector of length @n@ strictly ascending with respect to+-- a given comparison function, find an index at which the given+-- element could be inserted while preserving sortedness.  The 'Left'+-- result indicates, that the 'EQ' element has been found, while the+-- 'Right' result means otherwise.  Value of the 'Right' result is in+-- the [0,n] range. binarySearch :: Unbox a => (a -> Ordering) -> U.Vector a -> Either Int Int binarySearch cmp v = ST.runST $ do     w <- U.unsafeThaw v
src/Data/DAWG/Int.hs view
@@ -1,11 +1,10 @@--- | The module implements /directed acyclic word graphs/ (DAWGs)--- internaly represented as /minimal acyclic deterministic--- finite-state automata/.+-- | The module implements /directed acyclic word graphs/ (DAWGs) internaly+-- represented as /minimal acyclic deterministic finite-state automata/. -- The implementation provides a fast insert operation which can be -- used to build the DAWG structure incrementaly. ----- Alphabet symbols must have an `Enum` instance; see `Data.DAWG.Ord`--- if you look for a more generic solution.+-- Keys and values must provide an `Enum` instance; see the+-- `Data.DAWG.Ord` module if you look for a more generic solution.   module Data.DAWG.Int@@ -16,25 +15,34 @@ , root  -- * Query-, member+, lookup , numStates , numEdges  -- * Traversal-, accept+, value , edges , follow  -- * Construction , empty , fromList+, fromListWith+, fromLang -- ** Insertion , insert+, insertWith+-- ** Deletion+, delete  -- * Conversion+, assocs , keys+, elems ) where ++import           Prelude hiding (lookup)  import           Data.DAWG.Gen.Types import           Data.DAWG.Int.Dynamic
src/Data/DAWG/Int/Dynamic.hs view
@@ -13,32 +13,40 @@   DAWG (root)  -- * Query-, member+, lookup , numStates , numEdges  -- * Traversal-, accept+, value , edges , follow  -- * Construction , empty , fromList+, fromListWith+, fromLang -- ** Insertion , insert+, insertWith+-- ** Deletion+, delete  -- * Conversion+, assocs , keys+, elems ) where  --- import Control.Applicative ((<$>), (<*>))+import Prelude hiding (lookup)+import Control.Applicative ((<$>), (<*>)) import Control.Arrow (first) import Data.List (foldl') import qualified Control.Monad.State.Strict as S--- import           Control.Monad.Trans.Maybe--- import           Control.Monad.Trans.Class+import           Control.Monad.Trans.Maybe+import           Control.Monad.Trans.Class  import           Data.DAWG.Gen.Types import           Data.DAWG.Gen.Graph (Graph)@@ -73,7 +81,7 @@  -- | Leaf node with no children and 'Nothing' value. insertLeaf :: GraphM ID-insertLeaf = insertNode $ N.Node False T.empty+insertLeaf = insertNode $ N.Node Nothing T.empty     -- i <- insertNode (N.Leaf Nothing)     -- insertNode (N.Branch i T.empty) @@ -84,71 +92,69 @@   -- | Invariant: the identifier points to the 'Branch' node.--- TODO: which identifier?-insertM :: [Sym] -> ID -> GraphM ID-insertM (x:xs) i = do+insertM :: [Sym] -> Val -> ID -> GraphM ID+insertM (x:xs) y i = do     n <- nodeBy i     j <- case N.onSym x n of         Just j  -> return j         Nothing -> insertLeaf-    k <- insertM xs j+    k <- insertM xs y j     deleteNode n     insertNode (N.insert x k n)-insertM [] i = do+insertM [] y i = do     n <- nodeBy i     deleteNode n-    insertNode (n { N.accept = True })----- deleteM :: [Sym] -> ID -> GraphM ID--- deleteM (x:xs) i = do---     n <- nodeBy i---     case N.onSym x n of---         Nothing -> return i---         Just j  -> do---             k <- deleteM xs j---             deleteNode n---             insertNode (N.insert x k n)--- deleteM [] i = do---     n <- nodeBy i---     deleteNode n---     insertNode (n { N.value = Nothing })+    insertNode (n { N.value = Just y })  --- -- | Follow the path from the given identifier.--- followPath :: [Sym] -> ID -> MaybeT GraphM ID--- followPath (x:xs) i = do---     n <- lift $ nodeBy i---     j <- liftMaybe $ N.onSym x n---     followPath xs j--- followPath [] i = return i+insertWithM+    :: (Val -> Val -> Val)+    -> [Sym] -> Val -> ID -> GraphM ID+insertWithM f (x:xs) y i = do+    n <- nodeBy i+    j <- case N.onSym x n of+        Just j  -> return j+        Nothing -> insertLeaf+    k <- insertWithM f xs y j+    deleteNode n+    insertNode (N.insert x k n)+insertWithM f [] y i = do+    n <- nodeBy i+    deleteNode n+    let y'new = case N.value n of+            Just y' -> f y y'+            Nothing -> y+    insertNode (n { N.value = Just y'new })  --- | Follow the path from the given identifier.-followPath' :: [Sym] -> ID -> GraphM (Maybe ID)-followPath' (x:xs) i = do+deleteM :: [Sym] -> ID -> GraphM ID+deleteM (x:xs) i = do     n <- nodeBy i     case N.onSym x n of-         Nothing -> return Nothing-         Just j  -> followPath' xs j-followPath' [] i = return $ Just i+        Nothing -> return i+        Just j  -> do+            k <- deleteM xs j+            deleteNode n+            insertNode (N.insert x k n)+deleteM [] i = do+    n <- nodeBy i+    deleteNode n+    insertNode (n { N.value = Nothing })  -memberM :: [Sym] -> ID -> GraphM Bool-memberM xs i = do-    mj <- followPath' xs i-    case mj of-         Nothing    -> return False-         Just j     -> N.accept <$> nodeBy j-+-- | Follow the path from the given identifier.+followPath :: [Sym] -> ID -> MaybeT GraphM ID+followPath (x:xs) i = do+    n <- lift $ nodeBy i+    j <- liftMaybe $ N.onSym x n+    followPath xs j+followPath [] i = return i+     --- memberM :: [Sym] -> ID -> GraphM Bool--- memberM xs i = fmap justTrue . runMaybeT $ do---     j <- followPath xs i---     lift $ N.accept <$> nodeBy j---   where---     justTrue (Just True) = True---     justTrue _           = False+lookupM :: [Sym] -> ID -> GraphM (Maybe Val)+lookupM xs i = runMaybeT $ do+    j <- followPath xs i+    MaybeT $ N.value <$> nodeBy j   ------------------------------------------------------------@@ -158,16 +164,15 @@  -- | Return all (key, value) pairs in ascending key order in the -- sub-DAWG determined by the given node ID.-subPairs :: Graph N.Node -> ID -> [[Sym]]+subPairs :: Graph N.Node -> ID -> [([Sym], Val)] subPairs g i =     here n ++ concatMap there (N.edges n)   where     n = G.nodeBy i g-    here v = [[] | N.accept v]---     here v = if N.accept v---         then [[]]---         else []-    there (sym, j) = map (sym:) (subPairs g j)+    here v = case N.value v of+        Just x  -> [([], x)]+        Nothing -> []+    there (sym, j) = map (first (sym:)) (subPairs g j)   -- | Empty DAWG.@@ -187,32 +192,48 @@ numEdges = sum . map (length . N.edges) . G.nodes . graph  --- | Insert the word into the DAWG.-insert :: Enum a => [a] -> DAWG a -> DAWG a-insert xs' d =+-- | Insert the (key, value) pair into the DAWG.+insert :: Enum a => [a] -> Val -> DAWG a -> DAWG a+insert xs' y d =     let xs = map fromEnum xs'-        (i, g) = S.runState (insertM xs $ root d) (graph d)+        (i, g) = S.runState (insertM xs y $ root d) (graph d)     in  DAWG g i {-# INLINE insert #-}  --- -- | Delete the key from the DAWG.--- delete :: Enum a => [a] -> DAWG a -> DAWG a--- delete xs' d =---     let xs = map fromEnum xs'---         (i, g) = S.runState (deleteM xs $ root d) (graph d)---     in  DAWG g i--- {-# SPECIALIZE delete :: String -> DAWG Char -> DAWG Char #-}+-- | 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).+insertWith+    :: Enum a => (Val -> Val -> Val)+    -> [a] -> Val -> DAWG a -> DAWG a+insertWith f xs' y d =+    let xs = map fromEnum xs'+        (i, g) = S.runState (insertWithM f xs y $ root d) (graph d)+    in  DAWG g i+{-# SPECIALIZE insertWith+        :: (Val -> Val -> Val) -> String -> Val+        -> DAWG Char -> DAWG Char #-}  --- | Is the word a member of the DAWG?-member :: Enum a => [a] -> DAWG a -> Bool-member xs' d =+-- | Delete the key from the DAWG.+delete :: Enum a => [a] -> DAWG a -> DAWG a+delete xs' d =     let xs = map fromEnum xs'-    in  S.evalState (memberM xs $ root d) (graph d)-{-# SPECIALIZE member :: String -> DAWG Char -> Bool #-}+        (i, g) = S.runState (deleteM xs $ root d) (graph d)+    in  DAWG g i+{-# SPECIALIZE delete :: String -> DAWG Char -> DAWG Char #-}  +-- | Find value associated with the key.+lookup :: Enum a => [a] -> DAWG a -> Maybe Val+lookup xs' d =+    let xs = map fromEnum xs'+    in  S.evalState (lookupM xs $ root d) (graph d)+{-# SPECIALIZE lookup :: String -> DAWG Char -> Maybe Val #-}++ -- -- | Find all (key, value) pairs such that key is prefixed -- -- with the given string. -- withPrefix :: (Enum a, Ord b) => [a] -> DAWG a b -> [([a], b)]@@ -226,22 +247,54 @@ --     -> [(String, b)] #-}  --- | Return all keys in the DAWG in ascending key order.-keys :: Enum a => DAWG a -> [[a]]-keys-    = map (map toEnum)+-- | Return all key/value pairs in the DAWG in ascending key order.+assocs :: Enum a => DAWG a -> [([a], Val)]+assocs+    = map (first (map toEnum))     . (subPairs <$> graph <*> root)+{-# SPECIALIZE assocs :: DAWG Char -> [(String, Val)] #-}+++-- | Return all keys of the DAWG in ascending order.+keys :: Enum a => DAWG a -> [[a]]+keys = map fst . assocs {-# SPECIALIZE keys :: DAWG Char -> [String] #-}  --- | Construct DAWG from the list of words.-fromList :: Enum a => [[a]] -> DAWG a+-- | Return all elements of the DAWG in the ascending order of their keys.+elems :: DAWG a -> [Val]+elems = map snd . (subPairs <$> graph <*> root)+++-- | Construct DAWG from the list of (word, value) pairs.+fromList :: Enum a => [([a], Val)] -> DAWG a fromList xs =-    let update t x = insert x t+    let update t (x, v) = insert x v t     in  foldl' update empty xs-{-# SPECIALIZE fromList :: [String] -> DAWG Char #-}+{-# INLINE fromList #-}  +-- | Construct DAWG from the list of (word, value) pairs+-- with a combining function.  The combining function is+-- applied strictly.+fromListWith+    :: Enum a => (Val -> Val -> Val)+    -> [([a], Val)] -> DAWG a+fromListWith f xs =+    let update t (x, v) = insertWith f x v t+    in  foldl' update empty xs+{-# SPECIALIZE fromListWith+        :: (Val -> Val -> Val)+        -> [(String, Val)] -> DAWG Char #-}+++-- | Make DAWG from the list of words.  Annotate each word with+-- the @()@ value.+fromLang :: Enum a => [[a]] -> DAWG a+fromLang xs = fromList [(x, 0) | x <- xs]+{-# SPECIALIZE fromLang :: [String] -> DAWG Char #-}++ ------------------------------------------------------------ -- Traversal ------------------------------------------------------------@@ -257,21 +310,15 @@ {-# SPECIALIZE edges :: ID -> DAWG Int  -> [(Int, ID)]  #-}  --- | Does the identifer represent an accepting state?-accept :: ID -> DAWG a -> Bool-accept i = N.accept . G.nodeBy i . graph----- -- | Follow the given transition from the given state.--- follow :: Enum a => ID -> a -> DAWG a -> Maybe ID--- follow i x DAWG{..} = flip S.evalState graph $ runMaybeT $---     followPath [fromEnum x] i+-- | Value stored in the given state.+value :: ID -> DAWG a -> Maybe Val+value i = N.value . G.nodeBy i . graph   -- | Follow the given transition from the given state. follow :: Enum a => ID -> a -> DAWG a -> Maybe ID-follow i x DAWG{..} = flip S.evalState graph $-    followPath' [fromEnum x] i+follow i x DAWG{..} = flip S.evalState graph $ runMaybeT $+    followPath [fromEnum x] i   ------------------------------------------------------------@@ -279,6 +326,6 @@ ------------------------------------------------------------  --- liftMaybe :: Monad m => Maybe a -> MaybeT m a--- liftMaybe = MaybeT . return--- {-# INLINE liftMaybe #-}+liftMaybe :: Monad m => Maybe a -> MaybeT m a+liftMaybe = MaybeT . return+{-# INLINE liftMaybe #-}
src/Data/DAWG/Int/Dynamic/Internal.hs view
@@ -16,8 +16,13 @@ import qualified Data.DAWG.Int.Dynamic.Node as N  --- | A directed acyclic word graph with phantom type @a@--- representing the type of alphabet elements.+-- | A directed acyclic word graph with phantom type `a`+-- representing the type of alphabet symbols.+-- Type `a` must probide an `Enum` instance.+--+-- A DAWG is, semantically, a map from keys (sequences of `a`s) to+-- integral values (see `Data.DAWG.Ord` for a more generic version of+-- DAWGs). data DAWG a = DAWG     { graph :: !(Graph N.Node)     -- | Foot of the DAWG.
src/Data/DAWG/Int/Dynamic/Node.hs view
@@ -29,17 +29,17 @@ -- iff they are equal with respect to their values and outgoing -- edges. data Node = Node {-    -- | Accepting state or no?-      accept    :: !Bool+    -- | Value stored in the node.+      value    :: !(Maybe Val)     -- | Transition map (outgoing edges).     , transMap :: !(H.Hashed Trans)     } deriving (Show, Eq, Ord)  instance Hash Node where-    hash Node{..} = combine (hash accept) (H.hash transMap)+    hash Node{..} = combine (hash value) (H.hash transMap)  -- instance Binary Node where---     put Node{..} = put accept >> put transMap+--     put Node{..} = put value >> put transMap --     get = Node <$> get <*> get  @@ -63,5 +63,5 @@  -- | Substitue edge determined by a given symbol. insert :: Sym -> ID -> Node -> Node-insert x i (Node a t) = Node a (T.insert x i t)+insert x i (Node w t) = Node w (T.insert x i t) {-# INLINE insert #-}
src/Data/DAWG/Ord.hs view
@@ -1,5 +1,5 @@--- | A version of `Data.DAWG.Int` adapted to words with `Ord`--- instances.+-- | A version of `Data.DAWG.Int` adapted to keys and values with+-- `Ord` instances.   module Data.DAWG.Ord@@ -10,25 +10,30 @@ , root  -- * Query-, member+, lookup , numStates , numEdges  -- * Traversal-, accept+, value , edges , follow  -- * Construction , empty , fromList+, fromLang -- ** Insertion , insert  -- * Conversion+, assocs , keys+, elems ) where ++import           Prelude hiding (lookup)  import           Data.DAWG.Gen.Types import           Data.DAWG.Ord.Dynamic
src/Data/DAWG/Ord/Dynamic.hs view
@@ -1,8 +1,8 @@ {-# LANGUAGE RecordWildCards #-}  --- | A version of `Data.DAWG.Int.Dynamic` adapted to words with `Ord`--- instances.+-- | A version of `Data.DAWG.Int.Dynamic` adapted to+-- keys and values with `Ord` instances.   module Data.DAWG.Ord.Dynamic@@ -12,26 +12,30 @@ , root  -- * Query-, member+, lookup , numStates , numEdges  -- * Traversal-, accept+, value , edges , follow  -- * Construction , empty , fromList+, fromLang -- ** Insertion , insert  -- * Conversion+, assocs , keys+, elems ) where  +import           Prelude hiding (lookup) import           Data.List (foldl') import           Control.Arrow (first) import qualified Control.Monad.State.Strict as S@@ -48,17 +52,23 @@ ------------------------------------------------------------  --- | A directed acyclic word graph with type `a` representing the--- type of alphabet elements.-data DAWG a = DAWG+-- | A directed acyclic word graph (DAWG) with type `a` representing+-- the type of alphabet symbols (over which keys are constructued)+-- and type `b` -- the type of values.+--+-- A DAWG is, semantically, a map from keys (sequences of `a`s) to+-- values `b`.+data DAWG a b = DAWG     { intDAWG   :: D.DAWG Sym     , symMap    :: M.Map a Int     , symMapR   :: M.Map Int a+    , valMap    :: M.Map b Int+    , valMapR   :: M.Map Int b     } deriving (Show, Eq, Ord)   -- | Root of the DAWG.-root :: DAWG a -> ID+root :: DAWG a b -> ID root = D.root . intDAWG  @@ -68,12 +78,12 @@   -- | DAWG monad.-type DM a = S.State (DAWG a)+type DM a b = S.State (DAWG a b)   -- | Register new key in the underlying automaton. -- TODO: We could optimize it.-addSym :: Ord a => a -> DM a Int+addSym :: Ord a => a -> DM a b Int addSym x = S.state $ \dawg@DAWG{..} ->     let y = fromMaybe (M.size symMap) (M.lookup x symMap) --     let y = case M.lookup x symMap of@@ -85,12 +95,23 @@   -- | Register new key in the underlying automaton.-addKey :: Ord a => [a] -> DM a [Int]+addKey :: Ord a => [a] -> DM a b [Int] addKey = mapM addSym  +-- | Register new value in the underlying automaton.+-- TODO: We could optimize it.+addVal :: Ord b => b -> DM a b Int+addVal x = S.state $ \dawg@DAWG{..} ->+    let y = case M.lookup x valMap of+            Nothing -> M.size valMap+            Just k  -> k+    in  (y, dawg+            { valMap  = M.insert x y valMap+            , valMapR = M.insert y x valMapR })+ -- | Run the DAGW monad.-runDM :: DM a c -> DAWG a -> (c, DAWG a)+runDM :: DM a b c -> DAWG a b -> (c, DAWG a b) runDM = S.runState  @@ -100,26 +121,27 @@   -- | Empty DAWG.-empty :: DAWG a-empty = DAWG D.empty M.empty M.empty+empty :: DAWG a b+empty = DAWG D.empty M.empty M.empty M.empty M.empty   -- | Number of states in the automaton.-numStates :: DAWG a -> Int+numStates :: DAWG a b -> Int numStates = D.numStates . intDAWG   -- | Number of edges in the automaton.-numEdges :: DAWG a -> Int+numEdges :: DAWG a b -> Int numEdges = D.numEdges . intDAWG  --- | Insert the word into the DAWG.-insert :: (Ord a) => [a] -> DAWG a -> DAWG a-insert xs0 dag0 = snd $ flip runDM dag0 $ do+-- | Insert the (key, value) pair into the DAWG.+insert :: (Ord a, Ord b) => [a] -> b -> DAWG a b -> DAWG a b+insert xs0 y0 dag0 = snd $ flip runDM dag0 $ do     xs <- addKey xs0+    y  <- addVal y0     S.modify $ \dag -> dag-        {intDAWG = D.insert xs (intDAWG dag)}+        {intDAWG = D.insert xs y (intDAWG dag)}   -- -- | Insert with a function, combining new value and old value.@@ -143,60 +165,69 @@ -- {-# SPECIALIZE delete :: Ord b => String -> DAWG Char b -> DAWG Char b #-}  --- | Is the word a member of the DAWG?-member :: (Ord a) => [a] -> DAWG a -> Bool-member xs0 DAWG{..} = justTrue $ do-    xs <- mapM (`M.lookup` symMap) xs0-    return $ D.member xs intDAWG+-- | Find value associated with the key.+lookup :: (Ord a, Ord b) => [a] -> DAWG a b -> Maybe b+lookup xs0 DAWG{..} = do+    xs <- mapM (flip M.lookup symMap) xs0+    y  <- D.lookup xs intDAWG+    M.lookup y valMapR  --- | Return all keys in the DAWG in ascending key order.-keys :: DAWG a -> [[a]]-keys DAWG{..} =-    [ decodeKey xs-    | xs <- D.keys intDAWG ]+-- | Return all key/value pairs in the DAWG in ascending key order.+assocs :: DAWG a b -> [([a], b)]+assocs DAWG{..} = +    [ (decodeKey xs, decodeVal y)+    | (xs, y) <- D.assocs intDAWG ]   where     decodeKey = map decodeSym     decodeSym x = symMapR M.! x+    decodeVal x = valMapR M.! x  --- | Construct DAWG from the list of words.-fromList :: (Ord a) => [[a]] -> DAWG a+-- | Return all keys of the DAWG in ascending order.+keys :: DAWG a b -> [[a]]+keys = map fst . assocs+++-- | Return all elements of the DAWG in the ascending order of their keys.+elems :: DAWG a b -> [b]+elems = map snd . assocs+++-- | Construct DAWG from the list of (word, value) pairs.+fromList :: (Ord a, Ord b) => [([a], b)] -> DAWG a b fromList xs =-    let update t x = insert x t+    let update t (x, v) = insert x v t     in  foldl' update empty xs  +-- | Make DAWG from the list of words.  Annotate each word with+-- the @()@ value.+fromLang :: Ord a => [[a]] -> DAWG a ()+fromLang xs = fromList [(x, ()) | x <- xs]++ ------------------------------------------------------------ -- Traversal ------------------------------------------------------------  --- | Does the identifer represent an accepting state?-accept :: ID -> DAWG a -> Bool-accept i DAWG{..} = D.accept i intDAWG+-- | Value stored in the given node.+value :: ID -> DAWG a b -> Maybe b+value i DAWG{..}  = do+    x <- D.value i intDAWG+    M.lookup x valMapR   -- | A list of outgoing edges.-edges :: ID -> DAWG a -> [(a, ID)]+edges :: ID -> DAWG a b -> [(a, ID)] edges i DAWG{..} = map     (first (symMapR M.!))     (D.edges i intDAWG)   -- | Follow the given transition from the given state.-follow :: Ord a => ID -> a -> DAWG a -> Maybe ID+follow :: Ord a => ID -> a -> DAWG a b -> Maybe ID follow i x DAWG{..} = do     y <- M.lookup x symMap     D.follow i y intDAWG------------------------------------------------------------------ Misc------------------------------------------------------------------ | Is it `Just True`?-justTrue :: Maybe Bool -> Bool-justTrue (Just True) = True-justTrue _           = False