<!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</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.html");}; //]]> </script></head><body><div id="package-header"><ul class="links" id="page-menu"><li><a href="src/Data-Trie.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</td></tr><tr><th>Stability</th><td>experimental</td></tr><tr><th>Maintainer</th><td>wren@community.haskell.org</td></tr></table><p class="caption">Data.Trie</p></div><div id="table-of-contents"><p class="caption">Contents</p><ul><li><a href="#g:1">Data type </a></li><li><a href="#g:2">Basic functions </a></li><li><a href="#g:3">Conversion functions </a></li><li><a href="#g:4">Query functions </a></li><li><a href="#g:5">Single-value modification </a></li><li><a href="#g:6">Combining tries </a></li><li><a href="#g:7">Mapping functions </a></li></ul></div><div id="description"><p class="caption">Description</p><div class="doc"><p>An efficient implementation of finite maps from strings to values. The implementation is based on <em>big-endian patricia trees</em>, like <a href="Data-IntMap.html">Data.IntMap</a>. We first trie on the elements of <a href="Data-ByteString.html">Data.ByteString</a> and then trie on the big-endian bit representation of those elements. For further details on the latter, see </p><ul><li> Chris Okasaki and Andy Gill, "<em>Fast Mergeable Integer Maps</em>", Workshop on ML, September 1998, pages 77-86, <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.5452">http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.5452</a> </li><li> D.R. Morrison, "<em>PATRICIA -- Practical Algorithm To Retrieve</em> <em>Information Coded In Alphanumeric</em>", Journal of the ACM, 15(4), October 1968, pages 514-534. </li></ul><p>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 href="Data-Trie-Convenience.html">Data.Trie.Convenience</a>. For functions that give more detailed (potentially abstraction-breaking) access to the data strucuture, or for experimental functions which aren't quite ready for the public API, see <a href="Data-Trie-Internal.html">Data.Trie.Internal</a>. </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:empty">empty</a> :: <a href="Data-Trie.html#t:Trie">Trie</a> a</li><li class="src short"><a href="#v:null">null</a> :: <a href="Data-Trie.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.html#t:Trie">Trie</a> a</li><li class="src short"><a href="#v:size">size</a> :: <a href="Data-Trie.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:fromList">fromList</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.html#t:Trie">Trie</a> a</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.html#t:Trie">Trie</a> a -> [b]</li><li class="src short"><a href="#v:toList">toList</a> :: <a href="Data-Trie.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)]</li><li class="src short"><a href="#v:keys">keys</a> :: <a href="Data-Trie.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>]</li><li class="src short"><a href="#v:elems">elems</a> :: <a href="Data-Trie.html#t:Trie">Trie</a> a -> [a]</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.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.html#t:Trie">Trie</a> a -> b</li><li class="src short"><a href="#v:lookup">lookup</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.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</li><li class="src short"><a href="#v:member">member</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.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: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.html#t:Trie">Trie</a> a -> <a href="Data-Trie.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.html#t:Trie">Trie</a> a -> <a href="Data-Trie.html#t:Trie">Trie</a> a</li><li class="src short"><a href="#v:insert">insert</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.html#t:Trie">Trie</a> a -> <a href="Data-Trie.html#t:Trie">Trie</a> a</li><li class="src short"><a href="#v:adjust">adjust</a> :: (a -> 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.html#t:Trie">Trie</a> a -> <a href="Data-Trie.html#t:Trie">Trie</a> a</li><li class="src short"><a href="#v:delete">delete</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.html#t:Trie">Trie</a> a -> <a href="Data-Trie.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.html#t:Trie">Trie</a> a -> <a href="Data-Trie.html#t:Trie">Trie</a> a -> <a href="Data-Trie.html#t:Trie">Trie</a> a</li><li class="src short"><a href="#v:unionL">unionL</a> :: <a href="Data-Trie.html#t:Trie">Trie</a> a -> <a href="Data-Trie.html#t:Trie">Trie</a> a -> <a href="Data-Trie.html#t:Trie">Trie</a> a</li><li class="src short"><a href="#v:unionR">unionR</a> :: <a href="Data-Trie.html#t:Trie">Trie</a> a -> <a href="Data-Trie.html#t:Trie">Trie</a> a -> <a href="Data-Trie.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.html#t:Trie">Trie</a> a -> <a href="Data-Trie.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.html#t:Trie">Trie</a> a -> <a href="Data-Trie.html#t:Trie">Trie</a> b</li></ul></div><div id="interface"><h1 id="g:1">Data type </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.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.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.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.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.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.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.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.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.html#t:Trie">Trie</a> a)</td><td class="doc empty"> </td></tr></table></div></div></div><h1 id="g:2">Basic functions </h1><div class="top"><p class="src"><a name="v:empty" class="def">empty</a> :: <a href="Data-Trie.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.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.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.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:3">Conversion functions </h1><div class="top"><p class="src"><a name="v:fromList" class="def">fromList</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.html#t:Trie">Trie</a> a<a href="src/Data-Trie.html#fromList" class="link">Source</a></p><div class="doc"><p>Convert association list into a trie. On key conflict, values earlier in the list shadow later ones. </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.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><div class="top"><p class="src"><a name="v:toList" class="def">toList</a> :: <a href="Data-Trie.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="src/Data-Trie.html#toList" class="link">Source</a></p><div class="doc"><p>Convert trie into association list. Keys will be in sorted order. </p></div></div><div class="top"><p class="src"><a name="v:keys" class="def">keys</a> :: <a href="Data-Trie.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 href="src/Data-Trie.html#keys" class="link">Source</a></p><div class="doc"><p>Return all keys in the trie, in sorted order. </p></div></div><div class="top"><p class="src"><a name="v:elems" class="def">elems</a> :: <a href="Data-Trie.html#t:Trie">Trie</a> a -> [a]<a href="src/Data-Trie.html#elems" class="link">Source</a></p><div class="doc"><p>Return all values in the trie, in sorted order according to the keys. </p></div></div><h1 id="g:4">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.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.html#t:Trie">Trie</a> a -> b<a href="src/Data-Trie.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. </p></div></div><div class="top"><p class="src"><a name="v:lookup" class="def">lookup</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.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="src/Data-Trie.html#lookup" class="link">Source</a></p><div class="doc"><p>Return the value associated with a query string if it exists. </p></div></div><div class="top"><p class="src"><a name="v:member" class="def">member</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.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.html#member" class="link">Source</a></p><div class="doc"><p>Does a string have a value in the trie? </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.html#t:Trie">Trie</a> a -> <a href="Data-Trie.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:5">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.html#t:Trie">Trie</a> a -> <a href="Data-Trie.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:insert" class="def">insert</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.html#t:Trie">Trie</a> a -> <a href="Data-Trie.html#t:Trie">Trie</a> a<a href="src/Data-Trie.html#insert" class="link">Source</a></p><div class="doc"><p>Insert a new key. If the key is already present, overrides the old value </p></div></div><div class="top"><p class="src"><a name="v:adjust" class="def">adjust</a> :: (a -> 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.html#t:Trie">Trie</a> a -> <a href="Data-Trie.html#t:Trie">Trie</a> a<a href="src/Data-Trie.html#adjust" class="link">Source</a></p><div class="doc"><p>Apply a function to the value at a key. </p></div></div><div class="top"><p class="src"><a name="v:delete" class="def">delete</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.html#t:Trie">Trie</a> a -> <a href="Data-Trie.html#t:Trie">Trie</a> a<a href="src/Data-Trie.html#delete" class="link">Source</a></p><div class="doc"><p>Remove the value stored at a key. </p></div></div><h1 id="g:6">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.html#t:Trie">Trie</a> a -> <a href="Data-Trie.html#t:Trie">Trie</a> a -> <a href="Data-Trie.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><div class="top"><p class="src"><a name="v:unionL" class="def">unionL</a> :: <a href="Data-Trie.html#t:Trie">Trie</a> a -> <a href="Data-Trie.html#t:Trie">Trie</a> a -> <a href="Data-Trie.html#t:Trie">Trie</a> a<a href="src/Data-Trie.html#unionL" class="link">Source</a></p><div class="doc"><p>Combine two tries, resolving conflicts by choosing the value from the left trie. </p></div></div><div class="top"><p class="src"><a name="v:unionR" class="def">unionR</a> :: <a href="Data-Trie.html#t:Trie">Trie</a> a -> <a href="Data-Trie.html#t:Trie">Trie</a> a -> <a href="Data-Trie.html#t:Trie">Trie</a> a<a href="src/Data-Trie.html#unionR" class="link">Source</a></p><div class="doc"><p>Combine two tries, resolving conflicts by choosing the value from the right trie. </p></div></div><h1 id="g:7">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.html#t:Trie">Trie</a> a -> <a href="Data-Trie.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.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.html#t:Trie">Trie</a> a -> <a href="Data-Trie.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></div><div id="footer"><p>Produced by <a href="http://www.haskell.org/haddock/">Haddock</a> version 2.9.2</p></div></body></html>