Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Browse files

updated haddocks

  • Loading branch information...
commit d72e49aec6d21f94bc8ee099908e4dd3a7844377 1 parent 1430b2d
@ekmett authored
View
54 Data-LCA-Online-Monoidal.html
@@ -1,48 +1,14 @@
<!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.LCA.Online.Monoidal</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-LCA-Online-Monoidal.html");};
//]]>
-</script></head><body><div id="package-header"><ul class="links" id="page-menu"><li><a href="src/Data-LCA-Online-Monoidal.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">lca-0.2.4: O(log n) persistent on-line lowest common ancestor calculation without preprocessing</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>Edward Kmett &lt;ekmett@gmail.com&gt;</td></tr><tr><th>Safe Haskell</th><td>Safe-Inferred</td></tr></table><p class="caption">Data.LCA.Online.Monoidal</p></div><div id="description"><p class="caption">Description</p><div class="doc"><p>Provides online calculation of the the lowest common ancestor in <em>O(log h)</em>
+</script></head><body><div id="package-header"><ul class="links" id="page-menu"><li><a href="src/Data-LCA-Online-Monoidal.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">lca-0.3: O(log n) persistent on-line lowest common ancestor calculation without preprocessing</p></div><div id="content"><div id="module-header"><table class="info"><tr><th>Copyright</th><td>(C) 2012-2015 Edward Kmett</td></tr><tr><th>License</th><td>BSD-style (see the file LICENSE)</td></tr><tr><th>Maintainer</th><td>Edward Kmett &lt;ekmett@gmail.com&gt;</td></tr><tr><th>Stability</th><td>experimental</td></tr><tr><th>Portability</th><td>portable</td></tr><tr><th>Safe Haskell</th><td>Safe-Inferred</td></tr><tr><th>Language</th><td>Haskell98</td></tr></table><p class="caption">Data.LCA.Online.Monoidal</p></div><div id="description"><p class="caption">Description</p><div class="doc"><p>Provides online calculation of the the lowest common ancestor in <em>O(log h)</em>
by compressing the spine of the paths using a skew-binary random access
- list.
-</p><p>This library implements the technique described in my talk
-</p><p><a href="http://www.slideshare.net/ekmett/skewbinary-online-lowest-common-ancestor-search">http://www.slideshare.net/ekmett/skewbinary-online-lowest-common-ancestor-search</a>
-</p><p>to improve the known asymptotic bounds on both online lowest common ancestor search
-</p><p><a href="http://en.wikipedia.org/wiki/Lowest_common_ancestor">http://en.wikipedia.org/wiki/Lowest_common_ancestor</a>
-</p><p>and the online level ancestor problem:
-</p><p><a href="http://en.wikipedia.org/wiki/Level_ancestor_problem">http://en.wikipedia.org/wiki/Level_ancestor_problem</a>
-</p><p>Algorithms used here assume that the key values chosen for <code>k</code> are
- globally unique.
-</p><p>This version provides access to a monoidal &quot;summary&quot; of the
- elided path for many operations.
-</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:Path">Path</a> a</li><li class="src short"><a href="#v:toList">toList</a> :: <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; [(<a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a>, a)]</li><li class="src short"><a href="#v:fromList">fromList</a> :: <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a =&gt; [(<a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a>, a)] -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:map">map</a> :: <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Monoid.html#t:Monoid">Monoid</a> b =&gt; (a -&gt; b) -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b</li><li class="src short"><a href="#v:mapHom">mapHom</a> :: (a -&gt; b) -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b</li><li class="src short"><a href="#v:mapWithKey">mapWithKey</a> :: <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Monoid.html#t:Monoid">Monoid</a> b =&gt; (<a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a> -&gt; a -&gt; b) -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b</li><li class="src short"><a href="#v:traverse">traverse</a> :: (<a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Control-Applicative.html#t:Applicative">Applicative</a> f, <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Monoid.html#t:Monoid">Monoid</a> b) =&gt; (a -&gt; f b) -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; f (<a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b)</li><li class="src short"><a href="#v:traverseWithKey">traverseWithKey</a> :: (<a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Control-Applicative.html#t:Applicative">Applicative</a> f, <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Monoid.html#t:Monoid">Monoid</a> b) =&gt; (<a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a> -&gt; a -&gt; f b) -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; f (<a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b)</li><li class="src short"><a href="#v:empty">empty</a> :: <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:cons">cons</a> :: <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a =&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a> -&gt; a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:uncons">uncons</a> :: <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a =&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Maybe.html#t:Maybe">Maybe</a> (<a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a>, a, <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a)</li><li class="src short"><a href="#v:view">view</a> :: <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a =&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-View.html#t:View">View</a> <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:null">null</a> :: <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Bool.html#t:Bool">Bool</a></li><li class="src short"><a href="#v:length">length</a> :: <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a></li><li class="src short"><a href="#v:measure">measure</a> :: <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a =&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; a</li><li class="src short"><a href="#v:isAncestorOf">isAncestorOf</a> :: <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Monoid.html#t:Monoid">Monoid</a> b =&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b -&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Bool.html#t:Bool">Bool</a></li><li class="src short"><a href="#v:keep">keep</a> :: <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a =&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a> -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:mkeep">mkeep</a> :: <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a =&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a> -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; (a, <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a)</li><li class="src short"><a href="#v:drop">drop</a> :: <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a =&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a> -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:mdrop">mdrop</a> :: <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a =&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a> -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; (a, <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a)</li><li class="src short"><a href="#v:-126--61-">(~=)</a> :: <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b -&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Bool.html#t:Bool">Bool</a></li><li class="src short"><a href="#v:lca">lca</a> :: (<a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a, <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Monoid.html#t:Monoid">Monoid</a> b) =&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:mlca">mlca</a> :: (<a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a, <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Monoid.html#t:Monoid">Monoid</a> b) =&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b -&gt; (a, <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a, b, <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b)</li></ul></div><div id="interface"><h1>Documentation</h1><div class="top"><p class="src"><span class="keyword">data</span> <a name="t:Path" class="def">Path</a> a <a href="src/Data-LCA-Online-Monoidal.html#Path" class="link">Source</a></p><div class="doc"><p>A compressed <code><a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a></code> as a skew binary random access list
-</p></div><div class="subs instances"><p id="control.i:Path" class="caption collapser" onclick="toggleSection('i:Path')">Instances</p><div id="section.i:Path" class="show"><table><tr><td class="src"><a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Foldable.html#t:Foldable">Foldable</a> <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a></td><td class="doc empty">&nbsp;</td></tr><tr><td class="src"><a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Text-Read.html#t:Read">Read</a> a =&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Text-Read.html#t:Read">Read</a> (<a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a)</td><td class="doc empty">&nbsp;</td></tr><tr><td class="src"><a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Text-Show.html#t:Show">Show</a> a =&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Text-Show.html#t:Show">Show</a> (<a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a)</td><td class="doc empty">&nbsp;</td></tr></table></div></div></div><div class="top"><p class="src"><a name="v:toList" class="def">toList</a> :: <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; [(<a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a>, a)]<a href="src/Data-LCA-Online-Monoidal.html#toList" class="link">Source</a></p><div class="doc"><p>Convert a <code><a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a></code> to a list of <code>(ID, value)</code> pairs.
-</p></div></div><div class="top"><p class="src"><a name="v:fromList" class="def">fromList</a> :: <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a =&gt; [(<a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a>, a)] -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a<a href="src/Data-LCA-Online-Monoidal.html#fromList" class="link">Source</a></p><div class="doc"><p>Build a <code><a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a></code> from a list of <code>(ID, value)</code> pairs.
-</p></div></div><div class="top"><p class="src"><a name="v:map" class="def">map</a> :: <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Monoid.html#t:Monoid">Monoid</a> b =&gt; (a -&gt; b) -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b<a href="src/Data-LCA-Online-Monoidal.html#map" class="link">Source</a></p><div class="doc"><p><em>O(n)</em> Re-annotate a <code><a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a></code> full of monoidal values using a different <code><a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Monoid.html#t:Monoid">Monoid</a></code>.
-</p></div></div><div class="top"><p class="src"><a name="v:mapHom" class="def">mapHom</a> :: (a -&gt; b) -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b<a href="src/Data-LCA-Online-Monoidal.html#mapHom" class="link">Source</a></p><div class="doc"><p><em>O(n)</em> Re-annotate a <code><a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a></code> full of monoidal values/
-</p><p>Unlike <code><a href="Data-LCA-Online-Monoidal.html#v:map">map</a></code>, <code><code><a href="Data-LCA-Online-Monoidal.html#v:mapHom">mapHom</a></code> f</code> assumes that f is a <code><a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Monoid.html#t:Monoid">Monoid</a></code> homomorphism, that is to say you must ensure
-</p><pre>
- f a `'mappend'` f b = f (a `'mappend'` b)
- f <code><a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Monoid.html#v:mempty">mempty</a></code> = <code><a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Monoid.html#v:mempty">mempty</a></code>
-</pre></div></div><div class="top"><p class="src"><a name="v:mapWithKey" class="def">mapWithKey</a> :: <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Monoid.html#t:Monoid">Monoid</a> b =&gt; (<a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a> -&gt; a -&gt; b) -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b<a href="src/Data-LCA-Online-Monoidal.html#mapWithKey" class="link">Source</a></p><div class="doc"><p><em>O(n)</em> Re-annotate a <code><a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a></code> full of monoidal values with access to the key.
-</p></div></div><div class="top"><p class="src"><a name="v:traverse" class="def">traverse</a> :: (<a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Control-Applicative.html#t:Applicative">Applicative</a> f, <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Monoid.html#t:Monoid">Monoid</a> b) =&gt; (a -&gt; f b) -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; f (<a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b)<a href="src/Data-LCA-Online-Monoidal.html#traverse" class="link">Source</a></p><div class="doc"><p>Traverse a <code><a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a></code> yielding a new monoidal annotation.
-</p></div></div><div class="top"><p class="src"><a name="v:traverseWithKey" class="def">traverseWithKey</a> :: (<a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Control-Applicative.html#t:Applicative">Applicative</a> f, <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Monoid.html#t:Monoid">Monoid</a> b) =&gt; (<a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a> -&gt; a -&gt; f b) -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; f (<a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b)<a href="src/Data-LCA-Online-Monoidal.html#traverseWithKey" class="link">Source</a></p><div class="doc"><p>Traverse a <code><a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a></code> with access to the node IDs.
-</p></div></div><div class="top"><p class="src"><a name="v:empty" class="def">empty</a> :: <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a<a href="src/Data-LCA-Online-Monoidal.html#empty" class="link">Source</a></p><div class="doc"><p>The empty <code><a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a></code>
-</p></div></div><div class="top"><p class="src"><a name="v:cons" class="def">cons</a> :: <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a =&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a> -&gt; a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a<a href="src/Data-LCA-Online-Monoidal.html#cons" class="link">Source</a></p><div class="doc"><p><em>O(1)</em> Invariant: most operations assume that the keys <code>k</code> are globally unique
-</p><p>Extend the <code><a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a></code> with a new node ID and value.
-</p></div></div><div class="top"><p class="src"><a name="v:uncons" class="def">uncons</a> :: <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a =&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Maybe.html#t:Maybe">Maybe</a> (<a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a>, a, <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a)<a href="src/Data-LCA-Online-Monoidal.html#uncons" class="link">Source</a></p><div class="doc"><p><em>O(1)</em> Extract the node ID and value from the newest node on the <code><a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a></code>.
-</p></div></div><div class="top"><p class="src"><a name="v:view" class="def">view</a> :: <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a =&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-View.html#t:View">View</a> <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a<a href="src/Data-LCA-Online-Monoidal.html#view" class="link">Source</a></p><div class="doc"><p><em>O(1)</em> Extract the node ID and value from the newest node on the <code><a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a></code>, slightly faster than <code><a href="Data-LCA-Online-Monoidal.html#v:uncons">uncons</a></code>.
-</p></div></div><div class="top"><p class="src"><a name="v:null" class="def">null</a> :: <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Bool.html#t:Bool">Bool</a><a href="src/Data-LCA-Online-Monoidal.html#null" class="link">Source</a></p><div class="doc"><p><em>O(1)</em> Returns <code><a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Bool.html#v:True">True</a></code> iff the path is <code><a href="Data-LCA-Online-Monoidal.html#v:empty">empty</a></code>.
-</p></div></div><div class="top"><p class="src"><a name="v:length" class="def">length</a> :: <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a><a href="src/Data-LCA-Online-Monoidal.html#length" class="link">Source</a></p><div class="doc"><p><em>O(1)</em> Determine the <code><a href="Data-LCA-Online-Monoidal.html#v:length">length</a></code> of a <code><a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a></code>.
-</p></div></div><div class="top"><p class="src"><a name="v:measure" class="def">measure</a> :: <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a =&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; a<a href="src/Data-LCA-Online-Monoidal.html#measure" class="link">Source</a></p><div class="doc"><p>Extract a monoidal summary of a <code><a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a></code>.
-</p></div></div><div class="top"><p class="src"><a name="v:isAncestorOf" class="def">isAncestorOf</a> :: <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Monoid.html#t:Monoid">Monoid</a> b =&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b -&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Bool.html#t:Bool">Bool</a><a href="src/Data-LCA-Online-Monoidal.html#isAncestorOf" class="link">Source</a></p><div class="doc"><p><em>O(log h)</em> <code>xs `'isAncestorOf'` ys</code> holds when <code>xs</code> is a prefix starting at the root of path <code>ys</code>.
-</p></div></div><div class="top"><p class="src"><a name="v:keep" class="def">keep</a> :: <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a =&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a> -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a<a href="src/Data-LCA-Online-Monoidal.html#keep" class="link">Source</a></p><div class="doc"><p><em>O(log (h - k))</em> to <code><code><a href="Data-LCA-Online-Monoidal.html#v:keep">keep</a></code> k</code> elements of <code><a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a></code> of <code><a href="Data-LCA-Online-Monoidal.html#v:length">length</a></code> <code>h</code>
-</p><p>This solves the online version of the &quot;level ancestor problem&quot; with no preprocessing in <em>O(log h)</em> time,
- improving known complexity bounds.
-</p><p><a href="http://en.wikipedia.org/wiki/Level_ancestor_problem">http://en.wikipedia.org/wiki/Level_ancestor_problem</a>
-</p></div></div><div class="top"><p class="src"><a name="v:mkeep" class="def">mkeep</a> :: <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a =&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a> -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; (a, <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a)<a href="src/Data-LCA-Online-Monoidal.html#mkeep" class="link">Source</a></p><div class="doc"><p><em>O(log (h - k))</em> to keep <code>k</code> elements of <code><a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a></code> of <code><a href="Data-LCA-Online-Monoidal.html#v:length">length</a></code> <code>h</code>, and provide a monoidal summary of the dropped elements
-</p></div></div><div class="top"><p class="src"><a name="v:drop" class="def">drop</a> :: <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a =&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a> -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a<a href="src/Data-LCA-Online-Monoidal.html#drop" class="link">Source</a></p><div class="doc"><p><em>O(log k)</em> to <code><code><a href="Data-LCA-Online-Monoidal.html#v:drop">drop</a></code> k</code> elements from a <code><a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a></code>
-</p></div></div><div class="top"><p class="src"><a name="v:mdrop" class="def">mdrop</a> :: <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a =&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a> -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; (a, <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a)<a href="src/Data-LCA-Online-Monoidal.html#mdrop" class="link">Source</a></p><div class="doc"><p><em>O(log k)</em> to drop <code>k</code> elements from a <code><a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a></code> and provide a monoidal summary of the dropped elements
-</p></div></div><div class="top"><p class="src"><a name="v:-126--61-" class="def">(~=)</a> :: <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b -&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Bool.html#t:Bool">Bool</a><a href="src/Data-LCA-Online-Monoidal.html#~%3D" class="link">Source</a></p><div class="doc"><p><em>O(1)</em> Compare to see if two trees have the same leaf key
-</p></div></div><div class="top"><p class="src"><a name="v:lca" class="def">lca</a> :: (<a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a, <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Monoid.html#t:Monoid">Monoid</a> b) =&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a<a href="src/Data-LCA-Online-Monoidal.html#lca" class="link">Source</a></p><div class="doc"><p><em>O(log h)</em> Compute the lowest common ancestor of two paths
-</p></div></div><div class="top"><p class="src"><a name="v:mlca" class="def">mlca</a> :: (<a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a, <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Monoid.html#t:Monoid">Monoid</a> b) =&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b -&gt; (a, <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a, b, <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b)<a href="src/Data-LCA-Online-Monoidal.html#mlca" class="link">Source</a></p><div class="doc"><p><em>O(log h)</em> Compute the lowest common ancestor of two paths along with a monoidal summary of their respective tails.
-</p></div></div></div></div><div id="footer"><p>Produced by <a href="http://www.haskell.org/haddock/">Haddock</a> version 2.13.2</p></div></body></html>
+ list.</p><p>This library implements the technique described in my talk</p><p><a href="http://www.slideshare.net/ekmett/skewbinary-online-lowest-common-ancestor-search">http://www.slideshare.net/ekmett/skewbinary-online-lowest-common-ancestor-search</a></p><p>to improve the known asymptotic bounds on both online lowest common ancestor search</p><p><a href="http://en.wikipedia.org/wiki/Lowest_common_ancestor">http://en.wikipedia.org/wiki/Lowest_common_ancestor</a></p><p>and the online level ancestor problem:</p><p><a href="http://en.wikipedia.org/wiki/Level_ancestor_problem">http://en.wikipedia.org/wiki/Level_ancestor_problem</a></p><p>Algorithms used here assume that the key values chosen for <code>k</code> are
+ globally unique.</p><p>This version provides access to a monoidal &quot;summary&quot; of the
+ elided path for many operations.</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:Path">Path</a> a</li><li class="src short"><a href="#v:toList">toList</a> :: <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; [(<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a>, a)]</li><li class="src short"><a href="#v:fromList">fromList</a> :: <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a =&gt; [(<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a>, a)] -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:map">map</a> :: <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> b =&gt; (a -&gt; b) -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b</li><li class="src short"><a href="#v:mapHom">mapHom</a> :: (a -&gt; b) -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b</li><li class="src short"><a href="#v:mapWithKey">mapWithKey</a> :: <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> b =&gt; (<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> -&gt; a -&gt; b) -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b</li><li class="src short"><a href="#v:traverse">traverse</a> :: (<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Control-Applicative.html#t:Applicative">Applicative</a> f, <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> b) =&gt; (a -&gt; f b) -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; f (<a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b)</li><li class="src short"><a href="#v:traverseWithKey">traverseWithKey</a> :: (<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Control-Applicative.html#t:Applicative">Applicative</a> f, <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> b) =&gt; (<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> -&gt; a -&gt; f b) -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; f (<a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b)</li><li class="src short"><a href="#v:empty">empty</a> :: <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:cons">cons</a> :: <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a =&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> -&gt; a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:uncons">uncons</a> :: <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a =&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Maybe.html#t:Maybe">Maybe</a> (<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a>, a, <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a)</li><li class="src short"><a href="#v:view">view</a> :: <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a =&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-View.html#t:View">View</a> <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:null">null</a> :: <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Bool.html#t:Bool">Bool</a></li><li class="src short"><a href="#v:length">length</a> :: <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a></li><li class="src short"><a href="#v:measure">measure</a> :: <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a =&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; a</li><li class="src short"><a href="#v:isAncestorOf">isAncestorOf</a> :: <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> b =&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b -&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Bool.html#t:Bool">Bool</a></li><li class="src short"><a href="#v:keep">keep</a> :: <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a =&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:mkeep">mkeep</a> :: (<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a, <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> b) =&gt; (a -&gt; b) -&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; (b, <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a)</li><li class="src short"><a href="#v:drop">drop</a> :: <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a =&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:mdrop">mdrop</a> :: (<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a, <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> b) =&gt; (a -&gt; b) -&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; (b, <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a)</li><li class="src short"><a href="#v:-126--61-">(~=)</a> :: <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b -&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Bool.html#t:Bool">Bool</a></li><li class="src short"><a href="#v:lca">lca</a> :: (<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a, <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> b) =&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:mlca">mlca</a> :: (<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a, <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> b, <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> c, <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> d) =&gt; (a -&gt; c) -&gt; (b -&gt; d) -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b -&gt; (c, <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a, d, <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b)</li></ul></div><div id="interface"><h1>Documentation</h1><div class="top"><p class="src"><span class="keyword">data</span> <a name="t:Path" class="def">Path</a> a <a href="src/Data-LCA-Online-Monoidal.html#Path" class="link">Source</a></p><div class="doc"><p>A compressed <code><a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a></code> as a skew binary random access list</p></div><div class="subs instances"><p id="control.i:Path" class="caption collapser" onclick="toggleSection('i:Path')">Instances</p><div id="section.i:Path" class="show"><table><tr><td class="src"><a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Foldable.html#t:Foldable">Foldable</a> <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a></td><td class="doc empty">&nbsp;</td></tr><tr><td class="src"><a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Text-Read.html#t:Read">Read</a> a =&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Text-Read.html#t:Read">Read</a> (<a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a)</td><td class="doc empty">&nbsp;</td></tr><tr><td class="src"><a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Text-Show.html#t:Show">Show</a> a =&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Text-Show.html#t:Show">Show</a> (<a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a)</td><td class="doc empty">&nbsp;</td></tr></table></div></div></div><div class="top"><p class="src"><a name="v:toList" class="def">toList</a> :: <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; [(<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a>, a)] <a href="src/Data-LCA-Online-Monoidal.html#toList" class="link">Source</a></p><div class="doc"><p>Convert a <code><a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a></code> to a list of <code>(ID, value)</code> pairs.</p></div></div><div class="top"><p class="src"><a name="v:fromList" class="def">fromList</a> :: <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a =&gt; [(<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a>, a)] -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a <a href="src/Data-LCA-Online-Monoidal.html#fromList" class="link">Source</a></p><div class="doc"><p>Build a <code><a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a></code> from a list of <code>(ID, value)</code> pairs.</p></div></div><div class="top"><p class="src"><a name="v:map" class="def">map</a> :: <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> b =&gt; (a -&gt; b) -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b <a href="src/Data-LCA-Online-Monoidal.html#map" class="link">Source</a></p><div class="doc"><p><em>O(n)</em> Re-annotate a <code><a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a></code> full of monoidal values using a different <code><a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a></code>.</p></div></div><div class="top"><p class="src"><a name="v:mapHom" class="def">mapHom</a> :: (a -&gt; b) -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b <a href="src/Data-LCA-Online-Monoidal.html#mapHom" class="link">Source</a></p><div class="doc"><p><em>O(n)</em> Re-annotate a <code><a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a></code> full of monoidal values/</p><p>Unlike <code><a href="Data-LCA-Online-Monoidal.html#v:map">map</a></code>, <code><code><a href="Data-LCA-Online-Monoidal.html#v:mapHom">mapHom</a></code> f</code> assumes that <code>f</code> is a <code><a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a></code> homomorphism, that is to say you must ensure</p><pre>f a `'mappend'` f b = f (a `'mappend'` b)
+f <code><a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#v:mempty">mempty</a></code> = <code><a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#v:mempty">mempty</a></code>
+</pre></div></div><div class="top"><p class="src"><a name="v:mapWithKey" class="def">mapWithKey</a> :: <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> b =&gt; (<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> -&gt; a -&gt; b) -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b <a href="src/Data-LCA-Online-Monoidal.html#mapWithKey" class="link">Source</a></p><div class="doc"><p><em>O(n)</em> Re-annotate a <code><a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a></code> full of monoidal values with access to the key.</p></div></div><div class="top"><p class="src"><a name="v:traverse" class="def">traverse</a> :: (<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Control-Applicative.html#t:Applicative">Applicative</a> f, <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> b) =&gt; (a -&gt; f b) -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; f (<a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b) <a href="src/Data-LCA-Online-Monoidal.html#traverse" class="link">Source</a></p><div class="doc"><p>Traverse a <code><a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a></code> yielding a new monoidal annotation.</p></div></div><div class="top"><p class="src"><a name="v:traverseWithKey" class="def">traverseWithKey</a> :: (<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Control-Applicative.html#t:Applicative">Applicative</a> f, <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> b) =&gt; (<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> -&gt; a -&gt; f b) -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; f (<a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b) <a href="src/Data-LCA-Online-Monoidal.html#traverseWithKey" class="link">Source</a></p><div class="doc"><p>Traverse a <code><a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a></code> with access to the node IDs.</p></div></div><div class="top"><p class="src"><a name="v:empty" class="def">empty</a> :: <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a <a href="src/Data-LCA-Online-Monoidal.html#empty" class="link">Source</a></p><div class="doc"><p>The empty <code><a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a></code></p></div></div><div class="top"><p class="src"><a name="v:cons" class="def">cons</a> :: <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a =&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> -&gt; a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a <a href="src/Data-LCA-Online-Monoidal.html#cons" class="link">Source</a></p><div class="doc"><p><em>O(1)</em> Invariant: most operations assume that the keys <code>k</code> are globally unique</p><p>Extend the <code><a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a></code> with a new node ID and value.</p></div></div><div class="top"><p class="src"><a name="v:uncons" class="def">uncons</a> :: <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a =&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Maybe.html#t:Maybe">Maybe</a> (<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a>, a, <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a) <a href="src/Data-LCA-Online-Monoidal.html#uncons" class="link">Source</a></p><div class="doc"><p><em>O(1)</em> Extract the node ID and value from the newest node on the <code><a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a></code>.</p></div></div><div class="top"><p class="src"><a name="v:view" class="def">view</a> :: <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a =&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-View.html#t:View">View</a> <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a <a href="src/Data-LCA-Online-Monoidal.html#view" class="link">Source</a></p><div class="doc"><p><em>O(1)</em> Extract the node ID and value from the newest node on the <code><a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a></code>, slightly faster than <code><a href="Data-LCA-Online-Monoidal.html#v:uncons">uncons</a></code>.</p></div></div><div class="top"><p class="src"><a name="v:null" class="def">null</a> :: <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Bool.html#t:Bool">Bool</a> <a href="src/Data-LCA-Online-Monoidal.html#null" class="link">Source</a></p><div class="doc"><p><em>O(1)</em> Returns <code><a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Bool.html#v:True">True</a></code> iff the path is <code><a href="Data-LCA-Online-Monoidal.html#v:empty">empty</a></code>.</p></div></div><div class="top"><p class="src"><a name="v:length" class="def">length</a> :: <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> <a href="src/Data-LCA-Online-Monoidal.html#length" class="link">Source</a></p><div class="doc"><p><em>O(1)</em> Determine the <code><a href="Data-LCA-Online-Monoidal.html#v:length">length</a></code> of a <code><a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a></code>.</p></div></div><div class="top"><p class="src"><a name="v:measure" class="def">measure</a> :: <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a =&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; a <a href="src/Data-LCA-Online-Monoidal.html#measure" class="link">Source</a></p><div class="doc"><p>Extract a monoidal summary of a <code><a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a></code>.</p></div></div><div class="top"><p class="src"><a name="v:isAncestorOf" class="def">isAncestorOf</a> :: <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> b =&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b -&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Bool.html#t:Bool">Bool</a> <a href="src/Data-LCA-Online-Monoidal.html#isAncestorOf" class="link">Source</a></p><div class="doc"><p><em>O(log h)</em> <code>xs `'isAncestorOf'` ys</code> holds when <code>xs</code> is a prefix starting at the root of path <code>ys</code>.</p></div></div><div class="top"><p class="src"><a name="v:keep" class="def">keep</a> :: <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a =&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a <a href="src/Data-LCA-Online-Monoidal.html#keep" class="link">Source</a></p><div class="doc"><p><em>O(log (h - k))</em> to <code><code><a href="Data-LCA-Online-Monoidal.html#v:keep">keep</a></code> k</code> elements of <code><a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a></code> of <code><a href="Data-LCA-Online-Monoidal.html#v:length">length</a></code> <code>h</code></p><p>This solves the online version of the &quot;level ancestor problem&quot; with no preprocessing in <em>O(log h)</em> time,
+ improving known complexity bounds.</p><p><a href="http://en.wikipedia.org/wiki/Level_ancestor_problem">http://en.wikipedia.org/wiki/Level_ancestor_problem</a></p></div></div><div class="top"><p class="src"><a name="v:mkeep" class="def">mkeep</a> :: (<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a, <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> b) =&gt; (a -&gt; b) -&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; (b, <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a) <a href="src/Data-LCA-Online-Monoidal.html#mkeep" class="link">Source</a></p><div class="doc"><p><em>O(log (h - k))</em> to keep <code>k</code> elements of <code><a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a></code> of <code><a href="Data-LCA-Online-Monoidal.html#v:length">length</a></code> <code>h</code>, and provide a monoidal summary of the dropped elements
+ using a supplied monoid homomorphism.</p></div></div><div class="top"><p class="src"><a name="v:drop" class="def">drop</a> :: <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a =&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a <a href="src/Data-LCA-Online-Monoidal.html#drop" class="link">Source</a></p><div class="doc"><p><em>O(log k)</em> to <code><code><a href="Data-LCA-Online-Monoidal.html#v:drop">drop</a></code> k</code> elements from a <code><a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a></code></p></div></div><div class="top"><p class="src"><a name="v:mdrop" class="def">mdrop</a> :: (<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a, <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> b) =&gt; (a -&gt; b) -&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; (b, <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a) <a href="src/Data-LCA-Online-Monoidal.html#mdrop" class="link">Source</a></p><div class="doc"><p><em>O(log k)</em> to drop <code>k</code> elements from a <code><a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a></code> and provide a monoidal summary of the dropped elements
+ using a suplied monoid homomorphism</p></div></div><div class="top"><p class="src"><a name="v:-126--61-" class="def">(~=)</a> :: <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b -&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Bool.html#t:Bool">Bool</a> <span class="fixity">infix 4</span><span class="rightedge"></span> <a href="src/Data-LCA-Online-Monoidal.html#~%3D" class="link">Source</a></p><div class="doc"><p><em>O(1)</em> Compare to see if two trees have the same leaf key</p></div></div><div class="top"><p class="src"><a name="v:lca" class="def">lca</a> :: (<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a, <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> b) =&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a <a href="src/Data-LCA-Online-Monoidal.html#lca" class="link">Source</a></p><div class="doc"><p><em>O(log h)</em> Compute the lowest common ancestor of two paths</p></div></div><div class="top"><p class="src"><a name="v:mlca" class="def">mlca</a> :: (<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> a, <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> b, <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> c, <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Monoid.html#t:Monoid">Monoid</a> d) =&gt; (a -&gt; c) -&gt; (b -&gt; d) -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b -&gt; (c, <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a, d, <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b) <a href="src/Data-LCA-Online-Monoidal.html#mlca" class="link">Source</a></p><div class="doc"><p><em>O(log h)</em> Compute the lowest common ancestor of two paths along with a monoidal summary of their respective tails using
+ the supplied monoid homomorphisms.</p></div></div></div></div><div id="footer"><p>Produced by <a href="http://www.haskell.org/haddock/">Haddock</a> version 2.15.1</p></div></body></html>
View
19 Data-LCA-Online-Naive.html
@@ -1,21 +1,4 @@
<!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.LCA.Online.Naive</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-LCA-Online-Naive.html");};
//]]>
-</script></head><body><div id="package-header"><ul class="links" id="page-menu"><li><a href="src/Data-LCA-Online-Naive.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">lca-0.2.4: O(log n) persistent on-line lowest common ancestor calculation without preprocessing</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>Edward Kmett &lt;ekmett@gmail.com&gt;</td></tr><tr><th>Safe Haskell</th><td>Safe-Inferred</td></tr></table><p class="caption">Data.LCA.Online.Naive</p></div><div id="description"><p class="caption">Description</p><div class="doc"><p>Naive online calculation of the the lowest common ancestor in <em>O(h)</em>
-</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:Path">Path</a> a</li><li class="src short"><a href="#v:empty">empty</a> :: <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:cons">cons</a> :: <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a> -&gt; a -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:uncons">uncons</a> :: <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Maybe.html#t:Maybe">Maybe</a> (<a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a>, a, <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a)</li><li class="src short"><a href="#v:view">view</a> :: <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-View.html#t:View">View</a> <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:null">null</a> :: <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Bool.html#t:Bool">Bool</a></li><li class="src short"><a href="#v:length">length</a> :: <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a></li><li class="src short"><a href="#v:isAncestorOf">isAncestorOf</a> :: <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> b -&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Bool.html#t:Bool">Bool</a></li><li class="src short"><a href="#v:lca">lca</a> :: <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> b -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:keep">keep</a> :: <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a> -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:drop">drop</a> :: <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a> -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:traverseWithKey">traverseWithKey</a> :: <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Control-Applicative.html#t:Applicative">Applicative</a> f =&gt; (<a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a> -&gt; a -&gt; f b) -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; f (<a href="Data-LCA-Online-Naive.html#t:Path">Path</a> b)</li><li class="src short"><a href="#v:toList">toList</a> :: <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; [(<a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a>, a)]</li><li class="src short"><a href="#v:fromList">fromList</a> :: [(<a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a>, a)] -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:-126--61-">(~=)</a> :: <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> b -&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Bool.html#t:Bool">Bool</a></li></ul></div><div id="interface"><h1>Documentation</h1><div class="top"><p class="src"><span class="keyword">data</span> <a name="t:Path" class="def">Path</a> a <a href="src/Data-LCA-Online-Naive.html#Path" class="link">Source</a></p><div class="doc"><p>An uncompressed <code><a href="Data-LCA-Online-Naive.html#t:Path">Path</a></code> with memoized length.
-</p></div><div class="subs instances"><p id="control.i:Path" class="caption collapser" onclick="toggleSection('i:Path')">Instances</p><div id="section.i:Path" class="show"><table><tr><td class="src"><a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Control-Monad.html#t:Functor">Functor</a> <a href="Data-LCA-Online-Naive.html#t:Path">Path</a></td><td class="doc empty">&nbsp;</td></tr><tr><td class="src"><a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Foldable.html#t:Foldable">Foldable</a> <a href="Data-LCA-Online-Naive.html#t:Path">Path</a></td><td class="doc empty">&nbsp;</td></tr><tr><td class="src"><a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Traversable.html#t:Traversable">Traversable</a> <a href="Data-LCA-Online-Naive.html#t:Path">Path</a></td><td class="doc empty">&nbsp;</td></tr><tr><td class="src"><a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Text-Read.html#t:Read">Read</a> a =&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Text-Read.html#t:Read">Read</a> (<a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a)</td><td class="doc empty">&nbsp;</td></tr><tr><td class="src"><a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Text-Show.html#t:Show">Show</a> a =&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Text-Show.html#t:Show">Show</a> (<a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a)</td><td class="doc empty">&nbsp;</td></tr></table></div></div></div><div class="top"><p class="src"><a name="v:empty" class="def">empty</a> :: <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a<a href="src/Data-LCA-Online-Naive.html#empty" class="link">Source</a></p><div class="doc"><p>The empty <code><a href="Data-LCA-Online-Naive.html#t:Path">Path</a></code>
-</p></div></div><div class="top"><p class="src"><a name="v:cons" class="def">cons</a> :: <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a> -&gt; a -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a<a href="src/Data-LCA-Online-Naive.html#cons" class="link">Source</a></p><div class="doc"><p><em>O(1)</em> Invariant: most operations assume that the keys <code>k</code> are globally unique
-</p><p>Extend the path with a new node ID and value.
-</p></div></div><div class="top"><p class="src"><a name="v:uncons" class="def">uncons</a> :: <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Maybe.html#t:Maybe">Maybe</a> (<a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a>, a, <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a)<a href="src/Data-LCA-Online-Naive.html#uncons" class="link">Source</a></p><div class="doc"><p><em>O(1)</em> Extract the node ID and value from the newest node on the <code><a href="Data-LCA-Online-Naive.html#t:Path">Path</a></code>.
-</p></div></div><div class="top"><p class="src"><a name="v:view" class="def">view</a> :: <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-View.html#t:View">View</a> <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a<a href="src/Data-LCA-Online-Naive.html#view" class="link">Source</a></p><div class="doc"><p><em>O(1)</em> Extract the node ID and value from the newest node on the <code><a href="Data-LCA-Online-Naive.html#t:Path">Path</a></code>, slightly faster than <code><a href="Data-LCA-Online-Naive.html#v:uncons">uncons</a></code>.
-</p></div></div><div class="top"><p class="src"><a name="v:null" class="def">null</a> :: <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Bool.html#t:Bool">Bool</a><a href="src/Data-LCA-Online-Naive.html#null" class="link">Source</a></p><div class="doc"><p><em>O(1)</em> Returns <code><a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Bool.html#v:True">True</a></code> iff the <code><a href="Data-LCA-Online-Naive.html#t:Path">Path</a></code> is <code><a href="Data-LCA-Online-Naive.html#v:empty">empty</a></code>.
-</p></div></div><div class="top"><p class="src"><a name="v:length" class="def">length</a> :: <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a><a href="src/Data-LCA-Online-Naive.html#length" class="link">Source</a></p><div class="doc"><p><em>O(1)</em> Determine the length of a <code><a href="Data-LCA-Online-Naive.html#t:Path">Path</a></code>.
-</p></div></div><div class="top"><p class="src"><a name="v:isAncestorOf" class="def">isAncestorOf</a> :: <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> b -&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Bool.html#t:Bool">Bool</a><a href="src/Data-LCA-Online-Naive.html#isAncestorOf" class="link">Source</a></p><div class="doc"><p><em>O(h)</em> <code>xs <code><a href="Data-LCA-Online-Naive.html#v:isAncestorOf">isAncestorOf</a></code> ys</code> holds when <code>xs</code> is a prefix starting at the root of <code><a href="Data-LCA-Online-Naive.html#t:Path">Path</a></code> <code>ys</code>.
-</p></div></div><div class="top"><p class="src"><a name="v:lca" class="def">lca</a> :: <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> b -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a<a href="src/Data-LCA-Online-Naive.html#lca" class="link">Source</a></p><div class="doc"><p><em>O(h)</em> Compute the lowest common ancestor of two paths
-</p></div></div><div class="top"><p class="src"><a name="v:keep" class="def">keep</a> :: <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a> -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a<a href="src/Data-LCA-Online-Naive.html#keep" class="link">Source</a></p><div class="doc"><p><em>O(h - k)</em> to <code><code><a href="Data-LCA-Online-Naive.html#v:keep">keep</a></code> k</code> elements of <code><a href="Data-LCA-Online-Naive.html#t:Path">Path</a></code> of <code><a href="Data-LCA-Online-Naive.html#v:length">length</a></code> <code>h</code>
-</p></div></div><div class="top"><p class="src"><a name="v:drop" class="def">drop</a> :: <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a> -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a<a href="src/Data-LCA-Online-Naive.html#drop" class="link">Source</a></p><div class="doc"><p><em>O(k)</em> to <code><code><a href="Data-LCA-Online-Naive.html#v:drop">drop</a></code> k</code> elements from a <code><a href="Data-LCA-Online-Naive.html#t:Path">Path</a></code>
-</p></div></div><div class="top"><p class="src"><a name="v:traverseWithKey" class="def">traverseWithKey</a> :: <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Control-Applicative.html#t:Applicative">Applicative</a> f =&gt; (<a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a> -&gt; a -&gt; f b) -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; f (<a href="Data-LCA-Online-Naive.html#t:Path">Path</a> b)<a href="src/Data-LCA-Online-Naive.html#traverseWithKey" class="link">Source</a></p><div class="doc"><p>Traverse a <code><a href="Data-LCA-Online-Naive.html#t:Path">Path</a></code> with access to the node IDs.
-</p></div></div><div class="top"><p class="src"><a name="v:toList" class="def">toList</a> :: <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; [(<a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a>, a)]<a href="src/Data-LCA-Online-Naive.html#toList" class="link">Source</a></p><div class="doc"><p>Convert a <code><a href="Data-LCA-Online-Naive.html#t:Path">Path</a></code> to a list of <code>(ID, value)</code> pairs.
-</p></div></div><div class="top"><p class="src"><a name="v:fromList" class="def">fromList</a> :: [(<a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a>, a)] -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a<a href="src/Data-LCA-Online-Naive.html#fromList" class="link">Source</a></p><div class="doc"><p>Build a <code><a href="Data-LCA-Online-Naive.html#t:Path">Path</a></code> from a list of <code>(ID, value)</code> pairs.
-</p></div></div><div class="top"><p class="src"><a name="v:-126--61-" class="def">(~=)</a> :: <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> b -&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Bool.html#t:Bool">Bool</a><a href="src/Data-LCA-Online-Naive.html#~%3D" class="link">Source</a></p><div class="doc"><p><em>O(1)</em> Compare to see if two trees have the same leaf key
-</p></div></div></div></div><div id="footer"><p>Produced by <a href="http://www.haskell.org/haddock/">Haddock</a> version 2.13.2</p></div></body></html>
+</script></head><body><div id="package-header"><ul class="links" id="page-menu"><li><a href="src/Data-LCA-Online-Naive.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">lca-0.3: O(log n) persistent on-line lowest common ancestor calculation without preprocessing</p></div><div id="content"><div id="module-header"><table class="info"><tr><th>Copyright</th><td>(C) 2011-2015 Edward Kmett</td></tr><tr><th>License</th><td>BSD-style (see the file LICENSE)</td></tr><tr><th>Maintainer</th><td>Edward Kmett &lt;ekmett@gmail.com&gt;</td></tr><tr><th>Stability</th><td>experimental</td></tr><tr><th>Portability</th><td>portable</td></tr><tr><th>Safe Haskell</th><td>Safe-Inferred</td></tr><tr><th>Language</th><td>Haskell98</td></tr></table><p class="caption">Data.LCA.Online.Naive</p></div><div id="description"><p class="caption">Description</p><div class="doc"><p>Naive online calculation of the the lowest common ancestor in <em>O(h)</em></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:Path">Path</a> a</li><li class="src short"><a href="#v:empty">empty</a> :: <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:cons">cons</a> :: <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> -&gt; a -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:uncons">uncons</a> :: <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Maybe.html#t:Maybe">Maybe</a> (<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a>, a, <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a)</li><li class="src short"><a href="#v:view">view</a> :: <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-View.html#t:View">View</a> <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:null">null</a> :: <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Bool.html#t:Bool">Bool</a></li><li class="src short"><a href="#v:length">length</a> :: <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a></li><li class="src short"><a href="#v:isAncestorOf">isAncestorOf</a> :: <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> b -&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Bool.html#t:Bool">Bool</a></li><li class="src short"><a href="#v:lca">lca</a> :: <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> b -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:keep">keep</a> :: <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:drop">drop</a> :: <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:traverseWithKey">traverseWithKey</a> :: <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Control-Applicative.html#t:Applicative">Applicative</a> f =&gt; (<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> -&gt; a -&gt; f b) -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; f (<a href="Data-LCA-Online-Naive.html#t:Path">Path</a> b)</li><li class="src short"><a href="#v:toList">toList</a> :: <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; [(<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a>, a)]</li><li class="src short"><a href="#v:fromList">fromList</a> :: [(<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a>, a)] -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:-126--61-">(~=)</a> :: <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> b -&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Bool.html#t:Bool">Bool</a></li></ul></div><div id="interface"><h1>Documentation</h1><div class="top"><p class="src"><span class="keyword">data</span> <a name="t:Path" class="def">Path</a> a <a href="src/Data-LCA-Online-Naive.html#Path" class="link">Source</a></p><div class="doc"><p>An uncompressed <code><a href="Data-LCA-Online-Naive.html#t:Path">Path</a></code> with memoized length.</p></div><div class="subs instances"><p id="control.i:Path" class="caption collapser" onclick="toggleSection('i:Path')">Instances</p><div id="section.i:Path" class="show"><table><tr><td class="src"><a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Control-Monad.html#t:Functor">Functor</a> <a href="Data-LCA-Online-Naive.html#t:Path">Path</a></td><td class="doc empty">&nbsp;</td></tr><tr><td class="src"><a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Foldable.html#t:Foldable">Foldable</a> <a href="Data-LCA-Online-Naive.html#t:Path">Path</a></td><td class="doc empty">&nbsp;</td></tr><tr><td class="src"><a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Traversable.html#t:Traversable">Traversable</a> <a href="Data-LCA-Online-Naive.html#t:Path">Path</a></td><td class="doc empty">&nbsp;</td></tr><tr><td class="src"><a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Text-Read.html#t:Read">Read</a> a =&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Text-Read.html#t:Read">Read</a> (<a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a)</td><td class="doc empty">&nbsp;</td></tr><tr><td class="src"><a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Text-Show.html#t:Show">Show</a> a =&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Text-Show.html#t:Show">Show</a> (<a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a)</td><td class="doc empty">&nbsp;</td></tr></table></div></div></div><div class="top"><p class="src"><a name="v:empty" class="def">empty</a> :: <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a <a href="src/Data-LCA-Online-Naive.html#empty" class="link">Source</a></p><div class="doc"><p>The empty <code><a href="Data-LCA-Online-Naive.html#t:Path">Path</a></code></p></div></div><div class="top"><p class="src"><a name="v:cons" class="def">cons</a> :: <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> -&gt; a -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a <a href="src/Data-LCA-Online-Naive.html#cons" class="link">Source</a></p><div class="doc"><p><em>O(1)</em> Invariant: most operations assume that the keys <code>k</code> are globally unique</p><p>Extend the path with a new node ID and value.</p></div></div><div class="top"><p class="src"><a name="v:uncons" class="def">uncons</a> :: <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Maybe.html#t:Maybe">Maybe</a> (<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a>, a, <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a) <a href="src/Data-LCA-Online-Naive.html#uncons" class="link">Source</a></p><div class="doc"><p><em>O(1)</em> Extract the node ID and value from the newest node on the <code><a href="Data-LCA-Online-Naive.html#t:Path">Path</a></code>.</p></div></div><div class="top"><p class="src"><a name="v:view" class="def">view</a> :: <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-View.html#t:View">View</a> <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a <a href="src/Data-LCA-Online-Naive.html#view" class="link">Source</a></p><div class="doc"><p><em>O(1)</em> Extract the node ID and value from the newest node on the <code><a href="Data-LCA-Online-Naive.html#t:Path">Path</a></code>, slightly faster than <code><a href="Data-LCA-Online-Naive.html#v:uncons">uncons</a></code>.</p></div></div><div class="top"><p class="src"><a name="v:null" class="def">null</a> :: <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Bool.html#t:Bool">Bool</a> <a href="src/Data-LCA-Online-Naive.html#null" class="link">Source</a></p><div class="doc"><p><em>O(1)</em> Returns <code><a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Bool.html#v:True">True</a></code> iff the <code><a href="Data-LCA-Online-Naive.html#t:Path">Path</a></code> is <code><a href="Data-LCA-Online-Naive.html#v:empty">empty</a></code>.</p></div></div><div class="top"><p class="src"><a name="v:length" class="def">length</a> :: <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> <a href="src/Data-LCA-Online-Naive.html#length" class="link">Source</a></p><div class="doc"><p><em>O(1)</em> Determine the length of a <code><a href="Data-LCA-Online-Naive.html#t:Path">Path</a></code>.</p></div></div><div class="top"><p class="src"><a name="v:isAncestorOf" class="def">isAncestorOf</a> :: <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> b -&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Bool.html#t:Bool">Bool</a> <a href="src/Data-LCA-Online-Naive.html#isAncestorOf" class="link">Source</a></p><div class="doc"><p><em>O(h)</em> <code>xs <code><a href="Data-LCA-Online-Naive.html#v:isAncestorOf">isAncestorOf</a></code> ys</code> holds when <code>xs</code> is a prefix starting at the root of <code><a href="Data-LCA-Online-Naive.html#t:Path">Path</a></code> <code>ys</code>.</p></div></div><div class="top"><p class="src"><a name="v:lca" class="def">lca</a> :: <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> b -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a <a href="src/Data-LCA-Online-Naive.html#lca" class="link">Source</a></p><div class="doc"><p><em>O(h)</em> Compute the lowest common ancestor of two paths</p></div></div><div class="top"><p class="src"><a name="v:keep" class="def">keep</a> :: <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a <a href="src/Data-LCA-Online-Naive.html#keep" class="link">Source</a></p><div class="doc"><p><em>O(h - k)</em> to <code><code><a href="Data-LCA-Online-Naive.html#v:keep">keep</a></code> k</code> elements of <code><a href="Data-LCA-Online-Naive.html#t:Path">Path</a></code> of <code><a href="Data-LCA-Online-Naive.html#v:length">length</a></code> <code>h</code></p></div></div><div class="top"><p class="src"><a name="v:drop" class="def">drop</a> :: <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a <a href="src/Data-LCA-Online-Naive.html#drop" class="link">Source</a></p><div class="doc"><p><em>O(k)</em> to <code><code><a href="Data-LCA-Online-Naive.html#v:drop">drop</a></code> k</code> elements from a <code><a href="Data-LCA-Online-Naive.html#t:Path">Path</a></code></p></div></div><div class="top"><p class="src"><a name="v:traverseWithKey" class="def">traverseWithKey</a> :: <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Control-Applicative.html#t:Applicative">Applicative</a> f =&gt; (<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> -&gt; a -&gt; f b) -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; f (<a href="Data-LCA-Online-Naive.html#t:Path">Path</a> b) <a href="src/Data-LCA-Online-Naive.html#traverseWithKey" class="link">Source</a></p><div class="doc"><p>Traverse a <code><a href="Data-LCA-Online-Naive.html#t:Path">Path</a></code> with access to the node IDs.</p></div></div><div class="top"><p class="src"><a name="v:toList" class="def">toList</a> :: <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; [(<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a>, a)] <a href="src/Data-LCA-Online-Naive.html#toList" class="link">Source</a></p><div class="doc"><p>Convert a <code><a href="Data-LCA-Online-Naive.html#t:Path">Path</a></code> to a list of <code>(ID, value)</code> pairs.</p></div></div><div class="top"><p class="src"><a name="v:fromList" class="def">fromList</a> :: [(<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a>, a)] -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a <a href="src/Data-LCA-Online-Naive.html#fromList" class="link">Source</a></p><div class="doc"><p>Build a <code><a href="Data-LCA-Online-Naive.html#t:Path">Path</a></code> from a list of <code>(ID, value)</code> pairs.</p></div></div><div class="top"><p class="src"><a name="v:-126--61-" class="def">(~=)</a> :: <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online-Naive.html#t:Path">Path</a> b -&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Bool.html#t:Bool">Bool</a> <span class="fixity">infix 4</span><span class="rightedge"></span> <a href="src/Data-LCA-Online-Naive.html#~%3D" class="link">Source</a></p><div class="doc"><p><em>O(1)</em> Compare to see if two trees have the same leaf key</p></div></div></div></div><div id="footer"><p>Produced by <a href="http://www.haskell.org/haddock/">Haddock</a> version 2.15.1</p></div></body></html>
View
34 Data-LCA-Online.html
@@ -1,34 +1,8 @@
<!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.LCA.Online</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-LCA-Online.html");};
//]]>
-</script></head><body><div id="package-header"><ul class="links" id="page-menu"><li><a href="src/Data-LCA-Online.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">lca-0.2.4: O(log n) persistent on-line lowest common ancestor calculation without preprocessing</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>Edward Kmett &lt;ekmett@gmail.com&gt;</td></tr><tr><th>Safe Haskell</th><td>Safe-Inferred</td></tr></table><p class="caption">Data.LCA.Online</p></div><div id="description"><p class="caption">Description</p><div class="doc"><p>Provides online calculation of the the lowest common ancestor in <em>O(log h)</em>
+</script></head><body><div id="package-header"><ul class="links" id="page-menu"><li><a href="src/Data-LCA-Online.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">lca-0.3: O(log n) persistent on-line lowest common ancestor calculation without preprocessing</p></div><div id="content"><div id="module-header"><table class="info"><tr><th>Copyright</th><td>(C) 2011-2015 Edward Kmett</td></tr><tr><th>License</th><td>BSD-style (see the file LICENSE)</td></tr><tr><th>Maintainer</th><td>Edward Kmett &lt;ekmett@gmail.com&gt;</td></tr><tr><th>Stability</th><td>experimental</td></tr><tr><th>Portability</th><td>portable</td></tr><tr><th>Safe Haskell</th><td>Safe-Inferred</td></tr><tr><th>Language</th><td>Haskell98</td></tr></table><p class="caption">Data.LCA.Online</p></div><div id="description"><p class="caption">Description</p><div class="doc"><p>Provides online calculation of the the lowest common ancestor in <em>O(log h)</em>
by compressing the spine of a <code><a href="Data-LCA-Online.html#t:Path">Path</a></code> using a skew-binary random access
- list.
-</p><p>This library implements the technique described in my talk
-</p><p><a href="http://www.slideshare.net/ekmett/skewbinary-online-lowest-common-ancestor-search">http://www.slideshare.net/ekmett/skewbinary-online-lowest-common-ancestor-search</a>
-</p><p>to improve the known asymptotic bounds on both online lowest common ancestor search
-</p><p><a href="http://en.wikipedia.org/wiki/Lowest_common_ancestor">http://en.wikipedia.org/wiki/Lowest_common_ancestor</a>
-</p><p>and the online level ancestor problem:
-</p><p><a href="http://en.wikipedia.org/wiki/Level_ancestor_problem">http://en.wikipedia.org/wiki/Level_ancestor_problem</a>
-</p><p>Algorithms used here assume that the key values chosen for <code>k</code> are
- globally unique.
-</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:Path">Path</a> a</li><li class="src short"><a href="#v:lca">lca</a> :: <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> b -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:empty">empty</a> :: <a href="Data-LCA-Online.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:cons">cons</a> :: <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a> -&gt; a -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:uncons">uncons</a> :: <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Maybe.html#t:Maybe">Maybe</a> (<a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a>, a, <a href="Data-LCA-Online.html#t:Path">Path</a> a)</li><li class="src short"><a href="#v:view">view</a> :: <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-View.html#t:View">View</a> <a href="Data-LCA-Online.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:null">null</a> :: <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Bool.html#t:Bool">Bool</a></li><li class="src short"><a href="#v:length">length</a> :: <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a></li><li class="src short"><a href="#v:isAncestorOf">isAncestorOf</a> :: <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> b -&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Bool.html#t:Bool">Bool</a></li><li class="src short"><a href="#v:keep">keep</a> :: <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a> -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:drop">drop</a> :: <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a> -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:traverseWithKey">traverseWithKey</a> :: <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Control-Applicative.html#t:Applicative">Applicative</a> f =&gt; (<a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a> -&gt; a -&gt; f b) -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; f (<a href="Data-LCA-Online.html#t:Path">Path</a> b)</li><li class="src short"><a href="#v:toList">toList</a> :: <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; [(<a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a>, a)]</li><li class="src short"><a href="#v:fromList">fromList</a> :: [(<a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a>, a)] -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:-126--61-">(~=)</a> :: <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> b -&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Bool.html#t:Bool">Bool</a></li></ul></div><div id="interface"><h1>Documentation</h1><div class="top"><p class="src"><span class="keyword">data</span> <a name="t:Path" class="def">Path</a> a <a href="src/Data-LCA-Online.html#Path" class="link">Source</a></p><div class="doc"><p>Compressed paths using skew binary random access lists
-</p></div><div class="subs instances"><p id="control.i:Path" class="caption collapser" onclick="toggleSection('i:Path')">Instances</p><div id="section.i:Path" class="show"><table><tr><td class="src"><a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Control-Monad.html#t:Functor">Functor</a> <a href="Data-LCA-Online.html#t:Path">Path</a></td><td class="doc empty">&nbsp;</td></tr><tr><td class="src"><a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Foldable.html#t:Foldable">Foldable</a> <a href="Data-LCA-Online.html#t:Path">Path</a></td><td class="doc empty">&nbsp;</td></tr><tr><td class="src"><a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Traversable.html#t:Traversable">Traversable</a> <a href="Data-LCA-Online.html#t:Path">Path</a></td><td class="doc empty">&nbsp;</td></tr><tr><td class="src"><a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Text-Read.html#t:Read">Read</a> a =&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Text-Read.html#t:Read">Read</a> (<a href="Data-LCA-Online.html#t:Path">Path</a> a)</td><td class="doc empty">&nbsp;</td></tr><tr><td class="src"><a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Text-Show.html#t:Show">Show</a> a =&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Text-Show.html#t:Show">Show</a> (<a href="Data-LCA-Online.html#t:Path">Path</a> a)</td><td class="doc empty">&nbsp;</td></tr></table></div></div></div><div class="top"><p class="src"><a name="v:lca" class="def">lca</a> :: <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> b -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> a<a href="src/Data-LCA-Online.html#lca" class="link">Source</a></p><div class="doc"><p><em>O(log h)</em> Compute the lowest common ancestor of two paths.
-</p></div></div><div class="top"><p class="src"><a name="v:empty" class="def">empty</a> :: <a href="Data-LCA-Online.html#t:Path">Path</a> a<a href="src/Data-LCA-Online.html#empty" class="link">Source</a></p><div class="doc"><p>The <code><a href="Data-LCA-Online.html#v:empty">empty</a></code> <code><a href="Data-LCA-Online.html#t:Path">Path</a></code>
-</p></div></div><div class="top"><p class="src"><a name="v:cons" class="def">cons</a> :: <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a> -&gt; a -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> a<a href="src/Data-LCA-Online.html#cons" class="link">Source</a></p><div class="doc"><p><em>O(1)</em> Invariant: most operations assume that the keys <code>k</code> are globally unique
-</p><p>Extend the <code><a href="Data-LCA-Online.html#t:Path">Path</a></code> with a new node ID and value.
-</p></div></div><div class="top"><p class="src"><a name="v:uncons" class="def">uncons</a> :: <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Maybe.html#t:Maybe">Maybe</a> (<a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a>, a, <a href="Data-LCA-Online.html#t:Path">Path</a> a)<a href="src/Data-LCA-Online.html#uncons" class="link">Source</a></p><div class="doc"><p><em>O(1)</em> Extract the node ID and value from the newest node on the <code><a href="Data-LCA-Online.html#t:Path">Path</a></code>.
-</p></div></div><div class="top"><p class="src"><a name="v:view" class="def">view</a> :: <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-View.html#t:View">View</a> <a href="Data-LCA-Online.html#t:Path">Path</a> a<a href="src/Data-LCA-Online.html#view" class="link">Source</a></p><div class="doc"><p><em>O(1)</em> Extract the node ID and value from the newest node on the <code><a href="Data-LCA-Online.html#t:Path">Path</a></code>, slightly faster than <code><a href="Data-LCA-Online.html#v:uncons">uncons</a></code>.
-</p></div></div><div class="top"><p class="src"><a name="v:null" class="def">null</a> :: <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Bool.html#t:Bool">Bool</a><a href="src/Data-LCA-Online.html#null" class="link">Source</a></p><div class="doc"><p><em>O(1)</em> Returns <code><a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Bool.html#v:True">True</a></code> iff the path is <code><a href="Data-LCA-Online.html#v:empty">empty</a></code>.
-</p></div></div><div class="top"><p class="src"><a name="v:length" class="def">length</a> :: <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a><a href="src/Data-LCA-Online.html#length" class="link">Source</a></p><div class="doc"><p><em>O(1)</em> Determine the <code><a href="Data-LCA-Online.html#v:length">length</a></code> of a <code><a href="Data-LCA-Online.html#t:Path">Path</a></code>.
-</p></div></div><div class="top"><p class="src"><a name="v:isAncestorOf" class="def">isAncestorOf</a> :: <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> b -&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Bool.html#t:Bool">Bool</a><a href="src/Data-LCA-Online.html#isAncestorOf" class="link">Source</a></p><div class="doc"><p><em>O(log h)</em> <code>xs <code><a href="Data-LCA-Online.html#v:isAncestorOf">isAncestorOf</a></code> ys</code> holds when <code>xs</code> is a prefix starting at the root of <code><a href="Data-LCA-Online.html#t:Path">Path</a></code> <code>ys</code>.
-</p></div></div><div class="top"><p class="src"><a name="v:keep" class="def">keep</a> :: <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a> -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> a<a href="src/Data-LCA-Online.html#keep" class="link">Source</a></p><div class="doc"><p><em>O(log (h - k))</em> to <code><code><a href="Data-LCA-Online.html#v:keep">keep</a></code> k</code> elements of <code><a href="Data-LCA-Online.html#t:Path">Path</a></code> of <code><a href="Data-LCA-Online.html#v:length">length</a></code> <code>h</code>
-</p><p>This solves the online version of the &quot;level ancestor problem&quot; with no preprocessing in <em>O(log h)</em> time,
- improving known complexity bounds.
-</p><p><a href="http://en.wikipedia.org/wiki/Level_ancestor_problem">http://en.wikipedia.org/wiki/Level_ancestor_problem</a>
-</p></div></div><div class="top"><p class="src"><a name="v:drop" class="def">drop</a> :: <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a> -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> a<a href="src/Data-LCA-Online.html#drop" class="link">Source</a></p><div class="doc"><p><em>O(log k)</em> to <code><code><a href="Data-LCA-Online.html#v:drop">drop</a></code> k</code> elements from a <code><a href="Data-LCA-Online.html#t:Path">Path</a></code>
-</p></div></div><div class="top"><p class="src"><a name="v:traverseWithKey" class="def">traverseWithKey</a> :: <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Control-Applicative.html#t:Applicative">Applicative</a> f =&gt; (<a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a> -&gt; a -&gt; f b) -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; f (<a href="Data-LCA-Online.html#t:Path">Path</a> b)<a href="src/Data-LCA-Online.html#traverseWithKey" class="link">Source</a></p><div class="doc"><p>Traverse a <code><a href="Data-LCA-Online.html#t:Path">Path</a></code> with access to the node IDs.
-</p></div></div><div class="top"><p class="src"><a name="v:toList" class="def">toList</a> :: <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; [(<a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a>, a)]<a href="src/Data-LCA-Online.html#toList" class="link">Source</a></p><div class="doc"><p>Convert a <code><a href="Data-LCA-Online.html#t:Path">Path</a></code> to a list of <code>(ID, value)</code> pairs.
-</p></div></div><div class="top"><p class="src"><a name="v:fromList" class="def">fromList</a> :: [(<a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a>, a)] -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> a<a href="src/Data-LCA-Online.html#fromList" class="link">Source</a></p><div class="doc"><p>Build a <code><a href="Data-LCA-Online.html#t:Path">Path</a></code> from a list of <code>(ID, value)</code> pairs.
-</p></div></div><div class="top"><p class="src"><a name="v:-126--61-" class="def">(~=)</a> :: <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> b -&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Bool.html#t:Bool">Bool</a><a href="src/Data-LCA-Online.html#~%3D" class="link">Source</a></p><div class="doc"><p><em>O(1)</em> Compare to see if two trees have the same leaf key
-</p></div></div></div></div><div id="footer"><p>Produced by <a href="http://www.haskell.org/haddock/">Haddock</a> version 2.13.2</p></div></body></html>
+ list.</p><p>This library implements the technique described in my talk</p><p><a href="http://www.slideshare.net/ekmett/skewbinary-online-lowest-common-ancestor-search">http://www.slideshare.net/ekmett/skewbinary-online-lowest-common-ancestor-search</a></p><p>to improve the known asymptotic bounds on both online lowest common ancestor search</p><p><a href="http://en.wikipedia.org/wiki/Lowest_common_ancestor">http://en.wikipedia.org/wiki/Lowest_common_ancestor</a></p><p>and the online level ancestor problem:</p><p><a href="http://en.wikipedia.org/wiki/Level_ancestor_problem">http://en.wikipedia.org/wiki/Level_ancestor_problem</a></p><p>Algorithms used here assume that the key values chosen for <code>k</code> are
+ globally unique.</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:Path">Path</a> a</li><li class="src short"><a href="#v:lca">lca</a> :: <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> b -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:empty">empty</a> :: <a href="Data-LCA-Online.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:cons">cons</a> :: <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> -&gt; a -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:uncons">uncons</a> :: <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Maybe.html#t:Maybe">Maybe</a> (<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a>, a, <a href="Data-LCA-Online.html#t:Path">Path</a> a)</li><li class="src short"><a href="#v:view">view</a> :: <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-View.html#t:View">View</a> <a href="Data-LCA-Online.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:null">null</a> :: <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Bool.html#t:Bool">Bool</a></li><li class="src short"><a href="#v:length">length</a> :: <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a></li><li class="src short"><a href="#v:isAncestorOf">isAncestorOf</a> :: <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> b -&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Bool.html#t:Bool">Bool</a></li><li class="src short"><a href="#v:keep">keep</a> :: <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:drop">drop</a> :: <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:traverseWithKey">traverseWithKey</a> :: <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Control-Applicative.html#t:Applicative">Applicative</a> f =&gt; (<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> -&gt; a -&gt; f b) -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; f (<a href="Data-LCA-Online.html#t:Path">Path</a> b)</li><li class="src short"><a href="#v:toList">toList</a> :: <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; [(<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a>, a)]</li><li class="src short"><a href="#v:fromList">fromList</a> :: [(<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a>, a)] -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> a</li><li class="src short"><a href="#v:-126--61-">(~=)</a> :: <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> b -&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Bool.html#t:Bool">Bool</a></li></ul></div><div id="interface"><h1>Documentation</h1><div class="top"><p class="src"><span class="keyword">data</span> <a name="t:Path" class="def">Path</a> a <a href="src/Data-LCA-Online.html#Path" class="link">Source</a></p><div class="doc"><p>Compressed paths using skew binary random access lists</p></div><div class="subs instances"><p id="control.i:Path" class="caption collapser" onclick="toggleSection('i:Path')">Instances</p><div id="section.i:Path" class="show"><table><tr><td class="src"><a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Control-Monad.html#t:Functor">Functor</a> <a href="Data-LCA-Online.html#t:Path">Path</a></td><td class="doc empty">&nbsp;</td></tr><tr><td class="src"><a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Foldable.html#t:Foldable">Foldable</a> <a href="Data-LCA-Online.html#t:Path">Path</a></td><td class="doc empty">&nbsp;</td></tr><tr><td class="src"><a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Traversable.html#t:Traversable">Traversable</a> <a href="Data-LCA-Online.html#t:Path">Path</a></td><td class="doc empty">&nbsp;</td></tr><tr><td class="src"><a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Text-Read.html#t:Read">Read</a> a =&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Text-Read.html#t:Read">Read</a> (<a href="Data-LCA-Online.html#t:Path">Path</a> a)</td><td class="doc empty">&nbsp;</td></tr><tr><td class="src"><a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Text-Show.html#t:Show">Show</a> a =&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Text-Show.html#t:Show">Show</a> (<a href="Data-LCA-Online.html#t:Path">Path</a> a)</td><td class="doc empty">&nbsp;</td></tr></table></div></div></div><div class="top"><p class="src"><a name="v:lca" class="def">lca</a> :: <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> b -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> a <a href="src/Data-LCA-Online.html#lca" class="link">Source</a></p><div class="doc"><p><em>O(log h)</em> Compute the lowest common ancestor of two paths.</p></div></div><div class="top"><p class="src"><a name="v:empty" class="def">empty</a> :: <a href="Data-LCA-Online.html#t:Path">Path</a> a <a href="src/Data-LCA-Online.html#empty" class="link">Source</a></p><div class="doc"><p>The <code><a href="Data-LCA-Online.html#v:empty">empty</a></code> <code><a href="Data-LCA-Online.html#t:Path">Path</a></code></p></div></div><div class="top"><p class="src"><a name="v:cons" class="def">cons</a> :: <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> -&gt; a -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> a <a href="src/Data-LCA-Online.html#cons" class="link">Source</a></p><div class="doc"><p><em>O(1)</em> Invariant: most operations assume that the keys <code>k</code> are globally unique</p><p>Extend the <code><a href="Data-LCA-Online.html#t:Path">Path</a></code> with a new node ID and value.</p></div></div><div class="top"><p class="src"><a name="v:uncons" class="def">uncons</a> :: <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Maybe.html#t:Maybe">Maybe</a> (<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a>, a, <a href="Data-LCA-Online.html#t:Path">Path</a> a) <a href="src/Data-LCA-Online.html#uncons" class="link">Source</a></p><div class="doc"><p><em>O(1)</em> Extract the node ID and value from the newest node on the <code><a href="Data-LCA-Online.html#t:Path">Path</a></code>.</p></div></div><div class="top"><p class="src"><a name="v:view" class="def">view</a> :: <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-View.html#t:View">View</a> <a href="Data-LCA-Online.html#t:Path">Path</a> a <a href="src/Data-LCA-Online.html#view" class="link">Source</a></p><div class="doc"><p><em>O(1)</em> Extract the node ID and value from the newest node on the <code><a href="Data-LCA-Online.html#t:Path">Path</a></code>, slightly faster than <code><a href="Data-LCA-Online.html#v:uncons">uncons</a></code>.</p></div></div><div class="top"><p class="src"><a name="v:null" class="def">null</a> :: <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Bool.html#t:Bool">Bool</a> <a href="src/Data-LCA-Online.html#null" class="link">Source</a></p><div class="doc"><p><em>O(1)</em> Returns <code><a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Bool.html#v:True">True</a></code> iff the path is <code><a href="Data-LCA-Online.html#v:empty">empty</a></code>.</p></div></div><div class="top"><p class="src"><a name="v:length" class="def">length</a> :: <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> <a href="src/Data-LCA-Online.html#length" class="link">Source</a></p><div class="doc"><p><em>O(1)</em> Determine the <code><a href="Data-LCA-Online.html#v:length">length</a></code> of a <code><a href="Data-LCA-Online.html#t:Path">Path</a></code>.</p></div></div><div class="top"><p class="src"><a name="v:isAncestorOf" class="def">isAncestorOf</a> :: <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> b -&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Bool.html#t:Bool">Bool</a> <a href="src/Data-LCA-Online.html#isAncestorOf" class="link">Source</a></p><div class="doc"><p><em>O(log h)</em> <code>xs <code><a href="Data-LCA-Online.html#v:isAncestorOf">isAncestorOf</a></code> ys</code> holds when <code>xs</code> is a prefix starting at the root of <code><a href="Data-LCA-Online.html#t:Path">Path</a></code> <code>ys</code>.</p></div></div><div class="top"><p class="src"><a name="v:keep" class="def">keep</a> :: <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> a <a href="src/Data-LCA-Online.html#keep" class="link">Source</a></p><div class="doc"><p><em>O(log (h - k))</em> to <code><code><a href="Data-LCA-Online.html#v:keep">keep</a></code> k</code> elements of <code><a href="Data-LCA-Online.html#t:Path">Path</a></code> of <code><a href="Data-LCA-Online.html#v:length">length</a></code> <code>h</code></p><p>This solves the online version of the &quot;level ancestor problem&quot; with no preprocessing in <em>O(log h)</em> time,
+ improving known complexity bounds.</p><p><a href="http://en.wikipedia.org/wiki/Level_ancestor_problem">http://en.wikipedia.org/wiki/Level_ancestor_problem</a></p></div></div><div class="top"><p class="src"><a name="v:drop" class="def">drop</a> :: <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> a <a href="src/Data-LCA-Online.html#drop" class="link">Source</a></p><div class="doc"><p><em>O(log k)</em> to <code><code><a href="Data-LCA-Online.html#v:drop">drop</a></code> k</code> elements from a <code><a href="Data-LCA-Online.html#t:Path">Path</a></code></p></div></div><div class="top"><p class="src"><a name="v:traverseWithKey" class="def">traverseWithKey</a> :: <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Control-Applicative.html#t:Applicative">Applicative</a> f =&gt; (<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> -&gt; a -&gt; f b) -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; f (<a href="Data-LCA-Online.html#t:Path">Path</a> b) <a href="src/Data-LCA-Online.html#traverseWithKey" class="link">Source</a></p><div class="doc"><p>Traverse a <code><a href="Data-LCA-Online.html#t:Path">Path</a></code> with access to the node IDs.</p></div></div><div class="top"><p class="src"><a name="v:toList" class="def">toList</a> :: <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; [(<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a>, a)] <a href="src/Data-LCA-Online.html#toList" class="link">Source</a></p><div class="doc"><p>Convert a <code><a href="Data-LCA-Online.html#t:Path">Path</a></code> to a list of <code>(ID, value)</code> pairs.</p></div></div><div class="top"><p class="src"><a name="v:fromList" class="def">fromList</a> :: [(<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a>, a)] -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> a <a href="src/Data-LCA-Online.html#fromList" class="link">Source</a></p><div class="doc"><p>Build a <code><a href="Data-LCA-Online.html#t:Path">Path</a></code> from a list of <code>(ID, value)</code> pairs.</p></div></div><div class="top"><p class="src"><a name="v:-126--61-" class="def">(~=)</a> :: <a href="Data-LCA-Online.html#t:Path">Path</a> a -&gt; <a href="Data-LCA-Online.html#t:Path">Path</a> b -&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Bool.html#t:Bool">Bool</a> <span class="fixity">infix 4</span><span class="rightedge"></span> <a href="src/Data-LCA-Online.html#~%3D" class="link">Source</a></p><div class="doc"><p><em>O(1)</em> Compare to see if two trees have the same leaf key</p></div></div></div></div><div id="footer"><p>Produced by <a href="http://www.haskell.org/haddock/">Haddock</a> version 2.15.1</p></div></body></html>
View
3  Data-LCA-View.html
@@ -1,5 +1,4 @@
<!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.LCA.View</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-LCA-View.html");};
//]]>
-</script></head><body><div id="package-header"><ul class="links" id="page-menu"><li><a href="src/Data-LCA-View.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">lca-0.2.4: O(log n) persistent on-line lowest common ancestor calculation without preprocessing</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>provisional</td></tr><tr><th>Maintainer</th><td>Edward Kmett &lt;ekmett@gmail.com&gt;</td></tr><tr><th>Safe Haskell</th><td>Safe-Inferred</td></tr></table><p class="caption">Data.LCA.View</p></div><div id="description"><p class="caption">Description</p><div class="doc empty">&nbsp;</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:View">View</a> f a<ul class="subs"><li>= <a href="#v:Root">Root</a> </li><li>| <a href="#v:Node">Node</a> !<a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a> a (f a) </li></ul></li></ul></div><div id="interface"><h1>Documentation</h1><div class="top"><p class="src"><span class="keyword">data</span> <a name="t:View" class="def">View</a> f a <a href="src/Data-LCA-View.html#View" class="link">Source</a></p><div class="doc"><p>Provides a consistent <code><a href="Data-LCA-View.html#t:View">View</a></code> for peeling off the bottom node of a path.
-</p></div><div class="subs constructors"><p class="caption">Constructors</p><table><tr><td class="src"><a name="v:Root" class="def">Root</a></td><td class="doc empty">&nbsp;</td></tr><tr><td class="src"><a name="v:Node" class="def">Node</a> !<a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a> a (f a)</td><td class="doc empty">&nbsp;</td></tr></table></div><div class="subs instances"><p id="control.i:View" class="caption collapser" onclick="toggleSection('i:View')">Instances</p><div id="section.i:View" class="show"><table><tr><td class="src"><a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Control-Monad.html#t:Functor">Functor</a> f =&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Control-Monad.html#t:Functor">Functor</a> (<a href="Data-LCA-View.html#t:View">View</a> f)</td><td class="doc empty">&nbsp;</td></tr><tr><td class="src"><a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Foldable.html#t:Foldable">Foldable</a> f =&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Foldable.html#t:Foldable">Foldable</a> (<a href="Data-LCA-View.html#t:View">View</a> f)</td><td class="doc empty">&nbsp;</td></tr><tr><td class="src"><a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Traversable.html#t:Traversable">Traversable</a> f =&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Traversable.html#t:Traversable">Traversable</a> (<a href="Data-LCA-View.html#t:View">View</a> f)</td><td class="doc empty">&nbsp;</td></tr><tr><td class="src">(<a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Eq.html#t:Eq">Eq</a> a, <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Eq.html#t:Eq">Eq</a> (f a)) =&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Eq.html#t:Eq">Eq</a> (<a href="Data-LCA-View.html#t:View">View</a> f a)</td><td class="doc empty">&nbsp;</td></tr><tr><td class="src">(<a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> a, <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> (f a)) =&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Data-Ord.html#t:Ord">Ord</a> (<a href="Data-LCA-View.html#t:View">View</a> f a)</td><td class="doc empty">&nbsp;</td></tr><tr><td class="src">(<a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Text-Read.html#t:Read">Read</a> a, <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Text-Read.html#t:Read">Read</a> (f a)) =&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Text-Read.html#t:Read">Read</a> (<a href="Data-LCA-View.html#t:View">View</a> f a)</td><td class="doc empty">&nbsp;</td></tr><tr><td class="src">(<a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Text-Show.html#t:Show">Show</a> a, <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Text-Show.html#t:Show">Show</a> (f a)) =&gt; <a href="/usr/local/share/doc/ghc/html/libraries/base-4.6.0.1/Text-Show.html#t:Show">Show</a> (<a href="Data-LCA-View.html#t:View">View</a> f a)</td><td class="doc empty">&nbsp;</td></tr></table></div></div></div></div></div><div id="footer"><p>Produced by <a href="http://www.haskell.org/haddock/">Haddock</a> version 2.13.2</p></div></body></html>
+</script></head><body><div id="package-header"><ul class="links" id="page-menu"><li><a href="src/Data-LCA-View.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">lca-0.3: O(log n) persistent on-line lowest common ancestor calculation without preprocessing</p></div><div id="content"><div id="module-header"><table class="info"><tr><th>Copyright</th><td>(C) 2012-2015 Edward Kmett</td></tr><tr><th>License</th><td>BSD-style (see the file LICENSE)</td></tr><tr><th>Maintainer</th><td>Edward Kmett &lt;ekmett@gmail.com&gt;</td></tr><tr><th>Stability</th><td>provisional</td></tr><tr><th>Portability</th><td>portable</td></tr><tr><th>Safe Haskell</th><td>Safe-Inferred</td></tr><tr><th>Language</th><td>Haskell98</td></tr></table><p class="caption">Data.LCA.View</p></div><div id="description"><p class="caption">Description</p><div class="doc empty">&nbsp;</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:View">View</a> f a<ul class="subs"><li>= <a href="#v:Root">Root</a></li><li>| <a href="#v:Node">Node</a> !<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> a (f a)</li></ul></li></ul></div><div id="interface"><h1>Documentation</h1><div class="top"><p class="src"><span class="keyword">data</span> <a name="t:View" class="def">View</a> f a <a href="src/Data-LCA-View.html#View" class="link">Source</a></p><div class="doc"><p>Provides a consistent <code><a href="Data-LCA-View.html#t:View">View</a></code> for peeling off the bottom node of a path.</p></div><div class="subs constructors"><p class="caption">Constructors</p><table><tr><td class="src"><a name="v:Root" class="def">Root</a></td><td class="doc empty">&nbsp;</td></tr><tr><td class="src"><a name="v:Node" class="def">Node</a> !<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> a (f a)</td><td class="doc empty">&nbsp;</td></tr></table></div><div class="subs instances"><p id="control.i:View" class="caption collapser" onclick="toggleSection('i:View')">Instances</p><div id="section.i:View" class="show"><table><tr><td class="src"><a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Control-Monad.html#t:Functor">Functor</a> f =&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Control-Monad.html#t:Functor">Functor</a> (<a href="Data-LCA-View.html#t:View">View</a> f)</td><td class="doc empty">&nbsp;</td></tr><tr><td class="src"><a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Foldable.html#t:Foldable">Foldable</a> f =&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Foldable.html#t:Foldable">Foldable</a> (<a href="Data-LCA-View.html#t:View">View</a> f)</td><td class="doc empty">&nbsp;</td></tr><tr><td class="src"><a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Traversable.html#t:Traversable">Traversable</a> f =&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Traversable.html#t:Traversable">Traversable</a> (<a href="Data-LCA-View.html#t:View">View</a> f)</td><td class="doc empty">&nbsp;</td></tr><tr><td class="src">(<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Eq.html#t:Eq">Eq</a> a, <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Eq.html#t:Eq">Eq</a> (f a)) =&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Eq.html#t:Eq">Eq</a> (<a href="Data-LCA-View.html#t:View">View</a> f a)</td><td class="doc empty">&nbsp;</td></tr><tr><td class="src">(<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Ord.html#t:Ord">Ord</a> a, <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Ord.html#t:Ord">Ord</a> (f a)) =&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Ord.html#t:Ord">Ord</a> (<a href="Data-LCA-View.html#t:View">View</a> f a)</td><td class="doc empty">&nbsp;</td></tr><tr><td class="src">(<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Text-Read.html#t:Read">Read</a> a, <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Text-Read.html#t:Read">Read</a> (f a)) =&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Text-Read.html#t:Read">Read</a> (<a href="Data-LCA-View.html#t:View">View</a> f a)</td><td class="doc empty">&nbsp;</td></tr><tr><td class="src">(<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Text-Show.html#t:Show">Show</a> a, <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Text-Show.html#t:Show">Show</a> (f a)) =&gt; <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Text-Show.html#t:Show">Show</a> (<a href="Data-LCA-View.html#t:View">View</a> f a)</td><td class="doc empty">&nbsp;</td></tr></table></div></div></div></div></div><div id="footer"><p>Produced by <a href="http://www.haskell.org/haddock/">Haddock</a> version 2.15.1</p></div></body></html>
View
4 doc-index.html
@@ -1,4 +1,4 @@
-<!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>lca-0.2.4: O(log n) persistent on-line lowest common ancestor calculation without preprocessing (Index)</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[
+<!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>lca-0.3: O(log n) persistent on-line lowest common ancestor calculation without preprocessing (Index)</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();};
//]]>
-</script></head><body><div id="package-header"><ul class="links" id="page-menu"><li><a href="index.html">Contents</a></li><li><a href="doc-index.html">Index</a></li></ul><p class="caption">lca-0.2.4: O(log n) persistent on-line lowest common ancestor calculation without preprocessing</p></div><div id="content"><div id="index"><p class="caption">Index</p><table><tr><td class="src">cons</td><td>&nbsp;</td></tr><tr><td class="alt">1 (Function)</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:cons">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="alt">2 (Function)</td><td class="module"><a href="Data-LCA-Online-Naive.html#v:cons">Data.LCA.Online.Naive</a></td></tr><tr><td class="alt">3 (Function)</td><td class="module"><a href="Data-LCA-Online.html#v:cons">Data.LCA.Online</a></td></tr><tr><td class="src">drop</td><td>&nbsp;</td></tr><tr><td class="alt">1 (Function)</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:drop">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="alt">2 (Function)</td><td class="module"><a href="Data-LCA-Online-Naive.html#v:drop">Data.LCA.Online.Naive</a></td></tr><tr><td class="alt">3 (Function)</td><td class="module"><a href="Data-LCA-Online.html#v:drop">Data.LCA.Online</a></td></tr><tr><td class="src">empty</td><td>&nbsp;</td></tr><tr><td class="alt">1 (Function)</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:empty">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="alt">2 (Function)</td><td class="module"><a href="Data-LCA-Online-Naive.html#v:empty">Data.LCA.Online.Naive</a></td></tr><tr><td class="alt">3 (Function)</td><td class="module"><a href="Data-LCA-Online.html#v:empty">Data.LCA.Online</a></td></tr><tr><td class="src">fromList</td><td>&nbsp;</td></tr><tr><td class="alt">1 (Function)</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:fromList">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="alt">2 (Function)</td><td class="module"><a href="Data-LCA-Online-Naive.html#v:fromList">Data.LCA.Online.Naive</a></td></tr><tr><td class="alt">3 (Function)</td><td class="module"><a href="Data-LCA-Online.html#v:fromList">Data.LCA.Online</a></td></tr><tr><td class="src">isAncestorOf</td><td>&nbsp;</td></tr><tr><td class="alt">1 (Function)</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:isAncestorOf">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="alt">2 (Function)</td><td class="module"><a href="Data-LCA-Online-Naive.html#v:isAncestorOf">Data.LCA.Online.Naive</a></td></tr><tr><td class="alt">3 (Function)</td><td class="module"><a href="Data-LCA-Online.html#v:isAncestorOf">Data.LCA.Online</a></td></tr><tr><td class="src">keep</td><td>&nbsp;</td></tr><tr><td class="alt">1 (Function)</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:keep">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="alt">2 (Function)</td><td class="module"><a href="Data-LCA-Online-Naive.html#v:keep">Data.LCA.Online.Naive</a></td></tr><tr><td class="alt">3 (Function)</td><td class="module"><a href="Data-LCA-Online.html#v:keep">Data.LCA.Online</a></td></tr><tr><td class="src">lca</td><td>&nbsp;</td></tr><tr><td class="alt">1 (Function)</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:lca">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="alt">2 (Function)</td><td class="module"><a href="Data-LCA-Online-Naive.html#v:lca">Data.LCA.Online.Naive</a></td></tr><tr><td class="alt">3 (Function)</td><td class="module"><a href="Data-LCA-Online.html#v:lca">Data.LCA.Online</a></td></tr><tr><td class="src">length</td><td>&nbsp;</td></tr><tr><td class="alt">1 (Function)</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:length">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="alt">2 (Function)</td><td class="module"><a href="Data-LCA-Online-Naive.html#v:length">Data.LCA.Online.Naive</a></td></tr><tr><td class="alt">3 (Function)</td><td class="module"><a href="Data-LCA-Online.html#v:length">Data.LCA.Online</a></td></tr><tr><td class="src">map</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:map">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="src">mapHom</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:mapHom">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="src">mapWithKey</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:mapWithKey">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="src">mdrop</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:mdrop">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="src">measure</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:measure">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="src">mkeep</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:mkeep">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="src">mlca</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:mlca">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="src">Node</td><td class="module"><a href="Data-LCA-View.html#v:Node">Data.LCA.View</a></td></tr><tr><td class="src">null</td><td>&nbsp;</td></tr><tr><td class="alt">1 (Function)</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:null">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="alt">2 (Function)</td><td class="module"><a href="Data-LCA-Online-Naive.html#v:null">Data.LCA.Online.Naive</a></td></tr><tr><td class="alt">3 (Function)</td><td class="module"><a href="Data-LCA-Online.html#v:null">Data.LCA.Online</a></td></tr><tr><td class="src">Path</td><td>&nbsp;</td></tr><tr><td class="alt">1 (Type/Class)</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#t:Path">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="alt">2 (Type/Class)</td><td class="module"><a href="Data-LCA-Online-Naive.html#t:Path">Data.LCA.Online.Naive</a></td></tr><tr><td class="alt">3 (Type/Class)</td><td class="module"><a href="Data-LCA-Online.html#t:Path">Data.LCA.Online</a></td></tr><tr><td class="src">Root</td><td class="module"><a href="Data-LCA-View.html#v:Root">Data.LCA.View</a></td></tr><tr><td class="src">toList</td><td>&nbsp;</td></tr><tr><td class="alt">1 (Function)</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:toList">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="alt">2 (Function)</td><td class="module"><a href="Data-LCA-Online-Naive.html#v:toList">Data.LCA.Online.Naive</a></td></tr><tr><td class="alt">3 (Function)</td><td class="module"><a href="Data-LCA-Online.html#v:toList">Data.LCA.Online</a></td></tr><tr><td class="src">traverse</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:traverse">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="src">traverseWithKey</td><td>&nbsp;</td></tr><tr><td class="alt">1 (Function)</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:traverseWithKey">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="alt">2 (Function)</td><td class="module"><a href="Data-LCA-Online-Naive.html#v:traverseWithKey">Data.LCA.Online.Naive</a></td></tr><tr><td class="alt">3 (Function)</td><td class="module"><a href="Data-LCA-Online.html#v:traverseWithKey">Data.LCA.Online</a></td></tr><tr><td class="src">uncons</td><td>&nbsp;</td></tr><tr><td class="alt">1 (Function)</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:uncons">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="alt">2 (Function)</td><td class="module"><a href="Data-LCA-Online-Naive.html#v:uncons">Data.LCA.Online.Naive</a></td></tr><tr><td class="alt">3 (Function)</td><td class="module"><a href="Data-LCA-Online.html#v:uncons">Data.LCA.Online</a></td></tr><tr><td class="src">View</td><td class="module"><a href="Data-LCA-View.html#t:View">Data.LCA.View</a></td></tr><tr><td class="src">view</td><td>&nbsp;</td></tr><tr><td class="alt">1 (Function)</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:view">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="alt">2 (Function)</td><td class="module"><a href="Data-LCA-Online-Naive.html#v:view">Data.LCA.Online.Naive</a></td></tr><tr><td class="alt">3 (Function)</td><td class="module"><a href="Data-LCA-Online.html#v:view">Data.LCA.Online</a></td></tr><tr><td class="src">~=</td><td>&nbsp;</td></tr><tr><td class="alt">1 (Function)</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:-126--61-">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="alt">2 (Function)</td><td class="module"><a href="Data-LCA-Online-Naive.html#v:-126--61-">Data.LCA.Online.Naive</a></td></tr><tr><td class="alt">3 (Function)</td><td class="module"><a href="Data-LCA-Online.html#v:-126--61-">Data.LCA.Online</a></td></tr></table></div></div><div id="footer"><p>Produced by <a href="http://www.haskell.org/haddock/">Haddock</a> version 2.13.2</p></div></body></html>
+</script></head><body><div id="package-header"><ul class="links" id="page-menu"><li><a href="index.html">Contents</a></li><li><a href="doc-index.html">Index</a></li></ul><p class="caption">lca-0.3: O(log n) persistent on-line lowest common ancestor calculation without preprocessing</p></div><div id="content"><div id="index"><p class="caption">Index</p><table><tr><td class="src">cons</td><td>&nbsp;</td></tr><tr><td class="alt">1 (Function)</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:cons">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="alt">2 (Function)</td><td class="module"><a href="Data-LCA-Online-Naive.html#v:cons">Data.LCA.Online.Naive</a></td></tr><tr><td class="alt">3 (Function)</td><td class="module"><a href="Data-LCA-Online.html#v:cons">Data.LCA.Online</a></td></tr><tr><td class="src">drop</td><td>&nbsp;</td></tr><tr><td class="alt">1 (Function)</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:drop">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="alt">2 (Function)</td><td class="module"><a href="Data-LCA-Online-Naive.html#v:drop">Data.LCA.Online.Naive</a></td></tr><tr><td class="alt">3 (Function)</td><td class="module"><a href="Data-LCA-Online.html#v:drop">Data.LCA.Online</a></td></tr><tr><td class="src">empty</td><td>&nbsp;</td></tr><tr><td class="alt">1 (Function)</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:empty">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="alt">2 (Function)</td><td class="module"><a href="Data-LCA-Online-Naive.html#v:empty">Data.LCA.Online.Naive</a></td></tr><tr><td class="alt">3 (Function)</td><td class="module"><a href="Data-LCA-Online.html#v:empty">Data.LCA.Online</a></td></tr><tr><td class="src">fromList</td><td>&nbsp;</td></tr><tr><td class="alt">1 (Function)</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:fromList">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="alt">2 (Function)</td><td class="module"><a href="Data-LCA-Online-Naive.html#v:fromList">Data.LCA.Online.Naive</a></td></tr><tr><td class="alt">3 (Function)</td><td class="module"><a href="Data-LCA-Online.html#v:fromList">Data.LCA.Online</a></td></tr><tr><td class="src">isAncestorOf</td><td>&nbsp;</td></tr><tr><td class="alt">1 (Function)</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:isAncestorOf">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="alt">2 (Function)</td><td class="module"><a href="Data-LCA-Online-Naive.html#v:isAncestorOf">Data.LCA.Online.Naive</a></td></tr><tr><td class="alt">3 (Function)</td><td class="module"><a href="Data-LCA-Online.html#v:isAncestorOf">Data.LCA.Online</a></td></tr><tr><td class="src">keep</td><td>&nbsp;</td></tr><tr><td class="alt">1 (Function)</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:keep">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="alt">2 (Function)</td><td class="module"><a href="Data-LCA-Online-Naive.html#v:keep">Data.LCA.Online.Naive</a></td></tr><tr><td class="alt">3 (Function)</td><td class="module"><a href="Data-LCA-Online.html#v:keep">Data.LCA.Online</a></td></tr><tr><td class="src">lca</td><td>&nbsp;</td></tr><tr><td class="alt">1 (Function)</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:lca">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="alt">2 (Function)</td><td class="module"><a href="Data-LCA-Online-Naive.html#v:lca">Data.LCA.Online.Naive</a></td></tr><tr><td class="alt">3 (Function)</td><td class="module"><a href="Data-LCA-Online.html#v:lca">Data.LCA.Online</a></td></tr><tr><td class="src">length</td><td>&nbsp;</td></tr><tr><td class="alt">1 (Function)</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:length">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="alt">2 (Function)</td><td class="module"><a href="Data-LCA-Online-Naive.html#v:length">Data.LCA.Online.Naive</a></td></tr><tr><td class="alt">3 (Function)</td><td class="module"><a href="Data-LCA-Online.html#v:length">Data.LCA.Online</a></td></tr><tr><td class="src">map</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:map">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="src">mapHom</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:mapHom">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="src">mapWithKey</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:mapWithKey">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="src">mdrop</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:mdrop">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="src">measure</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:measure">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="src">mkeep</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:mkeep">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="src">mlca</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:mlca">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="src">Node</td><td class="module"><a href="Data-LCA-View.html#v:Node">Data.LCA.View</a></td></tr><tr><td class="src">null</td><td>&nbsp;</td></tr><tr><td class="alt">1 (Function)</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:null">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="alt">2 (Function)</td><td class="module"><a href="Data-LCA-Online-Naive.html#v:null">Data.LCA.Online.Naive</a></td></tr><tr><td class="alt">3 (Function)</td><td class="module"><a href="Data-LCA-Online.html#v:null">Data.LCA.Online</a></td></tr><tr><td class="src">Path</td><td>&nbsp;</td></tr><tr><td class="alt">1 (Type/Class)</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#t:Path">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="alt">2 (Type/Class)</td><td class="module"><a href="Data-LCA-Online-Naive.html#t:Path">Data.LCA.Online.Naive</a></td></tr><tr><td class="alt">3 (Type/Class)</td><td class="module"><a href="Data-LCA-Online.html#t:Path">Data.LCA.Online</a></td></tr><tr><td class="src">Root</td><td class="module"><a href="Data-LCA-View.html#v:Root">Data.LCA.View</a></td></tr><tr><td class="src">toList</td><td>&nbsp;</td></tr><tr><td class="alt">1 (Function)</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:toList">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="alt">2 (Function)</td><td class="module"><a href="Data-LCA-Online-Naive.html#v:toList">Data.LCA.Online.Naive</a></td></tr><tr><td class="alt">3 (Function)</td><td class="module"><a href="Data-LCA-Online.html#v:toList">Data.LCA.Online</a></td></tr><tr><td class="src">traverse</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:traverse">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="src">traverseWithKey</td><td>&nbsp;</td></tr><tr><td class="alt">1 (Function)</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:traverseWithKey">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="alt">2 (Function)</td><td class="module"><a href="Data-LCA-Online-Naive.html#v:traverseWithKey">Data.LCA.Online.Naive</a></td></tr><tr><td class="alt">3 (Function)</td><td class="module"><a href="Data-LCA-Online.html#v:traverseWithKey">Data.LCA.Online</a></td></tr><tr><td class="src">uncons</td><td>&nbsp;</td></tr><tr><td class="alt">1 (Function)</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:uncons">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="alt">2 (Function)</td><td class="module"><a href="Data-LCA-Online-Naive.html#v:uncons">Data.LCA.Online.Naive</a></td></tr><tr><td class="alt">3 (Function)</td><td class="module"><a href="Data-LCA-Online.html#v:uncons">Data.LCA.Online</a></td></tr><tr><td class="src">View</td><td class="module"><a href="Data-LCA-View.html#t:View">Data.LCA.View</a></td></tr><tr><td class="src">view</td><td>&nbsp;</td></tr><tr><td class="alt">1 (Function)</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:view">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="alt">2 (Function)</td><td class="module"><a href="Data-LCA-Online-Naive.html#v:view">Data.LCA.Online.Naive</a></td></tr><tr><td class="alt">3 (Function)</td><td class="module"><a href="Data-LCA-Online.html#v:view">Data.LCA.Online</a></td></tr><tr><td class="src">~=</td><td>&nbsp;</td></tr><tr><td class="alt">1 (Function)</td><td class="module"><a href="Data-LCA-Online-Monoidal.html#v:-126--61-">Data.LCA.Online.Monoidal</a></td></tr><tr><td class="alt">2 (Function)</td><td class="module"><a href="Data-LCA-Online-Naive.html#v:-126--61-">Data.LCA.Online.Naive</a></td></tr><tr><td class="alt">3 (Function)</td><td class="module"><a href="Data-LCA-Online.html#v:-126--61-">Data.LCA.Online</a></td></tr></table></div></div><div id="footer"><p>Produced by <a href="http://www.haskell.org/haddock/">Haddock</a> version 2.15.1</p></div></body></html>
View
2  index-frames.html
@@ -1,4 +1,4 @@
-<!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>lca-0.2.4: O(log n) persistent on-line lowest common ancestor calculation without preprocessing</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[
+<!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>lca-0.3: O(log n) persistent on-line lowest common ancestor calculation without preprocessing</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();};
//]]>
</script></head><body id="mini"><div id="module-list"><p class="caption">Modules</p><ul><li class="module"><a href="Data-LCA-Online.html" target="main">Data.LCA.Online</a></li><li class="module"><a href="Data-LCA-Online-Monoidal.html" target="main">Data.LCA.Online.Monoidal</a></li><li class="module"><a href="Data-LCA-Online-Naive.html" target="main">Data.LCA.Online.Naive</a></li><li class="module"><a href="Data-LCA-View.html" target="main">Data.LCA.View</a></li></ul></div></body></html>
View
8 index.html
@@ -1,8 +1,4 @@
-<!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>lca-0.2.4: O(log n) persistent on-line lowest common ancestor calculation without preprocessing</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[
+<!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>lca-0.3: O(log n) persistent on-line lowest common ancestor calculation without preprocessing</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();};
//]]>
-</script></head><body><div id="package-header"><ul class="links" id="page-menu"><li><a href="index.html">Contents</a></li><li><a href="doc-index.html">Index</a></li></ul><p class="caption">lca-0.2.4: O(log n) persistent on-line lowest common ancestor calculation without preprocessing</p></div><div id="content"><div id="description"><h1>lca-0.2.4: O(log n) persistent on-line lowest common ancestor calculation without preprocessing</h1><div class="doc"><p>This package provides a reference implementation of my skew binary random access algorithm for performing an <em>online</em> lowest common ancestor search (and online level ancestor search) in logarithmic time without preprocessing. This improves the previous known asymptotic bound for both of these problems from <em>O(h)</em> to <em>O(log h)</em>, where <em>h</em> is the height of the tree. Mostly importantly this bound is completely independent of the width or overall size of the tree, enabling you to calculate lowest common ancestors in a distributed fashion with good locality.
-</p><p>While <em>offline</em> algorithms exist for both of these algorithms that that provide <em>O(1)</em> query time, they all require at least <em>O(n)</em> preprocessing, where <em>n</em> is the size of the entire tree, and so are less suitable for LCA search in areas such as revision control where the tree is constantly updated, or distributed computing where the tree may be too large to fit in any one computer's memory.
-</p><p>Slides are available from
-</p><p><a href="http://www.slideshare.net/ekmett/skewbinary-online-lowest-common-ancestor-search">http://www.slideshare.net/ekmett/skewbinary-online-lowest-common-ancestor-search</a>
-</p></div></div><div id="module-list"><p class="caption">Modules</p><ul><li><span id="control.n.1" class="module collapser" onclick="toggleSection('n.1')">Data</span><ul id="section.n.1" class="show"><li><span id="control.n.1.1" class="module collapser" onclick="toggleSection('n.1.1')">LCA</span><ul id="section.n.1.1" class="show"><li><span class="module"><span id="control.n.1.1.1" class="collapser" onclick="toggleSection('n.1.1.1')">&nbsp;</span><a href="Data-LCA-Online.html">Data.LCA.Online</a></span><ul id="section.n.1.1.1" class="show"><li><span class="module"><a href="Data-LCA-Online-Monoidal.html">Data.LCA.Online.Monoidal</a></span></li><li><span class="module"><a href="Data-LCA-Online-Naive.html">Data.LCA.Online.Naive</a></span></li></ul></li><li><span class="module"><a href="Data-LCA-View.html">Data.LCA.View</a></span></li></ul></li></ul></li></ul></div></div><div id="footer"><p>Produced by <a href="http://www.haskell.org/haddock/">Haddock</a> version 2.13.2</p></div></body></html>
+</script></head><body><div id="package-header"><ul class="links" id="page-menu"><li><a href="index.html">Contents</a></li><li><a href="doc-index.html">Index</a></li></ul><p class="caption">lca-0.3: O(log n) persistent on-line lowest common ancestor calculation without preprocessing</p></div><div id="content"><div id="description"><h1>lca-0.3: O(log n) persistent on-line lowest common ancestor calculation without preprocessing</h1><div class="doc"><p>This package provides a reference implementation of my skew binary random access algorithm for performing an <em>online</em> lowest common ancestor search (and online level ancestor search) in logarithmic time without preprocessing. This improves the previous known asymptotic bound for both of these problems from <em>O(h)</em> to <em>O(log h)</em>, where <em>h</em> is the height of the tree. Mostly importantly this bound is completely independent of the width or overall size of the tree, enabling you to calculate lowest common ancestors in a distributed fashion with good locality.</p><p>While <em>offline</em> algorithms exist for both of these algorithms that that provide <em>O(1)</em> query time, they all require at least <em>O(n)</em> preprocessing, where <em>n</em> is the size of the entire tree, and so are less suitable for LCA search in areas such as revision control where the tree is constantly updated, or distributed computing where the tree may be too large to fit in any one computer's memory.</p><p>Slides are available from</p><p><a href="http://www.slideshare.net/ekmett/skewbinary-online-lowest-common-ancestor-search">http://www.slideshare.net/ekmett/skewbinary-online-lowest-common-ancestor-search</a></p></div></div><div id="module-list"><p class="caption">Modules</p><ul><li><span id="control.n.1" class="module collapser" onclick="toggleSection('n.1')">Data</span><ul id="section.n.1" class="show"><li><span id="control.n.1.1" class="module collapser" onclick="toggleSection('n.1.1')">LCA</span><ul id="section.n.1.1" class="show"><li><span class="module"><span id="control.n.1.1.1" class="collapser" onclick="toggleSection('n.1.1.1')">&nbsp;</span><a href="Data-LCA-Online.html">Data.LCA.Online</a></span><ul id="section.n.1.1.1" class="show"><li><span class="module"><a href="Data-LCA-Online-Monoidal.html">Data.LCA.Online.Monoidal</a></span></li><li><span class="module"><a href="Data-LCA-Online-Naive.html">Data.LCA.Online.Naive</a></span></li></ul></li><li><span class="module"><a href="Data-LCA-View.html">Data.LCA.View</a></span></li></ul></li></ul></li></ul></div></div><div id="footer"><p>Produced by <a href="http://www.haskell.org/haddock/">Haddock</a> version 2.15.1</p></div></body></html>
View
BIN  lca.haddock
Binary file not shown
View
41 ocean.css
@@ -49,14 +49,14 @@ a[href]:hover { text-decoration:underline; }
For reasons, see:
http://yui.yahooapis.com/3.1.1/build/cssfonts/fonts.css
*/
-
+
body {
font:13px/1.4 sans-serif;
*font-size:small; /* for IE */
*font:x-small; /* for IE in quirks mode */
}
-h1 { font-size: 146.5%; /* 19pt */ }
+h1 { font-size: 146.5%; /* 19pt */ }
h2 { font-size: 131%; /* 17pt */ }
h3 { font-size: 116%; /* 15pt */ }
h4 { font-size: 100%; /* 13pt */ }
@@ -98,7 +98,7 @@ pre, code, kbd, samp, tt, .src {
/* @group Common */
-.caption, h1, h2, h3, h4, h5, h6 {
+.caption, h1, h2, h3, h4, h5, h6 {
font-weight: bold;
color: rgb(78,98,114);
margin: 0.8em 0 0.4em;
@@ -122,7 +122,7 @@ ul.links {
ul.links li {
display: inline;
- border-left: 1px solid #d5d5d5;
+ border-left: 1px solid #d5d5d5;
white-space: nowrap;
padding: 0;
}
@@ -378,6 +378,19 @@ div#style-menu-holder {
margin: 0 -0.5em 0 0.5em;
}
+#interface span.fixity {
+ color: #919191;
+ border-left: 1px solid #919191;
+ padding: 0.2em 0.5em 0.2em 0.5em;
+ margin: 0 -1em 0 1em;
+}
+
+#interface span.rightedge {
+ border-left: 1px solid #919191;
+ padding: 0.2em 0 0.2em 0;
+ margin: 0 0 0 1em;
+}
+
#interface table { border-spacing: 2px; }
#interface td {
vertical-align: top;
@@ -420,6 +433,18 @@ div#style-menu-holder {
margin: 0;
}
+/* Render short-style data instances */
+.inst ul {
+ height: 100%;
+ padding: 0.5em;
+ margin: 0;
+}
+
+.inst, .inst li {
+ list-style: none;
+ margin-left: 1em;
+}
+
.top p.src {
border-top: 1px solid #ccc;
}
@@ -457,13 +482,19 @@ div#style-menu-holder {
/* @group Auxillary Pages */
+
+.extension-list {
+ list-style-type: none;
+ margin-left: 0;
+}
+
#mini {
margin: 0 auto;
padding: 0 1em 1em;
}
#mini > * {
- font-size: 93%; /* 12pt */
+ font-size: 93%; /* 12pt */
}
#mini #module-list .caption,
View
615 src/Data-LCA-Online-Monoidal.html
321 additions, 294 deletions not shown
View
292 src/Data-LCA-Online-Naive.html
@@ -7,144 +7,162 @@
<link type='text/css' rel='stylesheet' href='hscolour.css' />
</head>
<body>
-<pre><a name="line-1"></a><span class='hs-comment'>-----------------------------------------------------------------------------</span>
-<a name="line-2"></a><span class='hs-comment'>-- |</span>
-<a name="line-3"></a><span class='hs-comment'>-- Module : Data.LCA.Online.Naive</span>
-<a name="line-4"></a><span class='hs-comment'>-- Copyright : (C) 2011-2012 Edward Kmett</span>
-<a name="line-5"></a><span class='hs-comment'>-- License : BSD-style (see the file LICENSE)</span>
-<a name="line-6"></a><span class='hs-comment'>--</span>
-<a name="line-7"></a><span class='hs-comment'>-- Maintainer : Edward Kmett &lt;ekmett@gmail.com&gt;</span>
-<a name="line-8"></a><span class='hs-comment'>-- Stability : experimental</span>
-<a name="line-9"></a><span class='hs-comment'>-- Portability : portable</span>
-<a name="line-10"></a><span class='hs-comment'>--</span>
-<a name="line-11"></a><span class='hs-comment'>-- Naive online calculation of the the lowest common ancestor in /O(h)/</span>
-<a name="line-12"></a><span class='hs-comment'>----------------------------------------------------------------------------</span>
-<a name="line-13"></a><span class='hs-keyword'>module</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>LCA</span><span class='hs-varop'>.</span><span class='hs-conid'>Online</span><span class='hs-varop'>.</span><span class='hs-conid'>Naive</span>
-<a name="line-14"></a> <span class='hs-layout'>(</span> <span class='hs-conid'>Path</span>
-<a name="line-15"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>empty</span>
-<a name="line-16"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>cons</span>
-<a name="line-17"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>uncons</span>
-<a name="line-18"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>view</span>
-<a name="line-19"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>null</span>
-<a name="line-20"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>length</span>
-<a name="line-21"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>isAncestorOf</span>
-<a name="line-22"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>lca</span>
-<a name="line-23"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>keep</span>
-<a name="line-24"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>drop</span>
-<a name="line-25"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>traverseWithKey</span>
-<a name="line-26"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>toList</span>
-<a name="line-27"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>fromList</span>
-<a name="line-28"></a> <span class='hs-layout'>,</span> <span class='hs-layout'>(</span><span class='hs-varop'>~=</span><span class='hs-layout'>)</span>
-<a name="line-29"></a> <span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
-<a name="line-30"></a>
-<a name="line-31"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Control</span><span class='hs-varop'>.</span><span class='hs-conid'>Applicative</span> <span class='hs-varid'>hiding</span> <span class='hs-layout'>(</span><span class='hs-varid'>empty</span><span class='hs-layout'>)</span>
-<a name="line-32"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Foldable</span> <span class='hs-varid'>hiding</span> <span class='hs-layout'>(</span><span class='hs-varid'>toList</span><span class='hs-layout'>)</span>
-<a name="line-33"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Traversable</span>
-<a name="line-34"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Prelude</span> <span class='hs-varid'>hiding</span> <span class='hs-layout'>(</span><span class='hs-varid'>length</span><span class='hs-layout'>,</span> <span class='hs-varid'>null</span><span class='hs-layout'>,</span> <span class='hs-varid'>drop</span><span class='hs-layout'>)</span>
-<a name="line-35"></a><span class='hs-keyword'>import</span> <span class='hs-keyword'>qualified</span> <span class='hs-conid'>Prelude</span>
-<a name="line-36"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>LCA</span><span class='hs-varop'>.</span><span class='hs-conid'>View</span>
-<a name="line-37"></a>
-<a name="line-38"></a><a name="Path"></a><span class='hs-comment'>-- | An uncompressed 'Path' with memoized length.</span>
-<a name="line-39"></a><a name="Path"></a><span class='hs-keyword'>data</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Path</span> <span class='hs-comment'>{-# UNPACK #-}</span> <span class='hs-varop'>!</span><span class='hs-conid'>Int</span> <span class='hs-keyglyph'>[</span><span class='hs-layout'>(</span><span class='hs-conid'>Int</span><span class='hs-layout'>,</span><span class='hs-varid'>a</span><span class='hs-layout'>)</span><span class='hs-keyglyph'>]</span>
-<a name="line-40"></a> <span class='hs-keyword'>deriving</span> <span class='hs-layout'>(</span><span class='hs-conid'>Show</span><span class='hs-layout'>,</span> <span class='hs-conid'>Read</span><span class='hs-layout'>)</span>
-<a name="line-41"></a>
-<a name="line-42"></a><a name="toList"></a><span class='hs-comment'>-- | Convert a 'Path' to a list of @(ID, value)@ pairs.</span>
-<a name="line-43"></a><span class='hs-definition'>toList</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-keyglyph'>[</span><span class='hs-layout'>(</span><span class='hs-conid'>Int</span><span class='hs-layout'>,</span><span class='hs-varid'>a</span><span class='hs-layout'>)</span><span class='hs-keyglyph'>]</span>
-<a name="line-44"></a><span class='hs-definition'>toList</span> <span class='hs-layout'>(</span><span class='hs-conid'>Path</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>xs</span>
-<a name="line-45"></a><span class='hs-comment'>{-# INLINE toList #-}</span>
-<a name="line-46"></a>
-<a name="line-47"></a><a name="fromList"></a><span class='hs-comment'>-- | Build a 'Path' from a list of @(ID, value)@ pairs.</span>
-<a name="line-48"></a><span class='hs-definition'>fromList</span> <span class='hs-keyglyph'>::</span> <span class='hs-keyglyph'>[</span><span class='hs-layout'>(</span><span class='hs-conid'>Int</span><span class='hs-layout'>,</span><span class='hs-varid'>a</span><span class='hs-layout'>)</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span>
-<a name="line-49"></a><span class='hs-definition'>fromList</span> <span class='hs-varid'>xs</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Path</span> <span class='hs-layout'>(</span><span class='hs-conid'>Prelude</span><span class='hs-varop'>.</span><span class='hs-varid'>length</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-varid'>xs</span>
-<a name="line-50"></a><span class='hs-comment'>{-# INLINE fromList #-}</span>
-<a name="line-51"></a>
-<a name="line-52"></a><a name="instance%20Functor%20Path"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>Functor</span> <span class='hs-conid'>Path</span> <span class='hs-keyword'>where</span>
-<a name="line-53"></a> <span class='hs-varid'>fmap</span> <span class='hs-varid'>f</span> <span class='hs-layout'>(</span><span class='hs-conid'>Path</span> <span class='hs-varid'>n</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>n</span> <span class='hs-keyglyph'>[</span> <span class='hs-layout'>(</span><span class='hs-varid'>k</span><span class='hs-layout'>,</span> <span class='hs-varid'>f</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>|</span> <span class='hs-layout'>(</span><span class='hs-varid'>k</span><span class='hs-layout'>,</span><span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>&lt;-</span> <span class='hs-varid'>xs</span><span class='hs-keyglyph'>]</span>
-<a name="line-54"></a>
-<a name="line-55"></a><a name="instance%20Foldable%20Path"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>Foldable</span> <span class='hs-conid'>Path</span> <span class='hs-keyword'>where</span>
-<a name="line-56"></a> <span class='hs-varid'>foldMap</span> <span class='hs-varid'>f</span> <span class='hs-layout'>(</span><span class='hs-conid'>Path</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>foldMap</span> <span class='hs-layout'>(</span><span class='hs-varid'>f</span> <span class='hs-varop'>.</span> <span class='hs-varid'>snd</span><span class='hs-layout'>)</span> <span class='hs-varid'>xs</span>
+<pre><a name="line-1"></a><span class='hs-comment'>{-# LANGUAGE CPP #-}</span>
+<a name="line-2"></a><span class='hs-comment'>-----------------------------------------------------------------------------</span>
+<a name="line-3"></a><span class='hs-comment'>-- |</span>
+<a name="line-4"></a><span class='hs-comment'>-- Module : Data.LCA.Online.Naive</span>
+<a name="line-5"></a><span class='hs-comment'>-- Copyright : (C) 2011-2015 Edward Kmett</span>
+<a name="line-6"></a><span class='hs-comment'>-- License : BSD-style (see the file LICENSE)</span>
+<a name="line-7"></a><span class='hs-comment'>--</span>
+<a name="line-8"></a><span class='hs-comment'>-- Maintainer : Edward Kmett &lt;ekmett@gmail.com&gt;</span>
+<a name="line-9"></a><span class='hs-comment'>-- Stability : experimental</span>
+<a name="line-10"></a><span class='hs-comment'>-- Portability : portable</span>
+<a name="line-11"></a><span class='hs-comment'>--</span>
+<a name="line-12"></a><span class='hs-comment'>-- Naive online calculation of the the lowest common ancestor in /O(h)/</span>
+<a name="line-13"></a><span class='hs-comment'>----------------------------------------------------------------------------</span>
+<a name="line-14"></a><span class='hs-keyword'>module</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>LCA</span><span class='hs-varop'>.</span><span class='hs-conid'>Online</span><span class='hs-varop'>.</span><span class='hs-conid'>Naive</span>
+<a name="line-15"></a> <span class='hs-layout'>(</span> <span class='hs-conid'>Path</span>
+<a name="line-16"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>empty</span>
+<a name="line-17"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>cons</span>
+<a name="line-18"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>uncons</span>
+<a name="line-19"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>view</span>
+<a name="line-20"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>null</span>
+<a name="line-21"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>length</span>
+<a name="line-22"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>isAncestorOf</span>
+<a name="line-23"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>lca</span>
+<a name="line-24"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>keep</span>
+<a name="line-25"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>drop</span>
+<a name="line-26"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>traverseWithKey</span>
+<a name="line-27"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>toList</span>
+<a name="line-28"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>fromList</span>
+<a name="line-29"></a> <span class='hs-layout'>,</span> <span class='hs-layout'>(</span><span class='hs-varop'>~=</span><span class='hs-layout'>)</span>
+<a name="line-30"></a> <span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
+<a name="line-31"></a>
+<a name="line-32"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Control</span><span class='hs-varop'>.</span><span class='hs-conid'>Applicative</span> <span class='hs-varid'>hiding</span> <span class='hs-layout'>(</span><span class='hs-varid'>empty</span><span class='hs-layout'>)</span>
+<a name="line-33"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Foldable</span> <span class='hs-varid'>hiding</span> <span class='hs-layout'>(</span><span class='hs-varid'>toList</span><span class='hs-layout'>)</span>
+<a name="line-34"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>LCA</span><span class='hs-varop'>.</span><span class='hs-conid'>View</span>
+<a name="line-35"></a>
+<a name="line-36"></a><span class='hs-cpp'>#if __GLASGOW_HASKELL__ &lt; 710</span>
+<a name="line-37"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Traversable</span>
+<a name="line-38"></a><span class='hs-cpp'>#endif</span>
+<a name="line-39"></a>
+<a name="line-40"></a><span class='hs-keyword'>import</span> <span class='hs-keyword'>qualified</span> <span class='hs-conid'>Prelude</span>
+<a name="line-41"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Prelude</span> <span class='hs-varid'>hiding</span>
+<a name="line-42"></a> <span class='hs-layout'>(</span> <span class='hs-varid'>drop</span>
+<a name="line-43"></a><span class='hs-cpp'>#if __GLASGOW_HASKELL__ &lt; 710</span>
+<a name="line-44"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>length</span>
+<a name="line-45"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>null</span>
+<a name="line-46"></a><span class='hs-cpp'>#endif</span>
+<a name="line-47"></a> <span class='hs-layout'>)</span>
+<a name="line-48"></a>
+<a name="line-49"></a><a name="Path"></a><span class='hs-comment'>-- | An uncompressed 'Path' with memoized length.</span>
+<a name="line-50"></a><a name="Path"></a><span class='hs-keyword'>data</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Path</span> <span class='hs-comment'>{-# UNPACK #-}</span> <span class='hs-varop'>!</span><span class='hs-conid'>Int</span> <span class='hs-keyglyph'>[</span><span class='hs-layout'>(</span><span class='hs-conid'>Int</span><span class='hs-layout'>,</span><span class='hs-varid'>a</span><span class='hs-layout'>)</span><span class='hs-keyglyph'>]</span>
+<a name="line-51"></a> <span class='hs-keyword'>deriving</span> <span class='hs-layout'>(</span><span class='hs-conid'>Show</span><span class='hs-layout'>,</span> <span class='hs-conid'>Read</span><span class='hs-layout'>)</span>
+<a name="line-52"></a>
+<a name="line-53"></a><a name="toList"></a><span class='hs-comment'>-- | Convert a 'Path' to a list of @(ID, value)@ pairs.</span>
+<a name="line-54"></a><span class='hs-definition'>toList</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-keyglyph'>[</span><span class='hs-layout'>(</span><span class='hs-conid'>Int</span><span class='hs-layout'>,</span><span class='hs-varid'>a</span><span class='hs-layout'>)</span><span class='hs-keyglyph'>]</span>
+<a name="line-55"></a><span class='hs-definition'>toList</span> <span class='hs-layout'>(</span><span class='hs-conid'>Path</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>xs</span>
+<a name="line-56"></a><span class='hs-comment'>{-# INLINE toList #-}</span>
<a name="line-57"></a>
-<a name="line-58"></a><a name="instance%20Traversable%20Path"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>Traversable</span> <span class='hs-conid'>Path</span> <span class='hs-keyword'>where</span>
-<a name="line-59"></a> <span class='hs-varid'>traverse</span> <span class='hs-varid'>f</span> <span class='hs-layout'>(</span><span class='hs-conid'>Path</span> <span class='hs-varid'>n</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>n</span> <span class='hs-varop'>&lt;$&gt;</span> <span class='hs-varid'>traverse</span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>\</span><span class='hs-layout'>(</span><span class='hs-varid'>k</span><span class='hs-layout'>,</span><span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-conid'>(,)</span> <span class='hs-varid'>k</span> <span class='hs-varop'>&lt;$&gt;</span> <span class='hs-varid'>f</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-varid'>xs</span>
-<a name="line-60"></a>
-<a name="line-61"></a><a name="traverseWithKey"></a><span class='hs-comment'>-- | Traverse a 'Path' with access to the node IDs.</span>
-<a name="line-62"></a><span class='hs-definition'>traverseWithKey</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Applicative</span> <span class='hs-varid'>f</span> <span class='hs-keyglyph'>=&gt;</span> <span class='hs-layout'>(</span><span class='hs-conid'>Int</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-varid'>f</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-varid'>f</span> <span class='hs-layout'>(</span><span class='hs-conid'>Path</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span>
-<a name="line-63"></a><span class='hs-definition'>traverseWithKey</span> <span class='hs-varid'>f</span> <span class='hs-layout'>(</span><span class='hs-conid'>Path</span> <span class='hs-varid'>n</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>n</span> <span class='hs-varop'>&lt;$&gt;</span> <span class='hs-varid'>traverse</span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>\</span><span class='hs-layout'>(</span><span class='hs-varid'>k</span><span class='hs-layout'>,</span><span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-conid'>(,)</span> <span class='hs-varid'>k</span> <span class='hs-varop'>&lt;$&gt;</span> <span class='hs-varid'>f</span> <span class='hs-varid'>k</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-varid'>xs</span>
-<a name="line-64"></a><span class='hs-comment'>{-# INLINE traverseWithKey #-}</span>
+<a name="line-58"></a><a name="fromList"></a><span class='hs-comment'>-- | Build a 'Path' from a list of @(ID, value)@ pairs.</span>
+<a name="line-59"></a><span class='hs-definition'>fromList</span> <span class='hs-keyglyph'>::</span> <span class='hs-keyglyph'>[</span><span class='hs-layout'>(</span><span class='hs-conid'>Int</span><span class='hs-layout'>,</span><span class='hs-varid'>a</span><span class='hs-layout'>)</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span>
+<a name="line-60"></a><span class='hs-definition'>fromList</span> <span class='hs-varid'>xs</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Path</span> <span class='hs-layout'>(</span><span class='hs-conid'>Prelude</span><span class='hs-varop'>.</span><span class='hs-varid'>length</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-varid'>xs</span>
+<a name="line-61"></a><span class='hs-comment'>{-# INLINE fromList #-}</span>
+<a name="line-62"></a>
+<a name="line-63"></a><a name="instance%20Functor%20Path"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>Functor</span> <span class='hs-conid'>Path</span> <span class='hs-keyword'>where</span>
+<a name="line-64"></a> <span class='hs-varid'>fmap</span> <span class='hs-varid'>f</span> <span class='hs-layout'>(</span><span class='hs-conid'>Path</span> <span class='hs-varid'>n</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>n</span> <span class='hs-keyglyph'>[</span> <span class='hs-layout'>(</span><span class='hs-varid'>k</span><span class='hs-layout'>,</span> <span class='hs-varid'>f</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>|</span> <span class='hs-layout'>(</span><span class='hs-varid'>k</span><span class='hs-layout'>,</span><span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>&lt;-</span> <span class='hs-varid'>xs</span><span class='hs-keyglyph'>]</span>
<a name="line-65"></a>
-<a name="line-66"></a><a name="empty"></a><span class='hs-comment'>-- | The empty 'Path'</span>
-<a name="line-67"></a><span class='hs-definition'>empty</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span>
-<a name="line-68"></a><span class='hs-definition'>empty</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Path</span> <span class='hs-num'>0</span> <span class='hs-conid'>[]</span>
-<a name="line-69"></a>
-<a name="line-70"></a><a name="length"></a><span class='hs-comment'>-- | /O(1)/ Determine the length of a 'Path'.</span>
-<a name="line-71"></a><span class='hs-definition'>length</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-conid'>Int</span>
-<a name="line-72"></a><span class='hs-definition'>length</span> <span class='hs-layout'>(</span><span class='hs-conid'>Path</span> <span class='hs-varid'>n</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>n</span>
-<a name="line-73"></a><span class='hs-comment'>{-# INLINE length #-}</span>
-<a name="line-74"></a>
-<a name="line-75"></a><a name="null"></a><span class='hs-comment'>-- | /O(1)/ Returns 'True' iff the 'Path' is 'empty'.</span>
-<a name="line-76"></a><span class='hs-definition'>null</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-conid'>Bool</span>
-<a name="line-77"></a><span class='hs-definition'>null</span> <span class='hs-layout'>(</span><span class='hs-conid'>Path</span> <span class='hs-varid'>n</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>n</span> <span class='hs-varop'>==</span> <span class='hs-num'>0</span>
-<a name="line-78"></a><span class='hs-comment'>{-# INLINE null #-}</span>
-<a name="line-79"></a>
-<a name="line-80"></a><a name="cons"></a><span class='hs-comment'>-- | /O(1)/ Invariant: most operations assume that the keys @k@ are globally unique</span>
-<a name="line-81"></a><span class='hs-comment'>--</span>
-<a name="line-82"></a><span class='hs-comment'>-- Extend the path with a new node ID and value.</span>
-<a name="line-83"></a><span class='hs-definition'>cons</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Int</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span>
-<a name="line-84"></a><span class='hs-definition'>cons</span> <span class='hs-varid'>k</span> <span class='hs-varid'>a</span> <span class='hs-layout'>(</span><span class='hs-conid'>Path</span> <span class='hs-varid'>n</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Path</span> <span class='hs-layout'>(</span><span class='hs-varid'>n</span> <span class='hs-varop'>+</span> <span class='hs-num'>1</span><span class='hs-layout'>)</span> <span class='hs-varop'>$</span> <span class='hs-layout'>(</span><span class='hs-varid'>k</span><span class='hs-layout'>,</span><span class='hs-varid'>a</span><span class='hs-layout'>)</span><span class='hs-conop'>:</span><span class='hs-varid'>xs</span>
-<a name="line-85"></a><span class='hs-comment'>{-# INLINE cons #-}</span>
-<a name="line-86"></a>
-<a name="line-87"></a><a name="uncons"></a><span class='hs-comment'>-- | /O(1)/ Extract the node ID and value from the newest node on the 'Path'.</span>
-<a name="line-88"></a><span class='hs-definition'>uncons</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-conid'>Maybe</span> <span class='hs-layout'>(</span><span class='hs-conid'>Int</span><span class='hs-layout'>,</span> <span class='hs-varid'>a</span><span class='hs-layout'>,</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span>
-<a name="line-89"></a><span class='hs-definition'>uncons</span> <span class='hs-layout'>(</span><span class='hs-conid'>Path</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Nothing</span>
-<a name="line-90"></a><span class='hs-definition'>uncons</span> <span class='hs-layout'>(</span><span class='hs-conid'>Path</span> <span class='hs-varid'>n</span> <span class='hs-layout'>(</span><span class='hs-layout'>(</span><span class='hs-varid'>k</span><span class='hs-layout'>,</span><span class='hs-varid'>a</span><span class='hs-layout'>)</span><span class='hs-conop'>:</span><span class='hs-varid'>xs</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Just</span> <span class='hs-layout'>(</span><span class='hs-varid'>k</span><span class='hs-layout'>,</span><span class='hs-varid'>a</span><span class='hs-layout'>,</span><span class='hs-conid'>Path</span> <span class='hs-layout'>(</span><span class='hs-varid'>n</span> <span class='hs-comment'>-</span> <span class='hs-num'>1</span><span class='hs-layout'>)</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span>
-<a name="line-91"></a><span class='hs-comment'>{-# INLINE uncons #-}</span>
-<a name="line-92"></a>
-<a name="line-93"></a><a name="view"></a><span class='hs-comment'>-- | /O(1)/ Extract the node ID and value from the newest node on the 'Path', slightly faster than 'uncons'.</span>
-<a name="line-94"></a><span class='hs-definition'>view</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-conid'>View</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span>
-<a name="line-95"></a><span class='hs-definition'>view</span> <span class='hs-layout'>(</span><span class='hs-conid'>Path</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Root</span>
-<a name="line-96"></a><span class='hs-definition'>view</span> <span class='hs-layout'>(</span><span class='hs-conid'>Path</span> <span class='hs-varid'>n</span> <span class='hs-layout'>(</span><span class='hs-layout'>(</span><span class='hs-varid'>k</span><span class='hs-layout'>,</span><span class='hs-varid'>a</span><span class='hs-layout'>)</span><span class='hs-conop'>:</span><span class='hs-varid'>xs</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Node</span> <span class='hs-varid'>k</span> <span class='hs-varid'>a</span> <span class='hs-layout'>(</span><span class='hs-conid'>Path</span> <span class='hs-layout'>(</span><span class='hs-varid'>n</span> <span class='hs-comment'>-</span> <span class='hs-num'>1</span><span class='hs-layout'>)</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span>
-<a name="line-97"></a><span class='hs-comment'>{-# INLINE view #-}</span>
-<a name="line-98"></a>
-<a name="line-99"></a><a name="keep"></a><span class='hs-comment'>-- | /O(h - k)/ to @'keep' k@ elements of 'Path' of 'length' @h@</span>
-<a name="line-100"></a><span class='hs-definition'>keep</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Int</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span>
-<a name="line-101"></a><span class='hs-definition'>keep</span> <span class='hs-varid'>k</span> <span class='hs-varid'>p</span><span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-conid'>Path</span> <span class='hs-varid'>n</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span>
-<a name="line-102"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>k</span> <span class='hs-varop'>&gt;=</span> <span class='hs-varid'>n</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>p</span>
-<a name="line-103"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>k</span> <span class='hs-varop'>$</span> <span class='hs-conid'>Prelude</span><span class='hs-varop'>.</span><span class='hs-varid'>drop</span> <span class='hs-layout'>(</span><span class='hs-varid'>n</span> <span class='hs-comment'>-</span> <span class='hs-varid'>k</span><span class='hs-layout'>)</span> <span class='hs-varid'>xs</span>
-<a name="line-104"></a><span class='hs-comment'>{-# INLINE keep #-}</span>
-<a name="line-105"></a>
-<a name="line-106"></a><a name="drop"></a><span class='hs-comment'>-- | /O(k)/ to @'drop' k@ elements from a 'Path'</span>
-<a name="line-107"></a><span class='hs-definition'>drop</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Int</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span>
-<a name="line-108"></a><span class='hs-definition'>drop</span> <span class='hs-varid'>k</span> <span class='hs-layout'>(</span><span class='hs-conid'>Path</span> <span class='hs-varid'>n</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span>
-<a name="line-109"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>k</span> <span class='hs-varop'>&gt;=</span> <span class='hs-varid'>n</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>empty</span>
-<a name="line-110"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Path</span> <span class='hs-layout'>(</span><span class='hs-varid'>n</span> <span class='hs-comment'>-</span> <span class='hs-varid'>k</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-conid'>Prelude</span><span class='hs-varop'>.</span><span class='hs-varid'>drop</span> <span class='hs-varid'>k</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span>
-<a name="line-111"></a><span class='hs-comment'>{-# INLINE drop #-}</span>
-<a name="line-112"></a>
-<a name="line-113"></a><a name="isAncestorOf"></a><span class='hs-comment'>-- | /O(h)/ @xs `isAncestorOf` ys@ holds when @xs@ is a prefix starting at the root of 'Path' @ys@.</span>
-<a name="line-114"></a><span class='hs-definition'>isAncestorOf</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-conid'>Bool</span>
-<a name="line-115"></a><span class='hs-definition'>isAncestorOf</span> <span class='hs-varid'>xs</span> <span class='hs-varid'>ys</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>xs</span> <span class='hs-varop'>~=</span> <span class='hs-varid'>keep</span> <span class='hs-layout'>(</span><span class='hs-varid'>length</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-varid'>ys</span>
-<a name="line-116"></a><span class='hs-comment'>{-# INLINE isAncestorOf #-}</span>
-<a name="line-117"></a>
-<a name="line-118"></a><span class='hs-keyword'>infix</span> <span class='hs-num'>4</span> <span class='hs-varop'>~=</span>
-<a name="line-119"></a><a name="~="></a><span class='hs-comment'>-- | /O(1)/ Compare to see if two trees have the same leaf key</span>
-<a name="line-120"></a><span class='hs-layout'>(</span><span class='hs-varop'>~=</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-conid'>Bool</span>
-<a name="line-121"></a><span class='hs-conid'>Path</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span> <span class='hs-varop'>~=</span> <span class='hs-conid'>Path</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>True</span>
-<a name="line-122"></a><span class='hs-conid'>Path</span> <span class='hs-keyword'>_</span> <span class='hs-layout'>(</span><span class='hs-layout'>(</span><span class='hs-varid'>i</span><span class='hs-layout'>,</span><span class='hs-keyword'>_</span><span class='hs-layout'>)</span><span class='hs-conop'>:</span><span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-varop'>~=</span> <span class='hs-conid'>Path</span> <span class='hs-keyword'>_</span> <span class='hs-layout'>(</span><span class='hs-layout'>(</span><span class='hs-varid'>j</span><span class='hs-layout'>,</span><span class='hs-keyword'>_</span><span class='hs-layout'>)</span><span class='hs-conop'>:</span><span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>i</span> <span class='hs-varop'>==</span> <span class='hs-varid'>j</span>
-<a name="line-123"></a><span class='hs-keyword'>_</span> <span class='hs-varop'>~=</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>False</span>
-<a name="line-124"></a><span class='hs-comment'>{-# INLINE (~=) #-}</span>
-<a name="line-125"></a>
-<a name="line-126"></a><a name="lca"></a><span class='hs-comment'>-- | /O(h)/ Compute the lowest common ancestor of two paths</span>
-<a name="line-127"></a><span class='hs-definition'>lca</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span>
-<a name="line-128"></a><span class='hs-definition'>lca</span> <span class='hs-varid'>xs0</span> <span class='hs-varid'>ys0</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>compare</span> <span class='hs-varid'>nxs</span> <span class='hs-varid'>nys</span> <span class='hs-keyword'>of</span>
-<a name="line-129"></a> <span class='hs-conid'>LT</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-varid'>go</span> <span class='hs-varid'>nxs</span> <span class='hs-layout'>(</span><span class='hs-varid'>toList</span> <span class='hs-varid'>xs0</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>toList</span> <span class='hs-layout'>(</span><span class='hs-varid'>keep</span> <span class='hs-varid'>nxs</span> <span class='hs-varid'>ys0</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
-<a name="line-130"></a> <span class='hs-conid'>EQ</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-varid'>go</span> <span class='hs-varid'>nxs</span> <span class='hs-layout'>(</span><span class='hs-varid'>toList</span> <span class='hs-varid'>xs0</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>toList</span> <span class='hs-varid'>ys0</span><span class='hs-layout'>)</span>
-<a name="line-131"></a> <span class='hs-conid'>GT</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-varid'>go</span> <span class='hs-varid'>nys</span> <span class='hs-layout'>(</span><span class='hs-varid'>toList</span> <span class='hs-layout'>(</span><span class='hs-varid'>keep</span> <span class='hs-varid'>nys</span> <span class='hs-varid'>xs0</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>toList</span> <span class='hs-varid'>ys0</span><span class='hs-layout'>)</span>
-<a name="line-132"></a> <span class='hs-keyword'>where</span>
-<a name="line-133"></a> <span class='hs-varid'>nxs</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>length</span> <span class='hs-varid'>xs0</span>
-<a name="line-134"></a> <span class='hs-varid'>nys</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>length</span> <span class='hs-varid'>ys0</span>
-<a name="line-135"></a> <span class='hs-varid'>go</span> <span class='hs-varid'>k</span> <span class='hs-varid'>xss</span><span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-layout'>(</span><span class='hs-varid'>i</span><span class='hs-layout'>,</span><span class='hs-keyword'>_</span><span class='hs-layout'>)</span><span class='hs-conop'>:</span><span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-layout'>(</span><span class='hs-varid'>j</span><span class='hs-layout'>,</span><span class='hs-keyword'>_</span><span class='hs-layout'>)</span><span class='hs-conop'>:</span><span class='hs-varid'>ys</span><span class='hs-layout'>)</span>
-<a name="line-136"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>i</span> <span class='hs-varop'>==</span> <span class='hs-varid'>j</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>k</span> <span class='hs-varid'>xss</span>
-<a name="line-137"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>go</span> <span class='hs-layout'>(</span><span class='hs-varid'>k</span> <span class='hs-comment'>-</span> <span class='hs-num'>1</span><span class='hs-layout'>)</span> <span class='hs-varid'>xs</span> <span class='hs-varid'>ys</span>
-<a name="line-138"></a> <span class='hs-varid'>go</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>empty</span>
-<a name="line-139"></a><span class='hs-comment'>{-# INLINE lca #-}</span>
+<a name="line-66"></a><a name="instance%20Foldable%20Path"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>Foldable</span> <span class='hs-conid'>Path</span> <span class='hs-keyword'>where</span>
+<a name="line-67"></a> <span class='hs-varid'>foldMap</span> <span class='hs-varid'>f</span> <span class='hs-layout'>(</span><span class='hs-conid'>Path</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>foldMap</span> <span class='hs-layout'>(</span><span class='hs-varid'>f</span> <span class='hs-varop'>.</span> <span class='hs-varid'>snd</span><span class='hs-layout'>)</span> <span class='hs-varid'>xs</span>
+<a name="line-68"></a><span class='hs-cpp'>#if __GLASGOW_HASKELL__ &gt;= 710</span>
+<a name="line-69"></a> <span class='hs-varid'>length</span> <span class='hs-layout'>(</span><span class='hs-conid'>Path</span> <span class='hs-varid'>n</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>n</span>
+<a name="line-70"></a> <span class='hs-varid'>null</span> <span class='hs-layout'>(</span><span class='hs-conid'>Path</span> <span class='hs-varid'>n</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>n</span> <span class='hs-varop'>==</span> <span class='hs-num'>0</span>
+<a name="line-71"></a>
+<a name="line-72"></a><span class='hs-cpp'>#else</span>
+<a name="line-73"></a>
+<a name="line-74"></a><a name="length"></a><span class='hs-comment'>-- | /O(1)/ Determine the length of a 'Path'.</span>
+<a name="line-75"></a><span class='hs-definition'>length</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-conid'>Int</span>
+<a name="line-76"></a><span class='hs-definition'>length</span> <span class='hs-layout'>(</span><span class='hs-conid'>Path</span> <span class='hs-varid'>n</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>n</span>
+<a name="line-77"></a><span class='hs-comment'>{-# INLINE length #-}</span>
+<a name="line-78"></a>
+<a name="line-79"></a><a name="null"></a><span class='hs-comment'>-- | /O(1)/ Returns 'True' iff the 'Path' is 'empty'.</span>
+<a name="line-80"></a><span class='hs-definition'>null</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-conid'>Bool</span>
+<a name="line-81"></a><span class='hs-definition'>null</span> <span class='hs-layout'>(</span><span class='hs-conid'>Path</span> <span class='hs-varid'>n</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>n</span> <span class='hs-varop'>==</span> <span class='hs-num'>0</span>
+<a name="line-82"></a><span class='hs-comment'>{-# INLINE null #-}</span>
+<a name="line-83"></a>
+<a name="line-84"></a><span class='hs-cpp'>#endif</span>
+<a name="line-85"></a>
+<a name="line-86"></a><a name="instance%20Traversable%20Path"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>Traversable</span> <span class='hs-conid'>Path</span> <span class='hs-keyword'>where</span>
+<a name="line-87"></a> <span class='hs-varid'>traverse</span> <span class='hs-varid'>f</span> <span class='hs-layout'>(</span><span class='hs-conid'>Path</span> <span class='hs-varid'>n</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>n</span> <span class='hs-varop'>&lt;$&gt;</span> <span class='hs-varid'>traverse</span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>\</span><span class='hs-layout'>(</span><span class='hs-varid'>k</span><span class='hs-layout'>,</span><span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-conid'>(,)</span> <span class='hs-varid'>k</span> <span class='hs-varop'>&lt;$&gt;</span> <span class='hs-varid'>f</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-varid'>xs</span>
+<a name="line-88"></a>
+<a name="line-89"></a><a name="traverseWithKey"></a><span class='hs-comment'>-- | Traverse a 'Path' with access to the node IDs.</span>
+<a name="line-90"></a><span class='hs-definition'>traverseWithKey</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Applicative</span> <span class='hs-varid'>f</span> <span class='hs-keyglyph'>=&gt;</span> <span class='hs-layout'>(</span><span class='hs-conid'>Int</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-varid'>f</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-varid'>f</span> <span class='hs-layout'>(</span><span class='hs-conid'>Path</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span>
+<a name="line-91"></a><span class='hs-definition'>traverseWithKey</span> <span class='hs-varid'>f</span> <span class='hs-layout'>(</span><span class='hs-conid'>Path</span> <span class='hs-varid'>n</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>n</span> <span class='hs-varop'>&lt;$&gt;</span> <span class='hs-varid'>traverse</span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>\</span><span class='hs-layout'>(</span><span class='hs-varid'>k</span><span class='hs-layout'>,</span><span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-conid'>(,)</span> <span class='hs-varid'>k</span> <span class='hs-varop'>&lt;$&gt;</span> <span class='hs-varid'>f</span> <span class='hs-varid'>k</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-varid'>xs</span>
+<a name="line-92"></a><span class='hs-comment'>{-# INLINE traverseWithKey #-}</span>
+<a name="line-93"></a>
+<a name="line-94"></a><a name="empty"></a><span class='hs-comment'>-- | The empty 'Path'</span>
+<a name="line-95"></a><span class='hs-definition'>empty</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span>
+<a name="line-96"></a><span class='hs-definition'>empty</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Path</span> <span class='hs-num'>0</span> <span class='hs-conid'>[]</span>
+<a name="line-97"></a>
+<a name="line-98"></a><a name="cons"></a><span class='hs-comment'>-- | /O(1)/ Invariant: most operations assume that the keys @k@ are globally unique</span>
+<a name="line-99"></a><span class='hs-comment'>--</span>
+<a name="line-100"></a><span class='hs-comment'>-- Extend the path with a new node ID and value.</span>
+<a name="line-101"></a><span class='hs-definition'>cons</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Int</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span>
+<a name="line-102"></a><span class='hs-definition'>cons</span> <span class='hs-varid'>k</span> <span class='hs-varid'>a</span> <span class='hs-layout'>(</span><span class='hs-conid'>Path</span> <span class='hs-varid'>n</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Path</span> <span class='hs-layout'>(</span><span class='hs-varid'>n</span> <span class='hs-varop'>+</span> <span class='hs-num'>1</span><span class='hs-layout'>)</span> <span class='hs-varop'>$</span> <span class='hs-layout'>(</span><span class='hs-varid'>k</span><span class='hs-layout'>,</span><span class='hs-varid'>a</span><span class='hs-layout'>)</span><span class='hs-conop'>:</span><span class='hs-varid'>xs</span>
+<a name="line-103"></a><span class='hs-comment'>{-# INLINE cons #-}</span>
+<a name="line-104"></a>
+<a name="line-105"></a><a name="uncons"></a><span class='hs-comment'>-- | /O(1)/ Extract the node ID and value from the newest node on the 'Path'.</span>
+<a name="line-106"></a><span class='hs-definition'>uncons</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-conid'>Maybe</span> <span class='hs-layout'>(</span><span class='hs-conid'>Int</span><span class='hs-layout'>,</span> <span class='hs-varid'>a</span><span class='hs-layout'>,</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span>
+<a name="line-107"></a><span class='hs-definition'>uncons</span> <span class='hs-layout'>(</span><span class='hs-conid'>Path</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Nothing</span>
+<a name="line-108"></a><span class='hs-definition'>uncons</span> <span class='hs-layout'>(</span><span class='hs-conid'>Path</span> <span class='hs-varid'>n</span> <span class='hs-layout'>(</span><span class='hs-layout'>(</span><span class='hs-varid'>k</span><span class='hs-layout'>,</span><span class='hs-varid'>a</span><span class='hs-layout'>)</span><span class='hs-conop'>:</span><span class='hs-varid'>xs</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Just</span> <span class='hs-layout'>(</span><span class='hs-varid'>k</span><span class='hs-layout'>,</span><span class='hs-varid'>a</span><span class='hs-layout'>,</span><span class='hs-conid'>Path</span> <span class='hs-layout'>(</span><span class='hs-varid'>n</span> <span class='hs-comment'>-</span> <span class='hs-num'>1</span><span class='hs-layout'>)</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span>
+<a name="line-109"></a><span class='hs-comment'>{-# INLINE uncons #-}</span>
+<a name="line-110"></a>
+<a name="line-111"></a><a name="view"></a><span class='hs-comment'>-- | /O(1)/ Extract the node ID and value from the newest node on the 'Path', slightly faster than 'uncons'.</span>
+<a name="line-112"></a><span class='hs-definition'>view</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-conid'>View</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span>
+<a name="line-113"></a><span class='hs-definition'>view</span> <span class='hs-layout'>(</span><span class='hs-conid'>Path</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Root</span>
+<a name="line-114"></a><span class='hs-definition'>view</span> <span class='hs-layout'>(</span><span class='hs-conid'>Path</span> <span class='hs-varid'>n</span> <span class='hs-layout'>(</span><span class='hs-layout'>(</span><span class='hs-varid'>k</span><span class='hs-layout'>,</span><span class='hs-varid'>a</span><span class='hs-layout'>)</span><span class='hs-conop'>:</span><span class='hs-varid'>xs</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Node</span> <span class='hs-varid'>k</span> <span class='hs-varid'>a</span> <span class='hs-layout'>(</span><span class='hs-conid'>Path</span> <span class='hs-layout'>(</span><span class='hs-varid'>n</span> <span class='hs-comment'>-</span> <span class='hs-num'>1</span><span class='hs-layout'>)</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span>
+<a name="line-115"></a><span class='hs-comment'>{-# INLINE view #-}</span>
+<a name="line-116"></a>
+<a name="line-117"></a><a name="keep"></a><span class='hs-comment'>-- | /O(h - k)/ to @'keep' k@ elements of 'Path' of 'length' @h@</span>
+<a name="line-118"></a><span class='hs-definition'>keep</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Int</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span>
+<a name="line-119"></a><span class='hs-definition'>keep</span> <span class='hs-varid'>k</span> <span class='hs-varid'>p</span><span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-conid'>Path</span> <span class='hs-varid'>n</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span>
+<a name="line-120"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>k</span> <span class='hs-varop'>&gt;=</span> <span class='hs-varid'>n</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>p</span>
+<a name="line-121"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>k</span> <span class='hs-varop'>$</span> <span class='hs-conid'>Prelude</span><span class='hs-varop'>.</span><span class='hs-varid'>drop</span> <span class='hs-layout'>(</span><span class='hs-varid'>n</span> <span class='hs-comment'>-</span> <span class='hs-varid'>k</span><span class='hs-layout'>)</span> <span class='hs-varid'>xs</span>
+<a name="line-122"></a><span class='hs-comment'>{-# INLINE keep #-}</span>
+<a name="line-123"></a>
+<a name="line-124"></a><a name="drop"></a><span class='hs-comment'>-- | /O(k)/ to @'drop' k@ elements from a 'Path'</span>
+<a name="line-125"></a><span class='hs-definition'>drop</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Int</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span>
+<a name="line-126"></a><span class='hs-definition'>drop</span> <span class='hs-varid'>k</span> <span class='hs-layout'>(</span><span class='hs-conid'>Path</span> <span class='hs-varid'>n</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span>
+<a name="line-127"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>k</span> <span class='hs-varop'>&gt;=</span> <span class='hs-varid'>n</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>empty</span>
+<a name="line-128"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Path</span> <span class='hs-layout'>(</span><span class='hs-varid'>n</span> <span class='hs-comment'>-</span> <span class='hs-varid'>k</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-conid'>Prelude</span><span class='hs-varop'>.</span><span class='hs-varid'>drop</span> <span class='hs-varid'>k</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span>
+<a name="line-129"></a><span class='hs-comment'>{-# INLINE drop #-}</span>
+<a name="line-130"></a>
+<a name="line-131"></a><a name="isAncestorOf"></a><span class='hs-comment'>-- | /O(h)/ @xs `isAncestorOf` ys@ holds when @xs@ is a prefix starting at the root of 'Path' @ys@.</span>
+<a name="line-132"></a><span class='hs-definition'>isAncestorOf</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-conid'>Bool</span>
+<a name="line-133"></a><span class='hs-definition'>isAncestorOf</span> <span class='hs-varid'>xs</span> <span class='hs-varid'>ys</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>xs</span> <span class='hs-varop'>~=</span> <span class='hs-varid'>keep</span> <span class='hs-layout'>(</span><span class='hs-varid'>length</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-varid'>ys</span>
+<a name="line-134"></a><span class='hs-comment'>{-# INLINE isAncestorOf #-}</span>
+<a name="line-135"></a>
+<a name="line-136"></a><span class='hs-keyword'>infix</span> <span class='hs-num'>4</span> <span class='hs-varop'>~=</span>
+<a name="line-137"></a><a name="~="></a><span class='hs-comment'>-- | /O(1)/ Compare to see if two trees have the same leaf key</span>
+<a name="line-138"></a><span class='hs-layout'>(</span><span class='hs-varop'>~=</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-conid'>Bool</span>
+<a name="line-139"></a><span class='hs-conid'>Path</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span> <span class='hs-varop'>~=</span> <span class='hs-conid'>Path</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>True</span>
+<a name="line-140"></a><span class='hs-conid'>Path</span> <span class='hs-keyword'>_</span> <span class='hs-layout'>(</span><span class='hs-layout'>(</span><span class='hs-varid'>i</span><span class='hs-layout'>,</span><span class='hs-keyword'>_</span><span class='hs-layout'>)</span><span class='hs-conop'>:</span><span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-varop'>~=</span> <span class='hs-conid'>Path</span> <span class='hs-keyword'>_</span> <span class='hs-layout'>(</span><span class='hs-layout'>(</span><span class='hs-varid'>j</span><span class='hs-layout'>,</span><span class='hs-keyword'>_</span><span class='hs-layout'>)</span><span class='hs-conop'>:</span><span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>i</span> <span class='hs-varop'>==</span> <span class='hs-varid'>j</span>
+<a name="line-141"></a><span class='hs-keyword'>_</span> <span class='hs-varop'>~=</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>False</span>
+<a name="line-142"></a><span class='hs-comment'>{-# INLINE (~=) #-}</span>
+<a name="line-143"></a>
+<a name="line-144"></a><a name="lca"></a><span class='hs-comment'>-- | /O(h)/ Compute the lowest common ancestor of two paths</span>
+<a name="line-145"></a><span class='hs-definition'>lca</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>a</span>
+<a name="line-146"></a><span class='hs-definition'>lca</span> <span class='hs-varid'>xs0</span> <span class='hs-varid'>ys0</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>compare</span> <span class='hs-varid'>nxs</span> <span class='hs-varid'>nys</span> <span class='hs-keyword'>of</span>
+<a name="line-147"></a> <span class='hs-conid'>LT</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-varid'>go</span> <span class='hs-varid'>nxs</span> <span class='hs-layout'>(</span><span class='hs-varid'>toList</span> <span class='hs-varid'>xs0</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>toList</span> <span class='hs-layout'>(</span><span class='hs-varid'>keep</span> <span class='hs-varid'>nxs</span> <span class='hs-varid'>ys0</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
+<a name="line-148"></a> <span class='hs-conid'>EQ</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-varid'>go</span> <span class='hs-varid'>nxs</span> <span class='hs-layout'>(</span><span class='hs-varid'>toList</span> <span class='hs-varid'>xs0</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>toList</span> <span class='hs-varid'>ys0</span><span class='hs-layout'>)</span>
+<a name="line-149"></a> <span class='hs-conid'>GT</span> <span class='hs-keyglyph'>-&gt;</span> <span class='hs-varid'>go</span> <span class='hs-varid'>nys</span> <span class='hs-layout'>(</span><span class='hs-varid'>toList</span> <span class='hs-layout'>(</span><span class='hs-varid'>keep</span> <span class='hs-varid'>nys</span> <span class='hs-varid'>xs0</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>toList</span> <span class='hs-varid'>ys0</span><span class='hs-layout'>)</span>
+<a name="line-150"></a> <span class='hs-keyword'>where</span>
+<a name="line-151"></a> <span class='hs-varid'>nxs</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>length</span> <span class='hs-varid'>xs0</span>
+<a name="line-152"></a> <span class='hs-varid'>nys</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>length</span> <span class='hs-varid'>ys0</span>
+<a name="line-153"></a> <span class='hs-varid'>go</span> <span class='hs-varid'>k</span> <span class='hs-varid'>xss</span><span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-layout'>(</span><span class='hs-varid'>i</span><span class='hs-layout'>,</span><span class='hs-keyword'>_</span><span class='hs-layout'>)</span><span class='hs-conop'>:</span><span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-layout'>(</span><span class='hs-varid'>j</span><span class='hs-layout'>,</span><span class='hs-keyword'>_</span><span class='hs-layout'>)</span><span class='hs-conop'>:</span><span class='hs-varid'>ys</span><span class='hs-layout'>)</span>
+<a name="line-154"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>i</span> <span class='hs-varop'>==</span> <span class='hs-varid'>j</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Path</span> <span class='hs-varid'>k</span> <span class='hs-varid'>xss</span>
+<a name="line-155"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>go</span> <span class='hs-layout'>(</span><span class='hs-varid'>k</span> <span class='hs-comment'>-</span> <span class='hs-num'>1</span><span class='hs-layout'>)</span> <span class='hs-varid'>xs</span> <span class='hs-varid'>ys</span>
+<a name="line-156"></a> <span class='hs-varid'>go</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>empty</span>
+<a name="line-157"></a><span class='hs-comment'>{-# INLINE lca #-}</span>
</pre></body>
</html>
View
481 src/Data-LCA-Online.html
252 additions, 229 deletions not shown
View
71 src/Data-LCA-View.html
@@ -7,39 +7,42 @@
<link type='text/css' rel='stylesheet' href='hscolour.css' />
</head>
<body>
-<pre><a name=