-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | An efficient finite map from bytestrings to values.
--   
--   An efficient finite map from bytestrings to values.
--   
--   The implementation is based on big-endian patricia trees, like
--   <a>Data.IntMap</a>. We first trie on the elements of
--   <a>Data.ByteString</a> and then trie on the big-endian bit
--   representation of those elements. Patricia trees have efficient
--   algorithms for union and other merging operations, but they're also
--   quick for lookups and insertions.
--   
--   If you are only interested in being able to associate strings to
--   values, then you may prefer the <tt>hashmap</tt> package which is
--   faster for those only needing a map-like structure. This package is
--   intended for those who need the extra capabilities that a trie-like
--   structure can offer (e.g., structure sharing to reduce memory costs
--   for highly redundant keys, taking the submap of all keys with a given
--   prefix, contextual mapping, extracting the minimum and maximum keys,
--   etc.)
@package bytestring-trie
@version 0.2.7.6


-- | Internal definition of the <a>Trie</a> data type and generic functions
--   for manipulating them. Almost everything here is re-exported from
--   <a>Data.Trie</a>, which is the preferred API for users. This module is
--   for developers who need deeper (and less stable) access to the
--   abstract type.
module Data.Trie.Internal

-- | A map from <a>ByteString</a>s to <tt>a</tt>. For all the generic
--   functions, note that tries are strict in the <tt>Maybe</tt> but not in
--   <tt>a</tt>.
--   
--   The <a>Monad</a> instance is strange. If a key <tt>k1</tt> is a prefix
--   of other keys, then results from binding the value at <tt>k1</tt> 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.
data Trie a

-- | &lt;math&gt;. Construct the empty trie.
empty :: Trie a

-- | &lt;math&gt;. Is the trie empty?
null :: Trie a -> Bool

-- | &lt;math&gt;. Construct a singleton trie.
singleton :: ByteString -> a -> Trie a

-- | &lt;math&gt;. Get count of elements in trie.
size :: Trie a -> Int

-- | Convert association list into a trie. On key conflict, values earlier
--   in the list shadow later ones.
fromList :: [(ByteString, a)] -> Trie a

-- | Convert trie into association list. The list is ordered according to
--   the keys.
--   
--   <b>Warning</b>: This function suffers <a>Bug #25</a>.
toList :: Trie a -> [(ByteString, a)]

-- | Convert a trie into a list using a function. Resulting values are in
--   key-sorted order.
--   
--   <b>Warning</b>: This function suffers <a>Bug #25</a>.
toListBy :: (ByteString -> a -> b) -> Trie a -> [b]

-- | Return all values in the trie, in key-sorted order.
--   
--   <b>Note</b>: Prior to version 0.2.7, this function suffered <a>Bug
--   #25</a>; but it no longer does.
elems :: Trie a -> [a]

-- | 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 <a>lookupBy</a>.
--   
--   <b>Note</b>: <i>Type changed in 0.2.7</i>
lookupBy_ :: (a -> Trie a -> b) -> (Trie a -> b) -> b -> ByteString -> Trie a -> b

-- | Return the subtrie containing all keys beginning with a prefix.
submap :: ByteString -> Trie a -> Trie a

-- | 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
--   <a>match</a>.
match_ :: Trie a -> ByteString -> Maybe (Int, a)

-- | Given a query, find all prefixes with associated values in the trie,
--   and return the length of each prefix with their value, in order from
--   shortest prefix to longest. 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
--   <a>matches</a>.
matches_ :: Trie a -> ByteString -> [(Int, a)]

-- | Generic function to alter a trie by one element with a function to
--   resolve conflicts (or non-conflicts).
alterBy :: (ByteString -> a -> Maybe a -> Maybe a) -> ByteString -> a -> Trie a -> Trie a

