<!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.IntSet</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-IntSet.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">containers-0.4.2.1: Assorted concrete container types</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>libraries@haskell.org</td></tr><tr><th>Safe Haskell</th><td>Trustworthy</td></tr></table><p class="caption">Data.IntSet</p></div><div id="table-of-contents"><p class="caption">Contents</p><ul><li><a href="#g:1">Set type
</a></li><li><a href="#g:2">Operators
</a></li><li><a href="#g:3">Query
</a></li><li><a href="#g:4">Construction
</a></li><li><a href="#g:5">Combine
</a></li><li><a href="#g:6">Filter
</a></li><li><a href="#g:7">Map
</a></li><li><a href="#g:8">Folds
</a><ul><li><a href="#g:9">Strict folds
</a></li><li><a href="#g:10">Legacy folds
</a></li></ul></li><li><a href="#g:11">Min/Max
</a></li><li><a href="#g:12">Conversion
</a><ul><li><a href="#g:13">List
</a></li><li><a href="#g:14">Ordered list
</a></li></ul></li><li><a href="#g:15">Debugging
</a></li></ul></div><div id="description"><p class="caption">Description</p><div class="doc"><p>An efficient implementation of integer sets.
</p><p>Since many function names (but not the type name) clash with
<a href="../base-4.5.1.0/Prelude.html">Prelude</a> names, this module is usually imported <code>qualified</code>, e.g.
</p><pre> import Data.IntSet (IntSet)
import qualified Data.IntSet as IntSet
</pre><p>The implementation is based on <em>big-endian patricia trees</em>. This data
structure performs especially well on binary operations like <code><a href="Data-IntSet.html#v:union">union</a></code>
and <code><a href="Data-IntSet.html#v:intersection">intersection</a></code>. However, my benchmarks show that it is also
(much) faster on insertions and deletions when compared to a generic
size-balanced set implementation (see <a href="Data-Set.html">Data.Set</a>).
</p><ul><li> Chris Okasaki and Andy Gill, "<em>Fast Mergeable Integer Maps</em>",
Workshop on ML, September 1998, pages 77-86,
<a href="http://citeseer.ist.psu.edu/okasaki98fast.html">http://citeseer.ist.psu.edu/okasaki98fast.html</a>
</li><li> D.R. Morrison, "/PATRICIA -- Practical Algorithm To Retrieve
Information Coded In Alphanumeric/", Journal of the ACM, 15(4),
October 1968, pages 514-534.
</li></ul><p>Many operations have a worst-case complexity of <em>O(min(n,W))</em>.
This means that the operation can become linear in the number of
elements with a maximum of <em>W</em> -- the number of bits in an <code><a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a></code>
(32 or 64).
</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:IntSet">IntSet</a> </li><li class="src short"><a href="#v:-92--92-">(\\)</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a></li><li class="src short"><a href="#v:null">null</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></li><li class="src short"><a href="#v:size">size</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a></li><li class="src short"><a href="#v:member">member</a> :: <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></li><li class="src short"><a href="#v:notMember">notMember</a> :: <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></li><li class="src short"><a href="#v:isSubsetOf">isSubsetOf</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></li><li class="src short"><a href="#v:isProperSubsetOf">isProperSubsetOf</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></li><li class="src short"><a href="#v:empty">empty</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a></li><li class="src short"><a href="#v:singleton">singleton</a> :: <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a></li><li class="src short"><a href="#v:insert">insert</a> :: <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a></li><li class="src short"><a href="#v:delete">delete</a> :: <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a></li><li class="src short"><a href="#v:union">union</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a></li><li class="src short"><a href="#v:unions">unions</a> :: [<a href="Data-IntSet.html#t:IntSet">IntSet</a>] -> <a href="Data-IntSet.html#t:IntSet">IntSet</a></li><li class="src short"><a href="#v:difference">difference</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a></li><li class="src short"><a href="#v:intersection">intersection</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a></li><li class="src short"><a href="#v:filter">filter</a> :: (<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a></li><li class="src short"><a href="#v:partition">partition</a> :: (<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> (<a href="Data-IntSet.html#t:IntSet">IntSet</a>, <a href="Data-IntSet.html#t:IntSet">IntSet</a>)</li><li class="src short"><a href="#v:split">split</a> :: <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> (<a href="Data-IntSet.html#t:IntSet">IntSet</a>, <a href="Data-IntSet.html#t:IntSet">IntSet</a>)</li><li class="src short"><a href="#v:splitMember">splitMember</a> :: <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> (<a href="Data-IntSet.html#t:IntSet">IntSet</a>, <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>, <a href="Data-IntSet.html#t:IntSet">IntSet</a>)</li><li class="src short"><a href="#v:map">map</a> :: (<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>) -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a></li><li class="src short"><a href="#v:foldr">foldr</a> :: (<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> b -> b) -> b -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> b</li><li class="src short"><a href="#v:foldl">foldl</a> :: (a -> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> a) -> a -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> a</li><li class="src short"><a href="#v:foldr-39-">foldr'</a> :: (<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> b -> b) -> b -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> b</li><li class="src short"><a href="#v:foldl-39-">foldl'</a> :: (a -> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> a) -> a -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> a</li><li class="src short"><a href="#v:fold">fold</a> :: (<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> b -> b) -> b -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> b</li><li class="src short"><a href="#v:findMin">findMin</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a></li><li class="src short"><a href="#v:findMax">findMax</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a></li><li class="src short"><a href="#v:deleteMin">deleteMin</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a></li><li class="src short"><a href="#v:deleteMax">deleteMax</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a></li><li class="src short"><a href="#v:deleteFindMin">deleteFindMin</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> (<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>, <a href="Data-IntSet.html#t:IntSet">IntSet</a>)</li><li class="src short"><a href="#v:deleteFindMax">deleteFindMax</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> (<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>, <a href="Data-IntSet.html#t:IntSet">IntSet</a>)</li><li class="src short"><a href="#v:maxView">maxView</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> (<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>, <a href="Data-IntSet.html#t:IntSet">IntSet</a>)</li><li class="src short"><a href="#v:minView">minView</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> (<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>, <a href="Data-IntSet.html#t:IntSet">IntSet</a>)</li><li class="src short"><a href="#v:elems">elems</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> [<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>]</li><li class="src short"><a href="#v:toList">toList</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> [<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>]</li><li class="src short"><a href="#v:fromList">fromList</a> :: [<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>] -> <a href="Data-IntSet.html#t:IntSet">IntSet</a></li><li class="src short"><a href="#v:toAscList">toAscList</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> [<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>]</li><li class="src short"><a href="#v:fromAscList">fromAscList</a> :: [<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>] -> <a href="Data-IntSet.html#t:IntSet">IntSet</a></li><li class="src short"><a href="#v:fromDistinctAscList">fromDistinctAscList</a> :: [<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>] -> <a href="Data-IntSet.html#t:IntSet">IntSet</a></li><li class="src short"><a href="#v:showTree">showTree</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="../base-4.5.1.0/Data-String.html#t:String">String</a></li><li class="src short"><a href="#v:showTreeWith">showTreeWith</a> :: <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a> -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="../base-4.5.1.0/Data-String.html#t:String">String</a></li></ul></div><div id="interface"><h1 id="g:1">Set type
</h1><div class="top"><p class="src"><span class="keyword">data</span> <a name="t:IntSet" class="def">IntSet</a> </p><div class="doc"><p>A set of integers.
</p></div><div class="subs instances"><p id="control.i:IntSet" class="caption collapser" onclick="toggleSection('i:IntSet')">Instances</p><div id="section.i:IntSet" class="show"><table><tr><td class="src"><a href="../base-4.5.1.0/Data-Eq.html#t:Eq">Eq</a> <a href="Data-IntSet.html#t:IntSet">IntSet</a></td><td class="doc empty"> </td></tr><tr><td class="src"><a href="../base-4.5.1.0/Data-Data.html#t:Data">Data</a> <a href="Data-IntSet.html#t:IntSet">IntSet</a></td><td class="doc empty"> </td></tr><tr><td class="src"><a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> <a href="Data-IntSet.html#t:IntSet">IntSet</a></td><td class="doc empty"> </td></tr><tr><td class="src"><a href="../base-4.5.1.0/Text-Read.html#t:Read">Read</a> <a href="Data-IntSet.html#t:IntSet">IntSet</a></td><td class="doc empty"> </td></tr><tr><td class="src"><a href="../base-4.5.1.0/Text-Show.html#t:Show">Show</a> <a href="Data-IntSet.html#t:IntSet">IntSet</a></td><td class="doc empty"> </td></tr><tr><td class="src"><a href="../base-4.5.1.0/Data-Typeable-Internal.html#t:Typeable">Typeable</a> <a href="Data-IntSet.html#t:IntSet">IntSet</a></td><td class="doc empty"> </td></tr><tr><td class="src"><a href="../base-4.5.1.0/Data-Monoid.html#t:Monoid">Monoid</a> <a href="Data-IntSet.html#t:IntSet">IntSet</a></td><td class="doc empty"> </td></tr><tr><td class="src"><a href="../deepseq-1.3.0.0/Control-DeepSeq.html#t:NFData">NFData</a> <a href="Data-IntSet.html#t:IntSet">IntSet</a></td><td class="doc empty"> </td></tr></table></div></div></div><h1 id="g:2">Operators
</h1><div class="top"><p class="src"><a name="v:-92--92-" class="def">(\\)</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a></p><div class="doc"><p><em>O(n+m)</em>. See <code><a href="Data-IntSet.html#v:difference">difference</a></code>.
</p></div></div><h1 id="g:3">Query
</h1><div class="top"><p class="src"><a name="v:null" class="def">null</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></p><div class="doc"><p><em>O(1)</em>. Is the set empty?
</p></div></div><div class="top"><p class="src"><a name="v:size" class="def">size</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a></p><div class="doc"><p><em>O(n)</em>. Cardinality of the set.
</p></div></div><div class="top"><p class="src"><a name="v:member" class="def">member</a> :: <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></p><div class="doc"><p><em>O(min(n,W))</em>. Is the value a member of the set?
</p></div></div><div class="top"><p class="src"><a name="v:notMember" class="def">notMember</a> :: <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></p><div class="doc"><p><em>O(min(n,W))</em>. Is the element not in the set?
</p></div></div><div class="top"><p class="src"><a name="v:isSubsetOf" class="def">isSubsetOf</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></p><div class="doc"><p><em>O(n+m)</em>. Is this a subset?
<code>(s1 <code><a href="Data-IntSet.html#v:isSubsetOf">isSubsetOf</a></code> s2)</code> tells whether <code>s1</code> is a subset of <code>s2</code>.
</p></div></div><div class="top"><p class="src"><a name="v:isProperSubsetOf" class="def">isProperSubsetOf</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></p><div class="doc"><p><em>O(n+m)</em>. Is this a proper subset? (ie. a subset but not equal).
</p></div></div><h1 id="g:4">Construction
</h1><div class="top"><p class="src"><a name="v:empty" class="def">empty</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a></p><div class="doc"><p><em>O(1)</em>. The empty set.
</p></div></div><div class="top"><p class="src"><a name="v:singleton" class="def">singleton</a> :: <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a></p><div class="doc"><p><em>O(1)</em>. A set of one element.
</p></div></div><div class="top"><p class="src"><a name="v:insert" class="def">insert</a> :: <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a></p><div class="doc"><p><em>O(min(n,W))</em>. Add a value to the set. When the value is already
an element of the set, it is replaced by the new one, ie. <code><a href="Data-IntSet.html#v:insert">insert</a></code>
is left-biased.
</p></div></div><div class="top"><p class="src"><a name="v:delete" class="def">delete</a> :: <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a></p><div class="doc"><p><em>O(min(n,W))</em>. Delete a value in the set. Returns the
original set when the value was not present.
</p></div></div><h1 id="g:5">Combine
</h1><div class="top"><p class="src"><a name="v:union" class="def">union</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a></p><div class="doc"><p><em>O(n+m)</em>. The union of two sets.
</p></div></div><div class="top"><p class="src"><a name="v:unions" class="def">unions</a> :: [<a href="Data-IntSet.html#t:IntSet">IntSet</a>] -> <a href="Data-IntSet.html#t:IntSet">IntSet</a></p><div class="doc"><p>The union of a list of sets.
</p></div></div><div class="top"><p class="src"><a name="v:difference" class="def">difference</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a></p><div class="doc"><p><em>O(n+m)</em>. Difference between two sets.
</p></div></div><div class="top"><p class="src"><a name="v:intersection" class="def">intersection</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a></p><div class="doc"><p><em>O(n+m)</em>. The intersection of two sets.
</p></div></div><h1 id="g:6">Filter
</h1><div class="top"><p class="src"><a name="v:filter" class="def">filter</a> :: (<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a></p><div class="doc"><p><em>O(n)</em>. Filter all elements that satisfy some predicate.
</p></div></div><div class="top"><p class="src"><a name="v:partition" class="def">partition</a> :: (<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> (<a href="Data-IntSet.html#t:IntSet">IntSet</a>, <a href="Data-IntSet.html#t:IntSet">IntSet</a>)</p><div class="doc"><p><em>O(n)</em>. partition the set according to some predicate.
</p></div></div><div class="top"><p class="src"><a name="v:split" class="def">split</a> :: <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> (<a href="Data-IntSet.html#t:IntSet">IntSet</a>, <a href="Data-IntSet.html#t:IntSet">IntSet</a>)</p><div class="doc"><p><em>O(min(n,W))</em>. The expression (<code><code><a href="Data-IntSet.html#v:split">split</a></code> x set</code>) is a pair <code>(set1,set2)</code>
where <code>set1</code> comprises the elements of <code>set</code> less than <code>x</code> and <code>set2</code>
comprises the elements of <code>set</code> greater than <code>x</code>.
</p><pre> split 3 (fromList [1..5]) == (fromList [1,2], fromList [4,5])
</pre></div></div><div class="top"><p class="src"><a name="v:splitMember" class="def">splitMember</a> :: <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> (<a href="Data-IntSet.html#t:IntSet">IntSet</a>, <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>, <a href="Data-IntSet.html#t:IntSet">IntSet</a>)</p><div class="doc"><p><em>O(min(n,W))</em>. Performs a <code><a href="Data-IntSet.html#v:split">split</a></code> but also returns whether the pivot
element was found in the original set.
</p></div></div><h1 id="g:7">Map
</h1><div class="top"><p class="src"><a name="v:map" class="def">map</a> :: (<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>) -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a></p><div class="doc"><p><em>O(n*min(n,W))</em>.
<code><code><a href="Data-IntSet.html#v:map">map</a></code> f s</code> is the set obtained by applying <code>f</code> to each element of <code>s</code>.
</p><p>It's worth noting that the size of the result may be smaller if,
for some <code>(x,y)</code>, <code>x /= y && f x == f y</code>
</p></div></div><h1 id="g:8">Folds
</h1><div class="top"><p class="src"><a name="v:foldr" class="def">foldr</a> :: (<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> b -> b) -> b -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> b</p><div class="doc"><p><em>O(n)</em>. Fold the elements in the set using the given right-associative
binary operator, such that <code><code><a href="Data-IntSet.html#v:foldr">foldr</a></code> f z == <code><a href="../base-4.5.1.0/Prelude.html#v:foldr">foldr</a></code> f z . <code><a href="Data-IntSet.html#v:toAscList">toAscList</a></code></code>.
</p><p>For example,
</p><pre> toAscList set = foldr (:) [] set
</pre></div></div><div class="top"><p class="src"><a name="v:foldl" class="def">foldl</a> :: (a -> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> a) -> a -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> a</p><div class="doc"><p><em>O(n)</em>. Fold the elements in the set using the given left-associative
binary operator, such that <code><code><a href="Data-IntSet.html#v:foldl">foldl</a></code> f z == <code><a href="../base-4.5.1.0/Prelude.html#v:foldl">foldl</a></code> f z . <code><a href="Data-IntSet.html#v:toAscList">toAscList</a></code></code>.
</p><p>For example,
</p><pre> toDescList set = foldl (flip (:)) [] set
</pre></div></div><h2 id="g:9">Strict folds
</h2><div class="top"><p class="src"><a name="v:foldr-39-" class="def">foldr'</a> :: (<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> b -> b) -> b -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> b</p><div class="doc"><p><em>O(n)</em>. A strict version of <code><a href="Data-IntSet.html#v:foldr">foldr</a></code>. Each application of the operator is
evaluated before using the result in the next application. This
function is strict in the starting value.
</p></div></div><div class="top"><p class="src"><a name="v:foldl-39-" class="def">foldl'</a> :: (a -> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> a) -> a -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> a</p><div class="doc"><p><em>O(n)</em>. A strict version of <code><a href="Data-IntSet.html#v:foldl">foldl</a></code>. Each application of the operator is
evaluated before using the result in the next application. This
function is strict in the starting value.
</p></div></div><h2 id="g:10">Legacy folds
</h2><div class="top"><p class="src"><a name="v:fold" class="def">fold</a> :: (<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a> -> b -> b) -> b -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> b</p><div class="doc"><p><em>O(n)</em>. Fold the elements in the set using the given right-associative
binary operator. This function is an equivalent of <code><a href="Data-IntSet.html#v:foldr">foldr</a></code> and is present
for compatibility only.
</p><p><em>Please note that fold will be deprecated in the future and removed.</em>
</p></div></div><h1 id="g:11">Min/Max
</h1><div class="top"><p class="src"><a name="v:findMin" class="def">findMin</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a></p><div class="doc"><p><em>O(min(n,W))</em>. The minimal element of the set.
</p></div></div><div class="top"><p class="src"><a name="v:findMax" class="def">findMax</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a></p><div class="doc"><p><em>O(min(n,W))</em>. The maximal element of a set.
</p></div></div><div class="top"><p class="src"><a name="v:deleteMin" class="def">deleteMin</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a></p><div class="doc"><p><em>O(min(n,W))</em>. Delete the minimal element.
</p></div></div><div class="top"><p class="src"><a name="v:deleteMax" class="def">deleteMax</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a></p><div class="doc"><p><em>O(min(n,W))</em>. Delete the maximal element.
</p></div></div><div class="top"><p class="src"><a name="v:deleteFindMin" class="def">deleteFindMin</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> (<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>, <a href="Data-IntSet.html#t:IntSet">IntSet</a>)</p><div class="doc"><p><em>O(min(n,W))</em>. Delete and find the minimal element.
</p><pre> deleteFindMin set = (findMin set, deleteMin set)
</pre></div></div><div class="top"><p class="src"><a name="v:deleteFindMax" class="def">deleteFindMax</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> (<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>, <a href="Data-IntSet.html#t:IntSet">IntSet</a>)</p><div class="doc"><p><em>O(min(n,W))</em>. Delete and find the maximal element.
</p><pre> deleteFindMax set = (findMax set, deleteMax set)
</pre></div></div><div class="top"><p class="src"><a name="v:maxView" class="def">maxView</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> (<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>, <a href="Data-IntSet.html#t:IntSet">IntSet</a>)</p><div class="doc"><p><em>O(min(n,W))</em>. Retrieves the maximal key of the set, and the set
stripped of that element, or <code><a href="../base-4.5.1.0/Data-Maybe.html#v:Nothing">Nothing</a></code> if passed an empty set.
</p></div></div><div class="top"><p class="src"><a name="v:minView" class="def">minView</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> (<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>, <a href="Data-IntSet.html#t:IntSet">IntSet</a>)</p><div class="doc"><p><em>O(min(n,W))</em>. Retrieves the minimal key of the set, and the set
stripped of that element, or <code><a href="../base-4.5.1.0/Data-Maybe.html#v:Nothing">Nothing</a></code> if passed an empty set.
</p></div></div><h1 id="g:12">Conversion
</h1><h2 id="g:13">List
</h2><div class="top"><p class="src"><a name="v:elems" class="def">elems</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> [<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>]</p><div class="doc"><p><em>O(n)</em>. The elements of a set. (For sets, this is equivalent to toList)
</p></div></div><div class="top"><p class="src"><a name="v:toList" class="def">toList</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> [<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>]</p><div class="doc"><p><em>O(n)</em>. Convert the set to a list of elements.
</p></div></div><div class="top"><p class="src"><a name="v:fromList" class="def">fromList</a> :: [<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>] -> <a href="Data-IntSet.html#t:IntSet">IntSet</a></p><div class="doc"><p><em>O(n*min(n,W))</em>. Create a set from a list of integers.
</p></div></div><h2 id="g:14">Ordered list
</h2><div class="top"><p class="src"><a name="v:toAscList" class="def">toAscList</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> [<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>]</p><div class="doc"><p><em>O(n)</em>. Convert the set to an ascending list of elements.
</p></div></div><div class="top"><p class="src"><a name="v:fromAscList" class="def">fromAscList</a> :: [<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>] -> <a href="Data-IntSet.html#t:IntSet">IntSet</a></p><div class="doc"><p><em>O(n)</em>. Build a set from an ascending list of elements.
<em>The precondition (input list is ascending) is not checked.</em>
</p></div></div><div class="top"><p class="src"><a name="v:fromDistinctAscList" class="def">fromDistinctAscList</a> :: [<a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a>] -> <a href="Data-IntSet.html#t:IntSet">IntSet</a></p><div class="doc"><p><em>O(n)</em>. Build a set from an ascending list of distinct elements.
<em>The precondition (input list is strictly ascending) is not checked.</em>
</p></div></div><h1 id="g:15">Debugging
</h1><div class="top"><p class="src"><a name="v:showTree" class="def">showTree</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="../base-4.5.1.0/Data-String.html#t:String">String</a></p><div class="doc"><p><em>O(n)</em>. Show the tree that implements the set. The tree is shown
in a compressed, hanging format.
</p></div></div><div class="top"><p class="src"><a name="v:showTreeWith" class="def">showTreeWith</a> :: <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a> -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="../base-4.5.1.0/Data-String.html#t:String">String</a></p><div class="doc"><p><em>O(n)</em>. The expression (<code><code><a href="Data-IntSet.html#v:showTreeWith">showTreeWith</a></code> hang wide map</code>) shows
the tree that implements the set. If <code>hang</code> is
<code><a href="../base-4.5.1.0/Data-Bool.html#v:True">True</a></code>, a <em>hanging</em> tree is shown otherwise a rotated tree is shown. If
<code>wide</code> is <code><a href="../base-4.5.1.0/Data-Bool.html#v:True">True</a></code>, an extra wide version is shown.
</p></div></div></div></div><div id="footer"><p>Produced by <a href="http://www.haskell.org/haddock/">Haddock</a> version 2.11.0</p></div></body></html>
distrib
>
Mageia
>
5
>
i586
>
media
>
core-release
>
by-pkgid
>
6e204a966e8c42d976f99a1700ce5f20
>
files
>
2591
