/usr/share/doc/libghc-psqueue-doc/html/Data-PSQueue.html is in libghc-psqueue-doc 1.1-10.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | <!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.PSQueue</title><link href="ocean.css" rel="stylesheet" type="text/css" title="Ocean" /><script src="haddock-util.js" type="text/javascript"></script><script src="file:///usr/share/javascript/mathjax/MathJax.js" type="text/javascript"></script><script type="text/javascript">//<![CDATA[
window.onload = function () {pageLoad();setSynopsis("mini_Data-PSQueue.html");};
//]]>
</script></head><body><div id="package-header"><ul class="links" id="page-menu"><li><a href="src/Data-PSQueue.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">PSQueue-1.1: Priority Search Queue</p></div><div id="content"><div id="module-header"><table class="info"><tr><th>Safe Haskell</th><td>Safe</td></tr><tr><th>Language</th><td>Haskell98</td></tr></table><p class="caption">Data.PSQueue</p></div><div id="table-of-contents"><p class="caption">Contents</p><ul><li><a href="#g:1">Binding Type</a></li><li><a href="#g:2">Priority Search Queue Type</a></li><li><a href="#g:3">Query</a></li><li><a href="#g:4">Construction</a></li><li><a href="#g:5">Insertion</a></li><li><a href="#g:6">Delete/Update </a></li><li><a href="#g:7">Conversion</a></li><li><a href="#g:8">Priority Queue</a></li><li><a href="#g:9">Fold</a></li></ul></div><div id="description"><p class="caption">Description</p><div class="doc"><p>A <em>priority search queue</em> (henceforth <em>queue</em>) efficiently supports the
opperations of both a search tree and a priority queue. A <code><a href="Data-PSQueue.html#t:Binding">Binding</a></code> is a
product of a key and a priority. Bindings can be inserted, deleted, modified
and queried in logarithmic time, and the binding with the least priority can be
retrieved in constant time. A queue can be built from a list of bindings,
sorted by keys, in linear time.</p><p>This implementation is due to Ralf Hinze.</p><ul><li>Hinze, R., <em>A Simple Implementation Technique for Priority Search Queues</em>, ICFP 2001, pp. 110-121</li></ul><p><a href="http://citeseer.ist.psu.edu/hinze01simple.html">http://citeseer.ist.psu.edu/hinze01simple.html</a></p></div></div><div id="synopsis"><p id="control.syn" class="caption expander" onclick="toggleSection('syn')">Synopsis</p><ul id="section.syn" class="hide" onclick="toggleSection('syn')"><li class="src short"><span class="keyword">data</span> <a href="#t:Binding">Binding</a> k p = k <a href="#v::-45--62-">:-></a> p</li><li class="src short"><a href="#v:key">key</a> :: <a href="Data-PSQueue.html#t:Binding">Binding</a> k p -> k</li><li class="src short"><a href="#v:prio">prio</a> :: <a href="Data-PSQueue.html#t:Binding">Binding</a> k p -> p</li><li class="src short"><span class="keyword">data</span> <a href="#t:PSQ">PSQ</a> k p</li><li class="src short"><a href="#v:size">size</a> :: <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Int.html#t:Int">Int</a></li><li class="src short"><a href="#v:null">null</a> :: <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Bool.html#t:Bool">Bool</a></li><li class="src short"><a href="#v:lookup">lookup</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => k -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Maybe.html#t:Maybe">Maybe</a> p</li><li class="src short"><a href="#v:empty">empty</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p</li><li class="src short"><a href="#v:singleton">singleton</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => k -> p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p</li><li class="src short"><a href="#v:insert">insert</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => k -> p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p</li><li class="src short"><a href="#v:insertWith">insertWith</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => (p -> p -> p) -> k -> p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p</li><li class="src short"><a href="#v:delete">delete</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => k -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p</li><li class="src short"><a href="#v:adjust">adjust</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k) => (p -> p) -> k -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p</li><li class="src short"><a href="#v:adjustWithKey">adjustWithKey</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => (k -> p -> p) -> k -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p</li><li class="src short"><a href="#v:update">update</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => (p -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Maybe.html#t:Maybe">Maybe</a> p) -> k -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p</li><li class="src short"><a href="#v:updateWithKey">updateWithKey</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => (k -> p -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Maybe.html#t:Maybe">Maybe</a> p) -> k -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p</li><li class="src short"><a href="#v:alter">alter</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Maybe.html#t:Maybe">Maybe</a> p -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Maybe.html#t:Maybe">Maybe</a> p) -> k -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p</li><li class="src short"><a href="#v:keys">keys</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> [k]</li><li class="src short"><a href="#v:toList">toList</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> [<a href="Data-PSQueue.html#t:Binding">Binding</a> k p]</li><li class="src short"><a href="#v:toAscList">toAscList</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> [<a href="Data-PSQueue.html#t:Binding">Binding</a> k p]</li><li class="src short"><a href="#v:toDescList">toDescList</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> [<a href="Data-PSQueue.html#t:Binding">Binding</a> k p]</li><li class="src short"><a href="#v:fromList">fromList</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => [<a href="Data-PSQueue.html#t:Binding">Binding</a> k p] -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p</li><li class="src short"><a href="#v:fromAscList">fromAscList</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => [<a href="Data-PSQueue.html#t:Binding">Binding</a> k p] -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p</li><li class="src short"><a href="#v:fromDistinctAscList">fromDistinctAscList</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => [<a href="Data-PSQueue.html#t:Binding">Binding</a> k p] -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p</li><li class="src short"><a href="#v:findMin">findMin</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Maybe.html#t:Maybe">Maybe</a> (<a href="Data-PSQueue.html#t:Binding">Binding</a> k p)</li><li class="src short"><a href="#v:deleteMin">deleteMin</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p</li><li class="src short"><a href="#v:minView">minView</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Maybe.html#t:Maybe">Maybe</a> (<a href="Data-PSQueue.html#t:Binding">Binding</a> k p, <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p)</li><li class="src short"><a href="#v:atMost">atMost</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> [<a href="Data-PSQueue.html#t:Binding">Binding</a> k p]</li><li class="src short"><a href="#v:atMostRange">atMostRange</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => p -> (k, k) -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> [<a href="Data-PSQueue.html#t:Binding">Binding</a> k p]</li><li class="src short"><a href="#v:foldr">foldr</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => (<a href="Data-PSQueue.html#t:Binding">Binding</a> k p -> b -> b) -> b -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> b</li><li class="src short"><a href="#v:foldl">foldl</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => (b -> <a href="Data-PSQueue.html#t:Binding">Binding</a> k p -> b) -> b -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> b</li></ul></div><div id="interface"><h1 id="g:1">Binding Type</h1><div class="top"><p class="src"><span class="keyword">data</span> <a id="t:Binding" class="def">Binding</a> k p <a href="src/Data-PSQueue.html#Binding" class="link">Source</a> <a href="#t:Binding" class="selflink">#</a></p><div class="doc"><p><code>k :-> p</code> binds the key <code>k</code> with the priority <code>p</code>.</p></div><div class="subs constructors"><p class="caption">Constructors</p><table><tr><td class="src">k <a id="v::-45--62-" class="def">:-></a> p <span class="fixity">infix 0</span><span class="rightedge"></span></td><td class="doc empty"> </td></tr></table></div><div class="subs instances"><p id="control.i:Binding" class="caption collapser" onclick="toggleSection('i:Binding')">Instances</p><div id="section.i:Binding" class="show"><table><tr><td class="src clearfix"><span class="inst-left"><span id="control.i:id:Binding:Eq:1" class="instance expander" onclick="toggleSection('i:id:Binding:Eq:1')"></span> (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Eq.html#t:Eq">Eq</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Eq.html#t:Eq">Eq</a> p) => <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Eq.html#t:Eq">Eq</a> (<a href="Data-PSQueue.html#t:Binding">Binding</a> k p)</span> <a href="src/Data-PSQueue.html#line-78" class="link">Source</a> <a href="#t:Binding" class="selflink">#</a></td><td class="doc empty"> </td></tr><tr><td colspan="2"><div id="section.i:id:Binding:Eq:1" class="inst-details hide"><div class="subs methods"><p class="caption">Methods</p><p class="src"><a href="#v:-61--61-">(==)</a> :: <a href="Data-PSQueue.html#t:Binding">Binding</a> k p -> <a href="Data-PSQueue.html#t:Binding">Binding</a> k p -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Bool.html#t:Bool">Bool</a> <a href="#v:-61--61-" class="selflink">#</a></p><p class="src"><a href="#v:-47--61-">(/=)</a> :: <a href="Data-PSQueue.html#t:Binding">Binding</a> k p -> <a href="Data-PSQueue.html#t:Binding">Binding</a> k p -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Bool.html#t:Bool">Bool</a> <a href="#v:-47--61-" class="selflink">#</a></p></div></div></td></tr><tr><td class="src clearfix"><span class="inst-left"><span id="control.i:id:Binding:Ord:2" class="instance expander" onclick="toggleSection('i:id:Binding:Ord:2')"></span> (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> (<a href="Data-PSQueue.html#t:Binding">Binding</a> k p)</span> <a href="src/Data-PSQueue.html#line-78" class="link">Source</a> <a href="#t:Binding" class="selflink">#</a></td><td class="doc empty"> </td></tr><tr><td colspan="2"><div id="section.i:id:Binding:Ord:2" class="inst-details hide"><div class="subs methods"><p class="caption">Methods</p><p class="src"><a href="#v:compare">compare</a> :: <a href="Data-PSQueue.html#t:Binding">Binding</a> k p -> <a href="Data-PSQueue.html#t:Binding">Binding</a> k p -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ordering">Ordering</a> <a href="#v:compare" class="selflink">#</a></p><p class="src"><a href="#v:-60-">(<)</a> :: <a href="Data-PSQueue.html#t:Binding">Binding</a> k p -> <a href="Data-PSQueue.html#t:Binding">Binding</a> k p -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Bool.html#t:Bool">Bool</a> <a href="#v:-60-" class="selflink">#</a></p><p class="src"><a href="#v:-60--61-">(<=)</a> :: <a href="Data-PSQueue.html#t:Binding">Binding</a> k p -> <a href="Data-PSQueue.html#t:Binding">Binding</a> k p -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Bool.html#t:Bool">Bool</a> <a href="#v:-60--61-" class="selflink">#</a></p><p class="src"><a href="#v:-62-">(>)</a> :: <a href="Data-PSQueue.html#t:Binding">Binding</a> k p -> <a href="Data-PSQueue.html#t:Binding">Binding</a> k p -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Bool.html#t:Bool">Bool</a> <a href="#v:-62-" class="selflink">#</a></p><p class="src"><a href="#v:-62--61-">(>=)</a> :: <a href="Data-PSQueue.html#t:Binding">Binding</a> k p -> <a href="Data-PSQueue.html#t:Binding">Binding</a> k p -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Bool.html#t:Bool">Bool</a> <a href="#v:-62--61-" class="selflink">#</a></p><p class="src"><a href="#v:max">max</a> :: <a href="Data-PSQueue.html#t:Binding">Binding</a> k p -> <a href="Data-PSQueue.html#t:Binding">Binding</a> k p -> <a href="Data-PSQueue.html#t:Binding">Binding</a> k p <a href="#v:max" class="selflink">#</a></p><p class="src"><a href="#v:min">min</a> :: <a href="Data-PSQueue.html#t:Binding">Binding</a> k p -> <a href="Data-PSQueue.html#t:Binding">Binding</a> k p -> <a href="Data-PSQueue.html#t:Binding">Binding</a> k p <a href="#v:min" class="selflink">#</a></p></div></div></td></tr><tr><td class="src clearfix"><span class="inst-left"><span id="control.i:id:Binding:Read:3" class="instance expander" onclick="toggleSection('i:id:Binding:Read:3')"></span> (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Text-Read.html#t:Read">Read</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Text-Read.html#t:Read">Read</a> p) => <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Text-Read.html#t:Read">Read</a> (<a href="Data-PSQueue.html#t:Binding">Binding</a> k p)</span> <a href="src/Data-PSQueue.html#line-78" class="link">Source</a> <a href="#t:Binding" class="selflink">#</a></td><td class="doc empty"> </td></tr><tr><td colspan="2"><div id="section.i:id:Binding:Read:3" class="inst-details hide"><div class="subs methods"><p class="caption">Methods</p><p class="src"><a href="#v:readsPrec">readsPrec</a> :: <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Int.html#t:Int">Int</a> -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Text-ParserCombinators-ReadP.html#t:ReadS">ReadS</a> (<a href="Data-PSQueue.html#t:Binding">Binding</a> k p) <a href="#v:readsPrec" class="selflink">#</a></p><p class="src"><a href="#v:readList">readList</a> :: <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Text-ParserCombinators-ReadP.html#t:ReadS">ReadS</a> [<a href="Data-PSQueue.html#t:Binding">Binding</a> k p] <a href="#v:readList" class="selflink">#</a></p><p class="src"><a href="#v:readPrec">readPrec</a> :: <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Text-ParserCombinators-ReadPrec.html#t:ReadPrec">ReadPrec</a> (<a href="Data-PSQueue.html#t:Binding">Binding</a> k p) <a href="#v:readPrec" class="selflink">#</a></p><p class="src"><a href="#v:readListPrec">readListPrec</a> :: <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Text-ParserCombinators-ReadPrec.html#t:ReadPrec">ReadPrec</a> [<a href="Data-PSQueue.html#t:Binding">Binding</a> k p] <a href="#v:readListPrec" class="selflink">#</a></p></div></div></td></tr><tr><td class="src clearfix"><span class="inst-left"><span id="control.i:id:Binding:Show:4" class="instance expander" onclick="toggleSection('i:id:Binding:Show:4')"></span> (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Text-Show.html#t:Show">Show</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Text-Show.html#t:Show">Show</a> p) => <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Text-Show.html#t:Show">Show</a> (<a href="Data-PSQueue.html#t:Binding">Binding</a> k p)</span> <a href="src/Data-PSQueue.html#line-78" class="link">Source</a> <a href="#t:Binding" class="selflink">#</a></td><td class="doc empty"> </td></tr><tr><td colspan="2"><div id="section.i:id:Binding:Show:4" class="inst-details hide"><div class="subs methods"><p class="caption">Methods</p><p class="src"><a href="#v:showsPrec">showsPrec</a> :: <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Int.html#t:Int">Int</a> -> <a href="Data-PSQueue.html#t:Binding">Binding</a> k p -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Text-Show.html#t:ShowS">ShowS</a> <a href="#v:showsPrec" class="selflink">#</a></p><p class="src"><a href="#v:show">show</a> :: <a href="Data-PSQueue.html#t:Binding">Binding</a> k p -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-String.html#t:String">String</a> <a href="#v:show" class="selflink">#</a></p><p class="src"><a href="#v:showList">showList</a> :: [<a href="Data-PSQueue.html#t:Binding">Binding</a> k p] -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Text-Show.html#t:ShowS">ShowS</a> <a href="#v:showList" class="selflink">#</a></p></div></div></td></tr></table></div></div></div><div class="top"><p class="src"><a id="v:key" class="def">key</a> :: <a href="Data-PSQueue.html#t:Binding">Binding</a> k p -> k <a href="src/Data-PSQueue.html#key" class="link">Source</a> <a href="#v:key" class="selflink">#</a></p><div class="doc"><p>The key of a binding</p></div></div><div class="top"><p class="src"><a id="v:prio" class="def">prio</a> :: <a href="Data-PSQueue.html#t:Binding">Binding</a> k p -> p <a href="src/Data-PSQueue.html#prio" class="link">Source</a> <a href="#v:prio" class="selflink">#</a></p><div class="doc"><p>The priority of a binding</p></div></div><h1 id="g:2">Priority Search Queue Type</h1><div class="top"><p class="src"><span class="keyword">data</span> <a id="t:PSQ" class="def">PSQ</a> k p <a href="src/Data-PSQueue.html#PSQ" class="link">Source</a> <a href="#t:PSQ" class="selflink">#</a></p><div class="doc"><p>A mapping from keys <code>k</code> to priorites <code>p</code>. </p></div><div class="subs instances"><p id="control.i:PSQ" class="caption collapser" onclick="toggleSection('i:PSQ')">Instances</p><div id="section.i:PSQ" class="show"><table><tr><td class="src clearfix"><span class="inst-left"><span id="control.i:id:PSQ:Show:1" class="instance expander" onclick="toggleSection('i:id:PSQ:Show:1')"></span> (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Text-Show.html#t:Show">Show</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Text-Show.html#t:Show">Show</a> p, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Text-Show.html#t:Show">Show</a> (<a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p)</span> <a href="src/Data-PSQueue.html#line-96" class="link">Source</a> <a href="#t:PSQ" class="selflink">#</a></td><td class="doc empty"> </td></tr><tr><td colspan="2"><div id="section.i:id:PSQ:Show:1" class="inst-details hide"><div class="subs methods"><p class="caption">Methods</p><p class="src"><a href="#v:showsPrec">showsPrec</a> :: <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Int.html#t:Int">Int</a> -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Text-Show.html#t:ShowS">ShowS</a> <a href="#v:showsPrec" class="selflink">#</a></p><p class="src"><a href="#v:show">show</a> :: <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-String.html#t:String">String</a> <a href="#v:show" class="selflink">#</a></p><p class="src"><a href="#v:showList">showList</a> :: [<a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p] -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Text-Show.html#t:ShowS">ShowS</a> <a href="#v:showList" class="selflink">#</a></p></div></div></td></tr></table></div></div></div><h1 id="g:3">Query</h1><div class="top"><p class="src"><a id="v:size" class="def">size</a> :: <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Int.html#t:Int">Int</a> <a href="src/Data-PSQueue.html#size" class="link">Source</a> <a href="#v:size" class="selflink">#</a></p><div class="doc"><p><em>O(1)</em> The number of bindings in a queue.</p></div></div><div class="top"><p class="src"><a id="v:null" class="def">null</a> :: <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Bool.html#t:Bool">Bool</a> <a href="src/Data-PSQueue.html#null" class="link">Source</a> <a href="#v:null" class="selflink">#</a></p><div class="doc"><p><em>O(1)</em> True if the queue is empty.</p></div></div><div class="top"><p class="src"><a id="v:lookup" class="def">lookup</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => k -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Maybe.html#t:Maybe">Maybe</a> p <a href="src/Data-PSQueue.html#lookup" class="link">Source</a> <a href="#v:lookup" class="selflink">#</a></p><div class="doc"><p><em>O(log n)</em> The priority of a given key, or Nothing if the key is not
bound.</p></div></div><h1 id="g:4">Construction</h1><div class="top"><p class="src"><a id="v:empty" class="def">empty</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p <a href="src/Data-PSQueue.html#empty" class="link">Source</a> <a href="#v:empty" class="selflink">#</a></p></div><div class="top"><p class="src"><a id="v:singleton" class="def">singleton</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => k -> p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p <a href="src/Data-PSQueue.html#singleton" class="link">Source</a> <a href="#v:singleton" class="selflink">#</a></p><div class="doc"><p>O(1) Build a queue with one binding.</p></div></div><h1 id="g:5">Insertion</h1><div class="top"><p class="src"><a id="v:insert" class="def">insert</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => k -> p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p <a href="src/Data-PSQueue.html#insert" class="link">Source</a> <a href="#v:insert" class="selflink">#</a></p><div class="doc"><p><em>O(log n)</em> Insert a binding into the queue.</p></div></div><div class="top"><p class="src"><a id="v:insertWith" class="def">insertWith</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => (p -> p -> p) -> k -> p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p <a href="src/Data-PSQueue.html#insertWith" class="link">Source</a> <a href="#v:insertWith" class="selflink">#</a></p><div class="doc"><p><em>O(log n)</em> Insert a binding with a combining function. </p></div></div><h1 id="g:6">Delete/Update </h1><div class="top"><p class="src"><a id="v:delete" class="def">delete</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => k -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p <a href="src/Data-PSQueue.html#delete" class="link">Source</a> <a href="#v:delete" class="selflink">#</a></p><div class="doc"><p><em>O(log n)</em> Remove a binding from the queue.</p></div></div><div class="top"><p class="src"><a id="v:adjust" class="def">adjust</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k) => (p -> p) -> k -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p <a href="src/Data-PSQueue.html#adjust" class="link">Source</a> <a href="#v:adjust" class="selflink">#</a></p><div class="doc"><p><em>O(log n)</em> Adjust the priority of a key.</p></div></div><div class="top"><p class="src"><a id="v:adjustWithKey" class="def">adjustWithKey</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => (k -> p -> p) -> k -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p <a href="src/Data-PSQueue.html#adjustWithKey" class="link">Source</a> <a href="#v:adjustWithKey" class="selflink">#</a></p><div class="doc"><p><em>O(log n)</em> Adjust the priority of a key.</p></div></div><div class="top"><p class="src"><a id="v:update" class="def">update</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => (p -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Maybe.html#t:Maybe">Maybe</a> p) -> k -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p <a href="src/Data-PSQueue.html#update" class="link">Source</a> <a href="#v:update" class="selflink">#</a></p><div class="doc"><p><em>O(log n)</em> The expression (<code>update f k q</code>) updates the
priority <code>p</code> bound <code>k</code> (if it is in the queue). If (<code>f p</code>) is <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Maybe.html#v:Nothing">Nothing</a></code>,
the binding is deleted. If it is (<code><code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Maybe.html#v:Just">Just</a></code> z</code>), the key <code>k</code> is bound
to the new priority <code>z</code>.</p></div></div><div class="top"><p class="src"><a id="v:updateWithKey" class="def">updateWithKey</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => (k -> p -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Maybe.html#t:Maybe">Maybe</a> p) -> k -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p <a href="src/Data-PSQueue.html#updateWithKey" class="link">Source</a> <a href="#v:updateWithKey" class="selflink">#</a></p><div class="doc"><p><em>O(log n)</em>. The expression (<code>updateWithKey f k q</code>) updates the
priority <code>p</code> bound <code>k</code> (if it is in the queue). If (<code>f k p</code>) is <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Maybe.html#v:Nothing">Nothing</a></code>,
the binding is deleted. If it is (<code><code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Maybe.html#v:Just">Just</a></code> z</code>), the key <code>k</code> is bound
to the new priority <code>z</code>.</p></div></div><div class="top"><p class="src"><a id="v:alter" class="def">alter</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Maybe.html#t:Maybe">Maybe</a> p -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Maybe.html#t:Maybe">Maybe</a> p) -> k -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p <a href="src/Data-PSQueue.html#alter" class="link">Source</a> <a href="#v:alter" class="selflink">#</a></p><div class="doc"><p><em>O(log n)</em>. The expression (<code><code><a href="Data-PSQueue.html#v:alter">alter</a></code> f k q</code>) alters the priority <code>p</code> bound to <code>k</code>, or absence thereof.
alter can be used to insert, delete, or update a priority in a queue.</p></div></div><h1 id="g:7">Conversion</h1><div class="top"><p class="src"><a id="v:keys" class="def">keys</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> [k] <a href="src/Data-PSQueue.html#keys" class="link">Source</a> <a href="#v:keys" class="selflink">#</a></p><div class="doc"><p><em>O(n)</em> The keys of a priority queue</p></div></div><div class="top"><p class="src"><a id="v:toList" class="def">toList</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> [<a href="Data-PSQueue.html#t:Binding">Binding</a> k p] <a href="src/Data-PSQueue.html#toList" class="link">Source</a> <a href="#v:toList" class="selflink">#</a></p><div class="doc"><p><em>O(n)</em> Convert a queue to a list.</p></div></div><div class="top"><p class="src"><a id="v:toAscList" class="def">toAscList</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> [<a href="Data-PSQueue.html#t:Binding">Binding</a> k p] <a href="src/Data-PSQueue.html#toAscList" class="link">Source</a> <a href="#v:toAscList" class="selflink">#</a></p><div class="doc"><p><em>O(n)</em> Convert a queue to a list in ascending order of keys.</p></div></div><div class="top"><p class="src"><a id="v:toDescList" class="def">toDescList</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> [<a href="Data-PSQueue.html#t:Binding">Binding</a> k p] <a href="src/Data-PSQueue.html#toDescList" class="link">Source</a> <a href="#v:toDescList" class="selflink">#</a></p><div class="doc"><p><em>O(n)</em> Convert a queue to a list in descending order of keys.</p></div></div><div class="top"><p class="src"><a id="v:fromList" class="def">fromList</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => [<a href="Data-PSQueue.html#t:Binding">Binding</a> k p] -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p <a href="src/Data-PSQueue.html#fromList" class="link">Source</a> <a href="#v:fromList" class="selflink">#</a></p><div class="doc"><p><em>O(n log n)</em> Build a queue from a list of bindings.</p></div></div><div class="top"><p class="src"><a id="v:fromAscList" class="def">fromAscList</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => [<a href="Data-PSQueue.html#t:Binding">Binding</a> k p] -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p <a href="src/Data-PSQueue.html#fromAscList" class="link">Source</a> <a href="#v:fromAscList" class="selflink">#</a></p><div class="doc"><p><em>O(n)</em> Build a queue from a list of bindings in order of
ascending keys. The precondition that the keys are ascending is not checked.</p></div></div><div class="top"><p class="src"><a id="v:fromDistinctAscList" class="def">fromDistinctAscList</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => [<a href="Data-PSQueue.html#t:Binding">Binding</a> k p] -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p <a href="src/Data-PSQueue.html#fromDistinctAscList" class="link">Source</a> <a href="#v:fromDistinctAscList" class="selflink">#</a></p><div class="doc"><p><em>O(n)</em> Build a queue from a list of distinct bindings in order of
ascending keys. The precondition that keys are distinct and ascending is not checked.</p></div></div><h1 id="g:8">Priority Queue</h1><div class="top"><p class="src"><a id="v:findMin" class="def">findMin</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Maybe.html#t:Maybe">Maybe</a> (<a href="Data-PSQueue.html#t:Binding">Binding</a> k p) <a href="src/Data-PSQueue.html#findMin" class="link">Source</a> <a href="#v:findMin" class="selflink">#</a></p><div class="doc"><p><em>O(1)</em> The binding with the lowest priority.</p></div></div><div class="top"><p class="src"><a id="v:deleteMin" class="def">deleteMin</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p <a href="src/Data-PSQueue.html#deleteMin" class="link">Source</a> <a href="#v:deleteMin" class="selflink">#</a></p><div class="doc"><p><em>O(log n)</em> Remove the binding with the lowest priority.</p></div></div><div class="top"><p class="src"><a id="v:minView" class="def">minView</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Maybe.html#t:Maybe">Maybe</a> (<a href="Data-PSQueue.html#t:Binding">Binding</a> k p, <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p) <a href="src/Data-PSQueue.html#minView" class="link">Source</a> <a href="#v:minView" class="selflink">#</a></p><div class="doc"><p><em>O(log n)</em> Retrieve the binding with the least priority, and the rest of
the queue stripped of that binding. </p></div></div><div class="top"><p class="src"><a id="v:atMost" class="def">atMost</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => p -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> [<a href="Data-PSQueue.html#t:Binding">Binding</a> k p] <a href="src/Data-PSQueue.html#atMost" class="link">Source</a> <a href="#v:atMost" class="selflink">#</a></p><div class="doc"><p><em>O(r(log n - log r)</em> <code>atMost p q</code> is a list of all the bindings in <code>q</code> with
priority less than <code>p</code>, in order of ascending keys.
Effectively, </p><pre> atMost p' q = filter (\(k:->p) -> p<=p') . toList
</pre></div></div><div class="top"><p class="src"><a id="v:atMostRange" class="def">atMostRange</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => p -> (k, k) -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> [<a href="Data-PSQueue.html#t:Binding">Binding</a> k p] <a href="src/Data-PSQueue.html#atMostRange" class="link">Source</a> <a href="#v:atMostRange" class="selflink">#</a></p><div class="doc"><p><em>O(r(log n - log r))</em> <code>atMostRange p (l,u) q</code> is a list of all the bindings in
<code>q</code> with a priority less than <code>p</code> and a key in the range <code>(l,u)</code> inclusive.
Effectively,</p><pre> atMostRange p' (l,u) q = filter (\(k:->p) -> l<=k && k<=u ) . <code><a href="Data-PSQueue.html#v:atMost">atMost</a></code> p'
</pre></div></div><h1 id="g:9">Fold</h1><div class="top"><p class="src"><a id="v:foldr" class="def">foldr</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => (<a href="Data-PSQueue.html#t:Binding">Binding</a> k p -> b -> b) -> b -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> b <a href="src/Data-PSQueue.html#foldr" class="link">Source</a> <a href="#v:foldr" class="selflink">#</a></p><div class="doc"><p>Right fold over the bindings in the queue, in key order.</p></div></div><div class="top"><p class="src"><a id="v:foldl" class="def">foldl</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.9.0.0/Data-Ord.html#t:Ord">Ord</a> p) => (b -> <a href="Data-PSQueue.html#t:Binding">Binding</a> k p -> b) -> b -> <a href="Data-PSQueue.html#t:PSQ">PSQ</a> k p -> b <a href="src/Data-PSQueue.html#foldl" class="link">Source</a> <a href="#v:foldl" class="selflink">#</a></p><div class="doc"><p>Left fold over the bindings in the queue, in key order.</p></div></div></div></div><div id="footer"><p>Produced by <a href="http://www.haskell.org/haddock/">Haddock</a> version 2.17.2</p></div></body></html>
|