-- | A variant of <a>alterBy</a> which also allows modifying the sub-trie.
--   If the function returns <tt>(Just v, t)</tt> and <tt>lookup
--   <a>empty</a> t == Just w</tt>, then the <tt>w</tt> will be overwritten
--   by <tt>v</tt>.
--   
--   <b>Note</b>: <i>Type changed in 0.2.6</i>
alterBy_ :: (Maybe a -> Trie a -> (Maybe a, Trie a)) -> ByteString -> Trie a -> Trie a

-- | Apply a function to the value at a key. If the key is not present,
--   then the trie is returned unaltered.
adjust :: (a -> a) -> ByteString -> Trie a -> Trie a

-- | Take the union of two tries, using a function to resolve conflicts.
--   The resulting trie is constructed strictly, but the results of the
--   combining function are evaluated lazily.
wip_unionWith :: (a -> a -> a) -> Trie a -> Trie a -> Trie a

-- | Take the union of 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).
mergeBy :: (a -> a -> Maybe a) -> Trie a -> Trie a -> Trie a

-- | Take the intersection of two tries, using a function to resolve
--   collisions.
intersectBy :: (a -> b -> Maybe c) -> Trie a -> Trie b -> Trie c

-- | Return the lexicographically smallest <a>ByteString</a> and the value
--   it's mapped to; or <a>Nothing</a> for the empty trie. When one entry
--   is a prefix of another, the prefix will be returned.
--   
--   <b>Note</b>: Prior to version 0.2.7, this function suffered <a>Bug
--   #25</a>; but it no longer does.
minAssoc :: Trie a -> Maybe (ByteString, a)

-- | Return the lexicographically largest <a>ByteString</a> and the value
--   it's mapped to; or <a>Nothing</a> for the empty trie. When one entry
--   is a prefix of another, the longer one will be returned.
--   
--   <b>Note</b>: Prior to version 0.2.7, this function suffered <a>Bug
--   #25</a>; but it no longer does.
maxAssoc :: Trie a -> Maybe (ByteString, a)

-- | Update the <a>minAssoc</a> and return the old <a>minAssoc</a>.
--   
--   <b>Note</b>: Prior to version 0.2.7, this function suffered <a>Bug
--   #25</a>; but it no longer does.
updateMinViewBy :: (ByteString -> a -> Maybe a) -> Trie a -> Maybe (ByteString, a, Trie a)

-- | Update the <a>maxAssoc</a> and return the old <a>maxAssoc</a>.
--   
--   <b>Note</b>: Prior to version 0.2.7, this function suffered <a>Bug
--   #25</a>; but it no longer does.
updateMaxViewBy :: (ByteString -> a -> Maybe a) -> Trie a -> Maybe (ByteString, a, Trie a)

