Safe Haskell	None
Language	Haskell2010

Data.Trie

Synopsis

Documentation

data Trie k v #

Constructors

Trie
Fields payloadT :: !v childrenT :: !(Map k (Trie k v))

Instances details

(Show v, Show k) => Show (Trie k v) #
Instance details Defined in Data.Trie Methods showsPrec :: Int -> Trie k v -> ShowS # show :: Trie k v -> String # showList :: [Trie k v] -> ShowS #
(Eq v, Eq k) => Eq (Trie k v) #
Instance details Defined in Data.Trie Methods (==) :: Trie k v -> Trie k v -> Bool # (/=) :: Trie k v -> Trie k v -> Bool #

rootT :: Ord k => v -> Trie k v #

\(O(1)\)

lookupT :: Ord k => [k] -> Trie k v -> Maybe v #

\(O(k \log w)\)

memberT :: Ord k => [k] -> Trie k v -> Bool #

\(O(k \log w)\)

modifyT :: Ord k => (v -> v) -> [k] -> Trie k v -> Trie k v #

\(O(k \log w)\) Does nothing if no such vertex exist.

modifyNodeT :: Ord k => (Trie k v -> Trie k v) -> [k] -> Trie k v -> Trie k v #

\(O(k \log w)\) Does nothing if no such vertex exist.

allocPathT :: Ord k => [k] -> v -> v -> Trie k v -> Trie k v #

\(O(k \log w)\) Non-existing nodes in the path will have the same payload.

allocModifyT :: Ord k => (v -> v) -> [k] -> v -> Trie k v -> Trie k v #

\(O(k \log w)\) Allocates a path from the root to a node and modifies the payload of the target node.

allocModifyPathT :: Ord k => (v -> v) -> [k] -> v -> Trie k v -> Trie k v #

\(O(k \log w)\) Allocates a path from the root to a node and modifies the payload of the node in the path.

modifyPathT :: Ord k => (v -> v) -> [k] -> Trie k v -> Trie k v #

\(O(k \log w)\) Modifies payload of a node and their parents.

pathT :: Ord k => [k] -> Trie k v -> [v] #

\(O(k \log w)\) Returns prefix payloads, excluding the root.