| Copyright | Copyright (c) 2008--2015 wren gayle romano 2019 michael j. klein |
|---|---|
| License | BSD3 |
| Maintainer | lambdamichael@gmail.com |
| Stability | experimental |
| Safe Haskell | None |
| Language | Haskell98 |
Data.Trie.Text.Internal
Contents
Description
Synopsis
- data Trie a
- showTrie :: Show a => Trie a -> String
- breakMaximalPrefix :: Text -> Text -> (Text, Text, Text)
- empty :: Trie a
- null :: Trie a -> Bool
- singleton :: Text -> a -> Trie a
- size :: Trie a -> Int
- foldrWithKey :: (Text -> a -> b -> b) -> b -> Trie a -> b
- toListBy :: (Text -> a -> b) -> Trie a -> [b]
- lookupBy_ :: (Maybe a -> Trie a -> b) -> b -> (Trie a -> b) -> Text -> Trie a -> b
- submap :: Text -> Trie a -> Trie a
- match_ :: Trie a -> Text -> Maybe (Int, a)
- matches_ :: Trie a -> Text -> [(Int, a)]
- alterBy :: (Text -> a -> Maybe a -> Maybe a) -> Text -> a -> Trie a -> Trie a
- alterBy_ :: (Text -> a -> Maybe a -> Trie a -> (Maybe a, Trie a)) -> Text -> a -> Trie a -> Trie a
- adjustBy :: (Text -> a -> a -> a) -> Text -> a -> Trie a -> Trie a
- mergeBy :: (a -> a -> Maybe a) -> Trie a -> Trie a -> Trie a
- mapBy :: (Text -> a -> Maybe b) -> Trie a -> Trie b
- filterMap :: (a -> Maybe b) -> Trie a -> Trie b
- contextualMap :: (a -> Trie a -> b) -> Trie a -> Trie b
- contextualMap' :: (a -> Trie a -> b) -> Trie a -> Trie b
- contextualFilterMap :: (a -> Trie a -> Maybe b) -> Trie a -> Trie b
- contextualMapBy :: (Text -> a -> Trie a -> Maybe b) -> Trie a -> Trie b
- minAssoc :: Trie a -> Maybe (Text, a)
- maxAssoc :: Trie a -> Maybe (Text, a)
- updateMinViewBy :: (Text -> a -> Maybe a) -> Trie a -> Maybe (Text, a, Trie a)
- updateMaxViewBy :: (Text -> a -> Maybe a) -> Trie a -> Maybe (Text, a, Trie a)
Data types
A map from ByteStrings to a. For all the generic functions,
note that tries are strict in the Maybe but not in a.
The Monad instance is strange. If a key k1 is a prefix of
other keys, then results from binding the value at k1 will
override values from longer keys when they collide. If this is
useful for anything, or if there's a more sensible instance, I'd
be curious to know.
Instances
| Monad Trie Source # | |
| Functor Trie Source # | |
| Applicative Trie Source # | |
| Foldable Trie Source # | |
Defined in Data.Trie.Text.Internal Methods fold :: Monoid m => Trie m -> m # foldMap :: Monoid m => (a -> m) -> Trie a -> m # foldr :: (a -> b -> b) -> b -> Trie a -> b # foldr' :: (a -> b -> b) -> b -> Trie a -> b # foldl :: (b -> a -> b) -> b -> Trie a -> b # foldl' :: (b -> a -> b) -> b -> Trie a -> b # foldr1 :: (a -> a -> a) -> Trie a -> a # foldl1 :: (a -> a -> a) -> Trie a -> a # elem :: Eq a => a -> Trie a -> Bool # maximum :: Ord a => Trie a -> a # | |
| Traversable Trie Source # | |
| Eq a => Eq (Trie a) Source # | |
| Show a => Show (Trie a) Source # | |
| Generic a => Generic (Trie a) Source # | |
| Semigroup a => Semigroup (Trie a) Source # | |
| Monoid a => Monoid (Trie a) Source # | |
| Binary a => Binary (Trie a) Source # | |
| Generic1 Trie Source # | |
| type Rep (Trie a) Source # | |
Defined in Data.Trie.Text.Internal | |
| type Rep1 Trie Source # | |
Defined in Data.Trie.Text.Internal | |
Functions for Text
breakMaximalPrefix :: Text -> Text -> (Text, Text, Text) Source #
commonPrefixes unless Nothing,
in which case ( is returnedempty, x, y)
Basic functions
Conversion and folding functions
foldrWithKey :: (Text -> a -> b -> b) -> b -> Trie a -> b Source #
Convert a trie into a list (in key-sorted order) using a function, folding the list as we go.
toListBy :: (Text -> a -> b) -> Trie a -> [b] Source #
Convert a trie into a list using a function. Resulting values are in key-sorted order.
Query functions
lookupBy_ :: (Maybe a -> Trie a -> b) -> b -> (Trie a -> b) -> Text -> Trie a -> b Source #
Generic function to find a value (if it exists) and the subtrie rooted at the prefix. The first function argument is called if and only if a node is exactly reachable by the query; if no node is exactly reachable the default value is used; if the middle of an arc is reached, the second function argument is used.
This function is intended for internal use. For the public-facing
version, see lookupBy in Data.Trie.
submap :: Text -> Trie a -> Trie a Source #
Return the subtrie containing all keys beginning with a prefix.
match_ :: Trie a -> Text -> Maybe (Int, a) Source #
Given a query, find the longest prefix with an associated value in the trie, returning the length of that prefix and the associated value.
This function may not have the most useful return type. For a
version that returns the prefix itself as well as the remaining
string, see match in Data.Trie.
matches_ :: Trie a -> Text -> [(Int, a)] Source #
Given a query, find all prefixes with associated values in the trie, returning their lengths and values. This function is a good producer for list fusion.
This function may not have the most useful return type. For a
version that returns the prefix itself as well as the remaining
string, see matches in Data.Trie.
Single-value modification
alterBy :: (Text -> a -> Maybe a -> Maybe a) -> Text -> a -> Trie a -> Trie a Source #
Generic function to alter a trie by one element with a function to resolve conflicts (or non-conflicts).
alterBy_ :: (Text -> a -> Maybe a -> Trie a -> (Maybe a, Trie a)) -> Text -> a -> Trie a -> Trie a Source #
A variant of alterBy which also allows modifying the sub-trie.
adjustBy :: (Text -> a -> a -> a) -> Text -> a -> Trie a -> Trie a Source #
Alter the value associated with a given key. If the key is not
present, then the trie is returned unaltered. See alterBy if
you are interested in inserting new keys or deleting old keys.
Because this function does not need to worry about changing the
trie structure, it is somewhat faster than alterBy.
Combining tries
mergeBy :: (a -> a -> Maybe a) -> Trie a -> Trie a -> Trie a Source #
Combine two tries, using a function to resolve collisions. This can only define the space of functions between union and symmetric difference but, with those two, all set operations can be defined (albeit inefficiently).
Mapping functions
filterMap :: (a -> Maybe b) -> Trie a -> Trie b Source #
Apply a function to all values, potentially removing them.
contextualMap :: (a -> Trie a -> b) -> Trie a -> Trie b Source #
A variant of fmap which provides access to the subtrie rooted
at each value.
contextualMap' :: (a -> Trie a -> b) -> Trie a -> Trie b Source #
A variant of contextualMap which applies the function strictly.
contextualFilterMap :: (a -> Trie a -> Maybe b) -> Trie a -> Trie b Source #
A contextual variant of filterMap.
contextualMapBy :: (Text -> a -> Trie a -> Maybe b) -> Trie a -> Trie b Source #
A contextual variant of mapBy. Again note that this is
expensive since we must reconstruct the keys.