-- | Retain only those values which satisfy some predicate.
--   
--   <h4><b>Laws</b></h4>
--   
--   <ul>
--   <li><i><i>Definition</i></i> <tt><a>filter</a> f ≡ <a>filterMap</a>
--   (\v -&gt; v <a>&lt;$</a> <a>guard</a> (f v))</tt></li>
--   </ul>
--   
--   <ul>
--   <li><i><i>Composition</i></i> <tt><a>filter</a> f . <a>filter</a> g ≡
--   <a>filter</a> (<a>liftA2</a> (<a>&amp;&amp;</a>) f g)</tt></li>
--   </ul>
--   
--   The definition above is a special case of the fusion law for
--   <a>filterMap</a>. (Also, the name just means definitional-equality;
--   it's not the actual implementation used.)
filter :: (a -> Bool) -> Trie a -> Trie a

-- | Apply a function to all values, potentially removing them.
--   
--   <h4><b>Laws</b></h4>
--   
--   <ul>
--   <li><i><i>Fission</i></i> <tt><a>filterMap</a> f ≡ <a>fmap</a>
--   (<a>fromJust</a> . f) . <a>filter</a> (<a>isJust</a> . f)</tt></li>
--   </ul>
--   
--   <ul>
--   <li><i><i>Fusion</i></i> <tt><a>fmap</a> f . <a>filter</a> g ≡
--   <a>filterMap</a> (\v -&gt; f v <a>&lt;$</a> <a>guard</a> (g
--   v))</tt></li>
--   <li><i><i>Conservation</i></i> <tt><a>filterMap</a> (<a>Just</a> . f)
--   ≡ <a>fmap</a> f</tt></li>
--   <li><i><i>Composition</i></i> <tt><a>filterMap</a> f .
--   <a>filterMap</a> g ≡ <a>filterMap</a> (f <a>&lt;=&lt;</a> g)</tt></li>
--   </ul>
--   
--   The fission/fusion laws are essentially the same, they differ only in
--   which direction is more "natural" for use as a rewrite rule. The
--   conservation law is just a special case of fusion, but it's a
--   particularly helpful one to take note of.
filterMap :: (a -> Maybe b) -> Trie a -> Trie b

-- | Keyed version of <a>filterMap</a>.
--   
--   <b>Warning</b>: This function suffers <a>Bug #25</a>.
mapBy :: (ByteString -> a -> Maybe b) -> Trie a -> Trie b

-- | An effectful version of <a>filter</a>.
--   
--   <h4><b>Laws</b></h4>
--   
--   <ul>
--   <li><i><i>Definition</i></i> <tt><a>filterA</a> f ≡ <a>wither</a> (\v
--   -&gt; (v <a>&lt;$</a>) . <a>guard</a> <a>&lt;$&gt;</a> f v)</tt></li>
--   </ul>
--   
--   <ul>
--   <li><i><i>Naturality</i></i> <tt><a>filterA</a> (t . f) ≡ t .
--   <a>filterA</a> f</tt>, for any <i>applicative-transformation</i>
--   <tt>t</tt></li>
--   <li><i><i>Purity</i></i> <tt><a>filterA</a> (<a>pure</a> . f) ≡
--   <a>pure</a> . <a>filter</a> f</tt></li>
--   <li><i><i>Horizontal Composition</i></i> <tt><a>filterA</a> f `under`
--   <a>filterA</a> g ≡ <a>filterA</a> (underA2 (<a>&amp;&amp;</a>) f
--   g)</tt>, where</li>
--   </ul>
--   
--   <pre>
--   -- Like 'liftA2' for the @(a-&gt;)@ monad, but horizontal.
--   -- The function definition should (hopefully) be straightforward
--   -- to follow; however, do beware the oddly criss-crossed types
--   -- for @g@ and @f@.
--   underA2 :: (Applicative f, Applicative g)
--           =&gt; (b -&gt; c -&gt; d)
--           -&gt; (a -&gt; g b)
--           -&gt; (a -&gt; f c)
--           -&gt; a -&gt; Compose f g d
--   underA2 h g f = liftA2 (liftA2 h) (g `under` pure) (pure `under` f)
--   </pre>
--   
--   For the definition of <tt>under</tt> and more details about horizontal
--   composition, see the laws section of <a>wither</a>.
filterA :: Applicative f => (a -> f Bool) -> Trie a -> f (Trie a)

-- | An effectful version of <a>filterMap</a>.
--   
--   <h4><b>Laws</b></h4>
--   
--   <ul>
--   <li><i><i>Naturality</i></i> <tt><a>wither</a> (t . f) ≡ t .
--   <a>wither</a> f</tt>, for any <i>applicative-transformation</i>
--   <tt>t</tt></li>
--   </ul>
--   
--   <ul>
--   <li><i><i>Purity</i></i> <tt><a>wither</a> (<a>pure</a> . f) ≡
--   <a>pure</a> . <a>filterMap</a> f</tt></li>
--   <li><i><i>Conservation</i></i> <tt><a>wither</a> (<a>fmap</a>
--   <a>Just</a> . f) ≡ <a>traverse</a> f</tt></li>
--   <li><i><i>Horizontal Composition</i></i> <tt><a>wither</a> f `under`
--   <a>wither</a> g ≡ <a>wither</a> (wither_Maybe f `under` g)</tt>,
--   where:</li>
--   </ul>
--   
--   <pre>
--   under :: Functor f
--         =&gt; (b -&gt; g c)
--         -&gt; (a -&gt; f b)
--         -&gt; a -&gt; Compose f g c
--   under g f = Compose . fmap g . f
--   
--   -- | Variant of wither for Maybe instead of Trie.
--   wither_Maybe :: Applicative f
--                =&gt; (a -&gt; f (Maybe b))
--                -&gt; Maybe a -&gt; f (Maybe b)
--   wither_Maybe f = fmap join . traverse f
--   </pre>
--   
--   Note that the horizontal composition law is using two different
--   applicative functors. Conversely, a vertical composition law would
--   have the form: <tt><a>wither</a> f <a>&lt;=&lt;</a> <a>wither</a> g ≡
--   ...</tt>; however, we cannot have such a law except when the
--   applicative functor is in fact a commutative monad (i.e., the order of
--   effects doesn't matter). For the curious, the terminology of
--   <a>"horizontal" composition</a> vs <a>"vertical" composition</a> comes
--   from category theory.
--   
--   Although the horizontal composition law may look baroque, it is
--   helpful to compare it to the composition law for <a>traverse</a>
--   itself:
--   
--   <pre>
--   <a>traverse</a> f `under` <a>traverse</a> g ≡ <a>traverse</a> (f `under` g)
--   </pre>
wither :: Applicative f => (a -> f (Maybe b)) -> Trie a -> f (Trie b)

-- | A variant of <a>fmap</a> which provides access to the subtrie rooted
--   at each value.
contextualMap :: (a -> Trie a -> b) -> Trie a -> Trie b

-- | A variant of <a>contextualMap</a> which evaluates the function
--   strictly.
contextualMap' :: (a -> Trie a -> b) -> Trie a -> Trie b

-- | Contextual variant of <a>filterMap</a>.
contextualFilterMap :: (a -> Trie a -> Maybe b) -> Trie a -> Trie b

-- | Contextual variant of <a>mapBy</a>, aka keyed variant of
--   <a>contextualFilterMap</a>.
--   
--   <b>Warning</b>: This function suffers <a>Bug #25</a>.
contextualMapBy :: (ByteString -> a -> Trie a -> Maybe b) -> Trie a -> Trie b

-- | Keyed variant of <a>foldr</a>.
--   
--   <b>Warning</b>: This function suffers <a>Bug #25</a>.
foldrWithKey :: (ByteString -> a -> b -> b) -> b -> Trie a -> b

-- | Keyed variant of <a>foldr'</a>.
--   
--   <b>Warning</b>: This function suffers <a>Bug #25</a>.
foldrWithKey' :: (ByteString -> a -> b -> b) -> b -> Trie a -> b

-- | Keyed variant of <a>foldl</a>.
--   
--   <b>Warning</b>: This function suffers <a>Bug #25</a>.
foldlWithKey :: (b -> ByteString -> a -> b) -> b -> Trie a -> b

-- | Keyed variant of <a>foldl'</a>.
--   
--   <b>Warning</b>: This function suffers <a>Bug #25</a>.
foldlWithKey' :: (b -> ByteString -> a -> b) -> b -> Trie a -> b

-- | Catamorphism for tries. Unlike most other functions (<a>mapBy</a>,
--   <a>contextualMapBy</a>, <a>foldrWithKey</a>, etc), this function does
--   <i>not</i> reconstruct the full <a>ByteString</a> for each value;
--   instead it only returns the suffix since the previous value or branch
--   point.
--   
--   This function is a direct/literal catamorphism of the implementation
--   datatype, erasing only some bitmasking metadata for the branches. For
--   a more semantic catamorphism, see <a>cata</a>.
cata_ :: (ByteString -> Maybe a -> b -> b) -> (b -> b -> b) -> b -> Trie a -> b

-- | Catamorphism for tries. Unlike most other functions (<a>mapBy</a>,
--   <a>contextualMapBy</a>, <a>foldrWithKey</a>, etc), this function does
--   <i>not</i> reconstruct the full <a>ByteString</a> for each value;
--   instead it only returns the suffix since the previous value or branch
--   point.
--   
--   This function is a semantic catamorphism; that is, it tries to express
--   the invariants of the implementation, rather than exposing the literal
--   structure of the implementation. For a more literal catamorphism, see
--   <a>cata_</a>.
cata :: (ByteString -> a -> b -> b) -> (ByteString -> [b] -> b) -> b -> Trie a -> b

-- | Keyed version of <a>traverse</a>.
--   
--   <b>Warning</b>: This function suffers <a>Bug #25</a>.
traverseWithKey :: Applicative f => (ByteString -> a -> f b) -> Trie a -> f (Trie b)

-- | Visualization fuction for debugging.
showTrie :: Show a => Trie a -> String

-- | Returns the longest shared prefix and the two remaining suffixes for a
--   pair of strings. This function performs no allocation/copying, it
--   simply returns slices/views of the arguments.
--   
--   <ul>
--   <li><pre>s ≡ (\(pre,s',z') -&gt; pre <a>&lt;&gt;</a> s')
--   (<a>breakMaximalPrefix</a> s z)</pre></li>
--   <li><pre>z ≡ (\(pre,s',z') -&gt; pre <a>&lt;&gt;</a> z')
--   (<a>breakMaximalPrefix</a> s z)</pre></li>
--   </ul>
breakMaximalPrefix :: ByteString -> ByteString -> (ByteString, ByteString, ByteString)
instance GHC.Internal.Base.Applicative Data.Trie.Internal.Trie
instance Data.Binary.Class.Binary a => Data.Binary.Class.Binary (Data.Trie.Internal.Trie a)
instance Data.Functor.Classes.Eq1 Data.Trie.Internal.Trie
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Trie.Internal.Trie a)
instance GHC.Internal.Data.Foldable.Foldable Data.Trie.Internal.Trie
instance GHC.Internal.Base.Functor Data.Trie.Internal.Trie
instance GHC.Internal.IsList.IsList (Data.Trie.Internal.Trie a)
instance GHC.Internal.Base.Monad Data.Trie.Internal.Trie
instance GHC.Internal.Base.Monoid a => GHC.Internal.Base.Monoid (Data.Trie.Internal.Trie a)
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.Trie.Internal.Trie a)
instance Data.Functor.Classes.Ord1 Data.Trie.Internal.Trie
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Trie.Internal.Trie a)
instance Data.Functor.Classes.Read1 Data.Trie.Internal.Trie
instance GHC.Internal.Read.Read a => GHC.Internal.Read.Read (Data.Trie.Internal.Trie a)
instance GHC.Internal.Base.Semigroup a => GHC.Internal.Base.Semigroup (Data.Trie.Internal.Trie a)
instance Data.Functor.Classes.Show1 Data.Trie.Internal.Trie
instance GHC.Internal.Show.Show a => GHC.Internal.Show.Show (Data.Trie.Internal.Trie a)
instance GHC.Internal.Data.Traversable.Traversable Data.Trie.Internal.Trie


-- | An efficient implementation of finite maps from strings to values. The
--   implementation is based on <i>big-endian patricia trees</i>, like
--   <a>Data.IntMap</a>. We first trie on the elements of
--   <a>Data.ByteString</a> and then trie on the big-endian bit
--   representation of those elements. For further details on the latter,
--   see
--   
--   <ul>
--   <li>Chris Okasaki and Andy Gill, "<i>Fast Mergeable Integer Maps</i>",
--   Workshop on ML, September 1998, pages 77-86,
--   <a>http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.5452</a></li>
--   <li>D.R. Morrison, "<i>PATRICIA -- Practical Algorithm To Retrieve</i>
--   <i>Information Coded In Alphanumeric</i>", Journal of the ACM, 15(4),
--   October 1968, pages 514-534.</li>
--   </ul>
--   
--   This module aims to provide an austere interface, while being detailed
--   enough for most users. For an extended interface with many additional
--   functions, see <a>Data.Trie.Convenience</a>. For functions that give
--   more detailed (potentially abstraction-breaking) access to the data
--   structure, or for experimental functions which aren't quite ready for
--   the public API, see <a>Data.Trie.Internal</a>.
module Data.Trie

-- | A map from <a>ByteString</a>s to <tt>a</tt>. For all the generic
--   functions, note that tries are strict in the <tt>Maybe</tt> but not in
--   <tt>a</tt>.
--   
--   The <a>Monad</a> instance is strange. If a key <tt>k1</tt> is a prefix
--   of other keys, then results from binding the value at <tt>k1</tt> 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.
data Trie a

-- | &lt;math&gt;. Construct the empty trie.
empty :: Trie a

-- | &lt;math&gt;. Is the trie empty?
null :: Trie a -> Bool

-- | &lt;math&gt;. Construct a singleton trie.
singleton :: ByteString -> a -> Trie a

-- | &lt;math&gt;. Get count of elements in trie.
size :: Trie a -> Int

-- | Convert association list into a trie. On key conflict, values earlier
--   in the list shadow later ones.
fromList :: [(ByteString, a)] -> Trie a

-- | Convert a trie into a list using a function. Resulting values are in
--   key-sorted order.
--   
--   <b>Warning</b>: This function suffers <a>Bug #25</a>.
toListBy :: (ByteString -> a -> b) -> Trie a -> [b]

-- | Convert trie into association list. The list is ordered according to
--   the keys.
--   
--   <b>Warning</b>: This function suffers <a>Bug #25</a>.
toList :: Trie a -> [(ByteString, a)]

-- | Return all keys in the trie, in sorted order.
--   
--   <b>Warning</b>: This function suffers <a>Bug #25</a>.
keys :: Trie a -> [ByteString]

-- | Return all values in the trie, in key-sorted order.
--   
--   <b>Note</b>: Prior to version 0.2.7, this function suffered <a>Bug
--   #25</a>; but it no longer does.
elems :: Trie a -> [a]

-- | Generic function to find a value (if it exists) and the subtrie rooted
--   at the prefix.
lookupBy :: (Maybe a -> Trie a -> b) -> ByteString -> Trie a -> b

-- | Return the value associated with a query string if it exists.
lookup :: ByteString -> Trie a -> Maybe a

-- | Does a string have a value in the trie?
member :: ByteString -> Trie a -> Bool

-- | Return the subtrie containing all keys beginning with a prefix.
submap :: ByteString -> Trie a -> Trie a

-- | Given a query, find the longest prefix with an associated value in the
--   trie, and return that prefix, its value, and the remainder of the
--   query.
match :: Trie a -> ByteString -> Maybe (ByteString, a, ByteString)

-- | Given a query, find the shortest prefix with an associated value in
--   the trie, and return that prefix, its value, and the remainder of the
--   query.
minMatch :: Trie a -> ByteString -> Maybe (ByteString, a, ByteString)

-- | Given a query, find all prefixes with associated values in the trie,
--   and return their (prefix, value, remainder) triples in order from
--   shortest prefix to longest. This function is a good producer for list
--   fusion.
matches :: Trie a -> ByteString -> [(ByteString, a, ByteString)]

-- | Insert a new key. If the key is already present, overrides the old
--   value
insert :: ByteString -> a -> Trie a -> Trie a

-- | Apply a function to the value at a key. If the key is not present,
--   then the trie is returned unaltered.
adjust :: (a -> a) -> ByteString -> Trie a -> Trie a

-- | Alter the value associated with a given key. If the key is not
--   present, then the trie is returned unaltered. See <a>alterBy</a> 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 <a>alterBy</a>.
--   
--   <b>Note</b>: Prior to version 0.2.6 this function was exported from
--   <a>Data.Trie.Internal</a> instead.
adjustBy :: (ByteString -> a -> a -> a) -> ByteString -> a -> Trie a -> Trie a

-- | Generic function to alter a trie by one element with a function to
--   resolve conflicts (or non-conflicts).
alterBy :: (ByteString -> a -> Maybe a -> Maybe a) -> ByteString -> a -> Trie a -> Trie a

-- | Remove the value stored at a key.
delete :: ByteString -> Trie a -> Trie a

-- | Remove all keys beginning with a prefix.
deleteSubmap :: ByteString -> Trie a -> Trie a

-- | Take the union of 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).
mergeBy :: (a -> a -> Maybe a) -> Trie a -> Trie a -> Trie a

