<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>Data.Trie.Internal</title><link href="ocean.css" rel="stylesheet" type="text/css" title="Ocean" /><script src="haddock-util.js" type="text/javascript"></script><script type="text/javascript">//<![CDATA[
window.onload = function () {pageLoad();setSynopsis("mini_Data-Trie-Internal.html");};
//]]>
</script></head><body><div id="package-header"><ul class="links" id="page-menu"><li><a href="src/Data-Trie-Internal.html">Source</a></li><li><a href="index.html">Contents</a></li><li><a href="doc-index.html">Index</a></li></ul><p class="caption">bytestring-trie-0.2.3: An efficient finite map from (byte)strings to values.</p></div><div id="content"><div id="module-header"><table class="info"><tr><th>Portability</th><td>portable (with CPP)</td></tr><tr><th>Stability</th><td>provisional</td></tr><tr><th>Maintainer</th><td>wren@community.haskell.org</td></tr></table><p class="caption">Data.Trie.Internal</p></div><div id="table-of-contents"><p class="caption">Contents</p><ul><li><a href="#g:1">Data types
</a></li><li><a href="#g:2">Functions for <code><a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a></code>s
</a></li><li><a href="#g:3">Basic functions
</a></li><li><a href="#g:4">Conversion and folding functions
</a></li><li><a href="#g:5">Query functions
</a></li><li><a href="#g:6">Single-value modification
</a></li><li><a href="#g:7">Combining tries
</a></li><li><a href="#g:8">Mapping functions
</a></li><li><a href="#g:9">Priority-queue functions
</a></li></ul></div><div id="description"><p class="caption">Description</p><div class="doc"><p>Internal definition of the <code><a href="Data-Trie-Internal.html#t:Trie">Trie</a></code> data type and generic functions
for manipulating them. Almost everything here is re-exported
from <a href="Data-Trie.html">Data.Trie</a>, which is the preferred API for users. This
module is for developers who need deeper (and potentially fragile)
access to the abstract type.
</p></div></div><div id="synopsis"><p id="control.syn" class="caption expander" onclick="toggleSection('syn')">Synopsis</p><ul id="section.syn" class="hide" onclick="toggleSection('syn')"><li class="src short"><span class="keyword">data</span> <a href="#t:Trie">Trie</a> a</li><li class="src short"><a href="#v:showTrie">showTrie</a> :: <a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Text-Show.html#t:Show">Show</a> a => <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Char.html#t:String">String</a></li><li class="src short"><a href="#v:breakMaximalPrefix">breakMaximalPrefix</a> :: <a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a> -> <a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a> -> (<a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a>, <a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a>, <a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a>)</li><li class="src short"><a href="#v:empty">empty</a> :: <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a</li><li class="src short"><a href="#v:null">null</a> :: <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Bool.html#t:Bool">Bool</a></li><li class="src short"><a href="#v:singleton">singleton</a> :: <a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a> -> a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a</li><li class="src short"><a href="#v:size">size</a> :: <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Int.html#t:Int">Int</a></li><li class="src short"><a href="#v:foldrWithKey">foldrWithKey</a> :: (<a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a> -> a -> b -> b) -> b -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> b</li><li class="src short"><a href="#v:toListBy">toListBy</a> :: (<a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a> -> a -> b) -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> [b]</li><li class="src short"><a href="#v:lookupBy_">lookupBy_</a> :: (<a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> b) -> b -> (<a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> b) -> <a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a> -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> b</li><li class="src short"><a href="#v:submap">submap</a> :: <a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a> -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a</li><li class="src short"><a href="#v:alterBy">alterBy</a> :: (<a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a> -> a -> <a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a -> <a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a) -> <a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a> -> a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a</li><li class="src short"><a href="#v:alterBy_">alterBy_</a> :: (<a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a> -> a -> <a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> (<a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a, <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a)) -> <a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a> -> a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a</li><li class="src short"><a href="#v:adjustBy">adjustBy</a> :: (<a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a> -> a -> a -> a) -> <a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a> -> a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a</li><li class="src short"><a href="#v:mergeBy">mergeBy</a> :: (a -> a -> <a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a) -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a</li><li class="src short"><a href="#v:mapBy">mapBy</a> :: (<a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a> -> a -> <a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Maybe.html#t:Maybe">Maybe</a> b) -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> b</li><li class="src short"><a href="#v:filterMap">filterMap</a> :: (a -> <a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Maybe.html#t:Maybe">Maybe</a> b) -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> b</li><li class="src short"><a href="#v:contextualMap">contextualMap</a> :: (a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> b) -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> b</li><li class="src short"><a href="#v:contextualMap-39-">contextualMap'</a> :: (a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> b) -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> b</li><li class="src short"><a href="#v:contextualFilterMap">contextualFilterMap</a> :: (a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Maybe.html#t:Maybe">Maybe</a> b) -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> b</li><li class="src short"><a href="#v:contextualMapBy">contextualMapBy</a> :: (<a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a> -> a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Maybe.html#t:Maybe">Maybe</a> b) -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> b</li><li class="src short"><a href="#v:minAssoc">minAssoc</a> :: <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Maybe.html#t:Maybe">Maybe</a> (<a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a>, a)</li><li class="src short"><a href="#v:maxAssoc">maxAssoc</a> :: <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Maybe.html#t:Maybe">Maybe</a> (<a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a>, a)</li><li class="src short"><a href="#v:updateMinViewBy">updateMinViewBy</a> :: (<a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a> -> a -> <a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a) -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Maybe.html#t:Maybe">Maybe</a> (<a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a>, a, <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a)</li><li class="src short"><a href="#v:updateMaxViewBy">updateMaxViewBy</a> :: (<a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a> -> a -> <a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a) -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Maybe.html#t:Maybe">Maybe</a> (<a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a>, a, <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a)</li></ul></div><div id="interface"><h1 id="g:1">Data types
</h1><div class="top"><p class="src"><span class="keyword">data</span> <a name="t:Trie" class="def">Trie</a> a <a href="src/Data-Trie-Internal.html#Trie" class="link">Source</a></p><div class="doc"><p>A map from <code><a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a></code>s to <code>a</code>. For all the generic functions,
note that tries are strict in the <code>Maybe</code> but not in <code>a</code>.
</p><p>The <code><a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Control-Monad.html#t:Monad">Monad</a></code> instance is strange. If a key <code>k1</code> is a prefix of
other keys, then results from binding the value at <code>k1</code> 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.
</p></div><div class="subs instances"><p id="control.i:Trie" class="caption collapser" onclick="toggleSection('i:Trie')">Instances</p><div id="section.i:Trie" class="show"><table><tr><td class="src"><a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Control-Monad.html#t:Monad">Monad</a> <a href="Data-Trie-Internal.html#t:Trie">Trie</a></td><td class="doc empty"> </td></tr><tr><td class="src"><a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Control-Monad.html#t:Functor">Functor</a> <a href="Data-Trie-Internal.html#t:Trie">Trie</a></td><td class="doc empty"> </td></tr><tr><td class="src"><a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Control-Applicative.html#t:Applicative">Applicative</a> <a href="Data-Trie-Internal.html#t:Trie">Trie</a></td><td class="doc empty"> </td></tr><tr><td class="src"><a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Foldable.html#t:Foldable">Foldable</a> <a href="Data-Trie-Internal.html#t:Trie">Trie</a></td><td class="doc empty"> </td></tr><tr><td class="src"><a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Traversable.html#t:Traversable">Traversable</a> <a href="Data-Trie-Internal.html#t:Trie">Trie</a></td><td class="doc empty"> </td></tr><tr><td class="src"><a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Eq.html#t:Eq">Eq</a> a => <a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Eq.html#t:Eq">Eq</a> (<a href="Data-Trie-Internal.html#t:Trie">Trie</a> a)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Text-Show.html#t:Show">Show</a> a => <a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Text-Show.html#t:Show">Show</a> (<a href="Data-Trie-Internal.html#t:Trie">Trie</a> a)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Monoid.html#t:Monoid">Monoid</a> a => <a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Monoid.html#t:Monoid">Monoid</a> (<a href="Data-Trie-Internal.html#t:Trie">Trie</a> a)</td><td class="doc empty"> </td></tr><tr><td class="src"><a href="/usr/share/doc/ghc/html/libraries/binary-0.5.0.2/Data-Binary.html#t:Binary">Binary</a> a => <a href="/usr/share/doc/ghc/html/libraries/binary-0.5.0.2/Data-Binary.html#t:Binary">Binary</a> (<a href="Data-Trie-Internal.html#t:Trie">Trie</a> a)</td><td class="doc empty"> </td></tr></table></div></div></div><div class="top"><p class="src"><a name="v:showTrie" class="def">showTrie</a> :: <a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Text-Show.html#t:Show">Show</a> a => <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Char.html#t:String">String</a><a href="src/Data-Trie-Internal.html#showTrie" class="link">Source</a></p><div class="doc"><p>Visualization fuction for debugging.
</p></div></div><h1 id="g:2">Functions for <code><a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a></code>s
</h1><div class="top"><p class="src"><a name="v:breakMaximalPrefix" class="def">breakMaximalPrefix</a> :: <a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a> -> <a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a> -> (<a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a>, <a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a>, <a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a>)<a href="src/Data-Trie-ByteStringInternal.html#breakMaximalPrefix" class="link">Source</a></p><div class="doc"><p>Returns the longest shared prefix and the two remaining suffixes
for a pair of strings.
</p><pre> s == (\(pre,s',z') -> pre `append` s') (breakMaximalPrefix s z)
z == (\(pre,s',z') -> pre `append` z') (breakMaximalPrefix s z)
</pre></div></div><h1 id="g:3">Basic functions
</h1><div class="top"><p class="src"><a name="v:empty" class="def">empty</a> :: <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a<a href="src/Data-Trie-Internal.html#empty" class="link">Source</a></p><div class="doc"><p><em>O(1)</em>, Construct the empty trie.
</p></div></div><div class="top"><p class="src"><a name="v:null" class="def">null</a> :: <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Bool.html#t:Bool">Bool</a><a href="src/Data-Trie-Internal.html#null" class="link">Source</a></p><div class="doc"><p><em>O(1)</em>, Is the trie empty?
</p></div></div><div class="top"><p class="src"><a name="v:singleton" class="def">singleton</a> :: <a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a> -> a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a<a href="src/Data-Trie-Internal.html#singleton" class="link">Source</a></p><div class="doc"><p><em>O(1)</em>, Construct a singleton trie.
</p></div></div><div class="top"><p class="src"><a name="v:size" class="def">size</a> :: <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Int.html#t:Int">Int</a><a href="src/Data-Trie-Internal.html#size" class="link">Source</a></p><div class="doc"><p><em>O(n)</em>, Get count of elements in trie.
</p></div></div><h1 id="g:4">Conversion and folding functions
</h1><div class="top"><p class="src"><a name="v:foldrWithKey" class="def">foldrWithKey</a> :: (<a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a> -> a -> b -> b) -> b -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> b<a href="src/Data-Trie-Internal.html#foldrWithKey" class="link">Source</a></p><div class="doc"><p>Convert a trie into a list (in key-sorted order) using a
function, folding the list as we go.
</p></div></div><div class="top"><p class="src"><a name="v:toListBy" class="def">toListBy</a> :: (<a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a> -> a -> b) -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> [b]<a href="src/Data-Trie-Internal.html#toListBy" class="link">Source</a></p><div class="doc"><p>Convert a trie into a list using a function. Resulting values
are in key-sorted order.
</p></div></div><h1 id="g:5">Query functions
</h1><div class="top"><p class="src"><a name="v:lookupBy_" class="def">lookupBy_</a> :: (<a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> b) -> b -> (<a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> b) -> <a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a> -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> b<a href="src/Data-Trie-Internal.html#lookupBy_" class="link">Source</a></p><div class="doc"><p>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.
</p><p>This function is intended for internal use. For the public-facing
version, see <code>lookupBy</code> in <a href="Data-Trie.html">Data.Trie</a>.
</p></div></div><div class="top"><p class="src"><a name="v:submap" class="def">submap</a> :: <a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a> -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a<a href="src/Data-Trie-Internal.html#submap" class="link">Source</a></p><div class="doc"><p>Return the subtrie containing all keys beginning with a prefix.
</p></div></div><h1 id="g:6">Single-value modification
</h1><div class="top"><p class="src"><a name="v:alterBy" class="def">alterBy</a> :: (<a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a> -> a -> <a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a -> <a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a) -> <a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a> -> a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a<a href="src/Data-Trie-Internal.html#alterBy" class="link">Source</a></p><div class="doc"><p>Generic function to alter a trie by one element with a function
to resolve conflicts (or non-conflicts).
</p></div></div><div class="top"><p class="src"><a name="v:alterBy_" class="def">alterBy_</a> :: (<a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a> -> a -> <a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> (<a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a, <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a)) -> <a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a> -> a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a<a href="src/Data-Trie-Internal.html#alterBy_" class="link">Source</a></p><div class="doc"><p>A variant of <code><a href="Data-Trie-Internal.html#v:alterBy">alterBy</a></code> which also allows modifying the sub-trie.
</p></div></div><div class="top"><p class="src"><a name="v:adjustBy" class="def">adjustBy</a> :: (<a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a> -> a -> a -> a) -> <a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a> -> a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a<a href="src/Data-Trie-Internal.html#adjustBy" class="link">Source</a></p><div class="doc"><p>Alter the value associated with a given key. If the key is not
present, then the trie is returned unaltered. See <code><a href="Data-Trie-Internal.html#v:alterBy">alterBy</a></code> 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 <code><a href="Data-Trie-Internal.html#v:alterBy">alterBy</a></code>.
</p></div></div><h1 id="g:7">Combining tries
</h1><div class="top"><p class="src"><a name="v:mergeBy" class="def">mergeBy</a> :: (a -> a -> <a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a) -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a<a href="src/Data-Trie-Internal.html#mergeBy" class="link">Source</a></p><div class="doc"><p>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).
</p></div></div><h1 id="g:8">Mapping functions
</h1><div class="top"><p class="src"><a name="v:mapBy" class="def">mapBy</a> :: (<a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a> -> a -> <a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Maybe.html#t:Maybe">Maybe</a> b) -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> b<a href="src/Data-Trie-Internal.html#mapBy" class="link">Source</a></p><div class="doc"><p>Generic version of <code><a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Control-Monad.html#v:fmap">fmap</a></code>. This function is notably more
expensive than <code><a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Control-Monad.html#v:fmap">fmap</a></code> or <code><a href="Data-Trie-Internal.html#v:filterMap">filterMap</a></code> because we have to reconstruct
the keys.
</p></div></div><div class="top"><p class="src"><a name="v:filterMap" class="def">filterMap</a> :: (a -> <a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Maybe.html#t:Maybe">Maybe</a> b) -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> b<a href="src/Data-Trie-Internal.html#filterMap" class="link">Source</a></p><div class="doc"><p>Apply a function to all values, potentially removing them.
</p></div></div><div class="top"><p class="src"><a name="v:contextualMap" class="def">contextualMap</a> :: (a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> b) -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> b<a href="src/Data-Trie-Internal.html#contextualMap" class="link">Source</a></p><div class="doc"><p>A variant of <code><a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Control-Monad.html#v:fmap">fmap</a></code> which provides access to the subtrie rooted
at each value.
</p></div></div><div class="top"><p class="src"><a name="v:contextualMap-39-" class="def">contextualMap'</a> :: (a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> b) -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> b<a href="src/Data-Trie-Internal.html#contextualMap%27" class="link">Source</a></p><div class="doc"><p>A variant of <code><a href="Data-Trie-Internal.html#v:contextualMap">contextualMap</a></code> which applies the function strictly.
</p></div></div><div class="top"><p class="src"><a name="v:contextualFilterMap" class="def">contextualFilterMap</a> :: (a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Maybe.html#t:Maybe">Maybe</a> b) -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> b<a href="src/Data-Trie-Internal.html#contextualFilterMap" class="link">Source</a></p><div class="doc"><p>A contextual variant of <code><a href="Data-Trie-Internal.html#v:filterMap">filterMap</a></code>.
</p></div></div><div class="top"><p class="src"><a name="v:contextualMapBy" class="def">contextualMapBy</a> :: (<a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a> -> a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Maybe.html#t:Maybe">Maybe</a> b) -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> b<a href="src/Data-Trie-Internal.html#contextualMapBy" class="link">Source</a></p><div class="doc"><p>A contextual variant of <code><a href="Data-Trie-Internal.html#v:mapBy">mapBy</a></code>. Again note that this is
expensive since we must reconstruct the keys.
</p></div></div><h1 id="g:9">Priority-queue functions
</h1><div class="top"><p class="src"><a name="v:minAssoc" class="def">minAssoc</a> :: <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Maybe.html#t:Maybe">Maybe</a> (<a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a>, a)<a href="src/Data-Trie-Internal.html#minAssoc" class="link">Source</a></p></div><div class="top"><p class="src"><a name="v:maxAssoc" class="def">maxAssoc</a> :: <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Maybe.html#t:Maybe">Maybe</a> (<a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a>, a)<a href="src/Data-Trie-Internal.html#maxAssoc" class="link">Source</a></p></div><div class="top"><p class="src"><a name="v:updateMinViewBy" class="def">updateMinViewBy</a> :: (<a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a> -> a -> <a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a) -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Maybe.html#t:Maybe">Maybe</a> (<a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a>, a, <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a)<a href="src/Data-Trie-Internal.html#updateMinViewBy" class="link">Source</a></p></div><div class="top"><p class="src"><a name="v:updateMaxViewBy" class="def">updateMaxViewBy</a> :: (<a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a> -> a -> <a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Maybe.html#t:Maybe">Maybe</a> a) -> <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a -> <a href="/usr/share/doc/ghc/html/libraries/base-4.3.1.0/Data-Maybe.html#t:Maybe">Maybe</a> (<a href="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.10/Data-ByteString.html#t:ByteString">ByteString</a>, a, <a href="Data-Trie-Internal.html#t:Trie">Trie</a> a)<a href="src/Data-Trie-Internal.html#updateMaxViewBy" class="link">Source</a></p></div></div></div><div id="footer"><p>Produced by <a href="http://www.haskell.org/haddock/">Haddock</a> version 2.9.2</p></div></body></html>
