-
Notifications
You must be signed in to change notification settings - Fork 3
/
Data-LCA-Online-Monoidal.html
14 lines (14 loc) · 28 KB
/
Data-LCA-Online-Monoidal.html
1
2
3
4
5
6
7
8
9
10
11
12
13
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.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 <ekmett@gmail.com></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 "summary" 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 -> [(<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 => [(<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: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 => (a -> b) -> <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -> <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b</li><li class="src short"><a href="#v:mapHom">mapHom</a> :: (a -> b) -> <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -> <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 => (<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> -> a -> b) -> <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -> <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) => (a -> f b) -> <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -> 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) => (<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> -> a -> f b) -> <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -> 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 => <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="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 => <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -> <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 => <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -> <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 -> <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 -> <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 => <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -> 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 => <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -> <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b -> <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 => <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> -> <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -> <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) => (a -> b) -> <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</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> 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 => <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> -> <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -> <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) => (a -> b) -> <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</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> a)</li><li class="src short"><a href="#v:-126--61-">(~=)</a> :: <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -> <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b -> <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) => <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -> <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b -> <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) => (a -> c) -> (b -> d) -> <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -> <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b -> (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"> </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> (<a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a)</td><td class="doc empty"> </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> (<a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a)</td><td class="doc empty"> </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 -> [(<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 => [(<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#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 => (a -> b) -> <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -> <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 -> b) -> <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -> <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 => (<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> -> a -> b) -> <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -> <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) => (a -> f b) -> <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -> 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) => (<a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> -> a -> f b) -> <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -> 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 => <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="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 => <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -> <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 => <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -> <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 -> <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 -> <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 => <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -> 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 => <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -> <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b -> <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 => <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> -> <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -> <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 "level ancestor problem" 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) => (a -> b) -> <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</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> 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 => <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</a> -> <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -> <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) => (a -> b) -> <a href="file:///usr/local/share/doc/ghc/html/libraries/base-4.7.0.1/Data-Int.html#t:Int">Int</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> 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 -> <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b -> <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) => <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -> <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b -> <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) => (a -> c) -> (b -> d) -> <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> a -> <a href="Data-LCA-Online-Monoidal.html#t:Path">Path</a> b -> (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>