-- | Take the union of two tries, resolving conflicts by choosing the value
--   from the left trie.
unionL :: Trie a -> Trie a -> Trie a

-- | Take the union of two tries, resolving conflicts by choosing the value
--   from the right trie.
unionR :: Trie a -> Trie a -> Trie a

-- | Take the intersection of two tries, using a function to resolve
--   collisions.
intersectBy :: (a -> b -> Maybe c) -> Trie a -> Trie b -> Trie c

-- | Take the intersection of two tries, with values from the left trie.
intersectL :: Trie a -> Trie b -> Trie a

-- | Take the intersection of two tries, with values from the right trie.
intersectR :: Trie a -> Trie b -> Trie b

-- | Keyed version of <a>filterMap</a>.
--   
--   <b>Warning</b>: This function suffers <a>Bug #25</a>.
mapBy :: (ByteString -> a -> Maybe b) -> Trie a -> Trie b

-- | Apply a function to all values, potentially removing them.
--   
--   <h4><b>Laws</b></h4>
--   
--   <ul>
--   <li><i><i>Fission</i></i> <tt><a>filterMap</a> f ≡ <a>fmap</a>
--   (<a>fromJust</a> . f) . <a>filter</a> (<a>isJust</a> . f)</tt></li>
--   </ul>
--   
--   <ul>
--   <li><i><i>Fusion</i></i> <tt><a>fmap</a> f . <a>filter</a> g ≡
--   <a>filterMap</a> (\v -&gt; f v <a>&lt;$</a> <a>guard</a> (g
--   v))</tt></li>
--   <li><i><i>Conservation</i></i> <tt><a>filterMap</a> (<a>Just</a> . f)
--   ≡ <a>fmap</a> f</tt></li>
--   <li><i><i>Composition</i></i> <tt><a>filterMap</a> f .
--   <a>filterMap</a> g ≡ <a>filterMap</a> (f <a>&lt;=&lt;</a> g)</tt></li>
--   </ul>
--   
--   The fission/fusion laws are essentially the same, they differ only in
--   which direction is more "natural" for use as a rewrite rule. The
--   conservation law is just a special case of fusion, but it's a
--   particularly helpful one to take note of.
filterMap :: (a -> Maybe b) -> Trie a -> Trie b


-- | Additional convenience functions. In order to keep <a>Data.Trie</a>
--   concise, non-essential and uncommonly used functions have been moved
--   here. Most of these functions simplify the generic functions from
--   <a>Data.Trie</a>, following after the interface for <a>Data.Map</a>
--   and <a>Data.IntMap</a>.
module Data.Trie.Convenience

-- | A left-fold version of <a>fromList</a>. If you run into issues with
--   stack overflows when using <a>fromList</a> or <a>fromListR</a>, then
--   you should use this function instead.
fromListL :: [(ByteString, a)] -> Trie a

-- | An explicitly right-fold variant of <a>fromList</a>. It is a good
--   consumer for list fusion. Worst-case behavior is somewhat worse than
--   worst-case for <a>fromListL</a>. The <a>fromList</a> function is
--   currently just an alias for <a>fromListR</a>.
fromListR :: [(ByteString, a)] -> Trie a

-- | This variant sorts the list before folding over it. This adds
--   &lt;math&gt; overhead and requires the whole list be in memory at
--   once, but it ensures that the list is in best-case order. The benefits
--   generally outweigh the costs.
fromListS :: [(ByteString, a)] -> Trie a

-- | A variant of <a>fromListR</a> that takes a function for combining
--   values on conflict. The first argument to the combining function is
--   the "new" value from the initial portion of the list; the second
--   argument is the value that has been accumulated into the trie from the
--   tail of the list (just like the first argument to <a>foldr</a>). Thus,
--   <tt>fromList = fromListWith const</tt>.
fromListWith :: (a -> a -> a) -> [(ByteString, a)] -> Trie a

-- | A variant of <a>fromListWith</a> which applies the combining function
--   strictly. This function is a good consumer for list fusion. If you
--   need list fusion and are running into stack overflow problems with
--   <a>fromListWith</a>, then this function may solve the problem.
fromListWith' :: (a -> a -> a) -> [(ByteString, a)] -> Trie a

-- | A left-fold variant of <a>fromListWith</a>. Note that the arguments to
--   the combining function are swapped: the first is the value in the trie
--   which has been accumulated from the initial part of the list; the
--   second argument is the "new" value from the remaining tail of the list
--   (just like the first argument to <a>foldl</a>). Thus, <tt>fromListL =
--   fromListWithL const</tt>.
fromListWithL :: (a -> a -> a) -> [(ByteString, a)] -> Trie a

-- | A variant of <a>fromListWithL</a> which applies the combining function
--   strictly.
fromListWithL' :: (a -> a -> a) -> [(ByteString, a)] -> Trie a

-- | Lookup a key, returning a default value if it's not found.
lookupWithDefault :: a -> ByteString -> Trie a -> a

-- | Insert a new key, retaining old value on conflict.
insertIfAbsent :: ByteString -> a -> Trie a -> Trie a

-- | Insert a new key, with a function to resolve conflicts.
insertWith :: (a -> a -> a) -> ByteString -> a -> Trie a -> Trie a

-- | A variant of <a>insertWith</a> which applies the combining function
--   strictly.
insertWith' :: (a -> a -> a) -> ByteString -> a -> Trie a -> Trie a

-- | A variant of <a>insertWith</a> which also provides the key to the
--   combining function.
insertWithKey :: (ByteString -> a -> a -> a) -> ByteString -> a -> Trie a -> Trie a

-- | A variant of <a>insertWithKey</a> which applies the combining function
--   strictly.
insertWithKey' :: (ByteString -> a -> a -> a) -> ByteString -> a -> Trie a -> Trie a

-- | Apply a function to change the value at a key.
adjustWithKey :: (ByteString -> a -> a) -> ByteString -> Trie a -> Trie a

-- | Apply a function to the value at a key, possibly removing it.
update :: (a -> Maybe a) -> ByteString -> Trie a -> Trie a

-- | A variant of <a>update</a> which also provides the key to the
--   function.
updateWithKey :: (ByteString -> a -> Maybe a) -> ByteString -> Trie a -> Trie a

-- | Combine two tries, a la symmetric difference. If they define the same
--   key, it is removed; otherwise it is retained with the value it has in
--   whichever trie.
disunion :: Trie a -> Trie a -> Trie a

-- | Take the union of two tries, using a function to resolve conflicts.
--   The resulting trie is constructed strictly, but the results of the
--   combining function are evaluated lazily.
unionWith :: (a -> a -> a) -> Trie a -> Trie a -> Trie a

-- | A variant of <a>unionWith</a> which evaluates the combining function
--   strictly.
unionWith' :: (a -> a -> a) -> Trie a -> Trie a -> Trie a

-- | Take the intersection of two tries, with a function to resolve the
--   values. The resulting trie is constructed strictly, bit the results of
--   the combining function are evaluated lazily.
intersectWith :: (a -> b -> c) -> Trie a -> Trie b -> Trie c

-- | A variant of <a>intersectWith</a> which evaluates the combining
--   function strictly.
intersectWith' :: (a -> b -> c) -> Trie a -> Trie b -> Trie c
