<!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="src/Data-IntSet.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">containers-0.4.0.0: 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></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">Min/Max </a></li><li><a href="#g:8">Map </a></li><li><a href="#g:9">Fold </a></li><li><a href="#g:10">Conversion </a><ul><li><a href="#g:11">List </a></li><li><a href="#g:12">Ordered list </a></li></ul></li><li><a href="#g:13">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="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.3.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.3.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.3.1.0/Data-Int.html#t:Int">Int</a></li><li class="src short"><a href="#v:member">member</a> :: <a href="../base-4.3.1.0/Data-Int.html#t:Int">Int</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="../base-4.3.1.0/Data-Bool.html#t:Bool">Bool</a></li><li class="src short"><a href="#v:notMember">notMember</a> :: <a href="../base-4.3.1.0/Data-Int.html#t:Int">Int</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="../base-4.3.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.3.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.3.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.3.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.3.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.3.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.3.1.0/Data-Int.html#t:Int">Int</a> -> <a href="../base-4.3.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.3.1.0/Data-Int.html#t:Int">Int</a> -> <a href="../base-4.3.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.3.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.3.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.3.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:findMin">findMin</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="../base-4.3.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.3.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.3.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.3.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.3.1.0/Data-Maybe.html#t:Maybe">Maybe</a> (<a href="../base-4.3.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.3.1.0/Data-Maybe.html#t:Maybe">Maybe</a> (<a href="../base-4.3.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:map">map</a> :: (<a href="../base-4.3.1.0/Data-Int.html#t:Int">Int</a> -> <a href="../base-4.3.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:fold">fold</a> :: (<a href="../base-4.3.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:elems">elems</a> :: <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> [<a href="../base-4.3.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.3.1.0/Data-Int.html#t:Int">Int</a>]</li><li class="src short"><a href="#v:fromList">fromList</a> :: [<a href="../base-4.3.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.3.1.0/Data-Int.html#t:Int">Int</a>]</li><li class="src short"><a href="#v:fromAscList">fromAscList</a> :: [<a href="../base-4.3.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.3.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.3.1.0/Data-Char.html#t:String">String</a></li><li class="src short"><a href="#v:showTreeWith">showTreeWith</a> :: <a href="../base-4.3.1.0/Data-Bool.html#t:Bool">Bool</a> -> <a href="../base-4.3.1.0/Data-Bool.html#t:Bool">Bool</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="../base-4.3.1.0/Data-Char.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> <a href="src/Data-IntSet.html#IntSet" class="link">Source</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.3.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.3.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.3.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.3.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.3.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.3.1.0/Data-Typeable.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.3.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></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><a href="src/Data-IntSet.html#%5C%5C" class="link">Source</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.3.1.0/Data-Bool.html#t:Bool">Bool</a><a href="src/Data-IntSet.html#null" class="link">Source</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.3.1.0/Data-Int.html#t:Int">Int</a><a href="src/Data-IntSet.html#size" class="link">Source</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.3.1.0/Data-Int.html#t:Int">Int</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="../base-4.3.1.0/Data-Bool.html#t:Bool">Bool</a><a href="src/Data-IntSet.html#member" class="link">Source</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.3.1.0/Data-Int.html#t:Int">Int</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="../base-4.3.1.0/Data-Bool.html#t:Bool">Bool</a><a href="src/Data-IntSet.html#notMember" class="link">Source</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.3.1.0/Data-Bool.html#t:Bool">Bool</a><a href="src/Data-IntSet.html#isSubsetOf" class="link">Source</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.3.1.0/Data-Bool.html#t:Bool">Bool</a><a href="src/Data-IntSet.html#isProperSubsetOf" class="link">Source</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><a href="src/Data-IntSet.html#empty" class="link">Source</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.3.1.0/Data-Int.html#t:Int">Int</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a><a href="src/Data-IntSet.html#singleton" class="link">Source</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.3.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="src/Data-IntSet.html#insert" class="link">Source</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.3.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="src/Data-IntSet.html#delete" class="link">Source</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><a href="src/Data-IntSet.html#union" class="link">Source</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><a href="src/Data-IntSet.html#unions" class="link">Source</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><a href="src/Data-IntSet.html#difference" class="link">Source</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><a href="src/Data-IntSet.html#intersection" class="link">Source</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.3.1.0/Data-Int.html#t:Int">Int</a> -> <a href="../base-4.3.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="src/Data-IntSet.html#filter" class="link">Source</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.3.1.0/Data-Int.html#t:Int">Int</a> -> <a href="../base-4.3.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>)<a href="src/Data-IntSet.html#partition" class="link">Source</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.3.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>)<a href="src/Data-IntSet.html#split" class="link">Source</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.3.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.3.1.0/Data-Bool.html#t:Bool">Bool</a>, <a href="Data-IntSet.html#t:IntSet">IntSet</a>)<a href="src/Data-IntSet.html#splitMember" class="link">Source</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">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.3.1.0/Data-Int.html#t:Int">Int</a><a href="src/Data-IntSet.html#findMin" class="link">Source</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.3.1.0/Data-Int.html#t:Int">Int</a><a href="src/Data-IntSet.html#findMax" class="link">Source</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><a href="src/Data-IntSet.html#deleteMin" class="link">Source</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><a href="src/Data-IntSet.html#deleteMax" class="link">Source</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.3.1.0/Data-Int.html#t:Int">Int</a>, <a href="Data-IntSet.html#t:IntSet">IntSet</a>)<a href="src/Data-IntSet.html#deleteFindMin" class="link">Source</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.3.1.0/Data-Int.html#t:Int">Int</a>, <a href="Data-IntSet.html#t:IntSet">IntSet</a>)<a href="src/Data-IntSet.html#deleteFindMax" class="link">Source</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.3.1.0/Data-Maybe.html#t:Maybe">Maybe</a> (<a href="../base-4.3.1.0/Data-Int.html#t:Int">Int</a>, <a href="Data-IntSet.html#t:IntSet">IntSet</a>)<a href="src/Data-IntSet.html#maxView" class="link">Source</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.3.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.3.1.0/Data-Maybe.html#t:Maybe">Maybe</a> (<a href="../base-4.3.1.0/Data-Int.html#t:Int">Int</a>, <a href="Data-IntSet.html#t:IntSet">IntSet</a>)<a href="src/Data-IntSet.html#minView" class="link">Source</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.3.1.0/Data-Maybe.html#v:Nothing">Nothing</a></code> if passed an empty set. </p></div></div><h1 id="g:8">Map </h1><div class="top"><p class="src"><a name="v:map" class="def">map</a> :: (<a href="../base-4.3.1.0/Data-Int.html#t:Int">Int</a> -> <a href="../base-4.3.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="src/Data-IntSet.html#map" class="link">Source</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:9">Fold </h1><div class="top"><p class="src"><a name="v:fold" class="def">fold</a> :: (<a href="../base-4.3.1.0/Data-Int.html#t:Int">Int</a> -> b -> b) -> b -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> b<a href="src/Data-IntSet.html#fold" class="link">Source</a></p><div class="doc"><p><em>O(n)</em>. Fold over the elements of a set in an unspecified order. </p><pre> sum set == fold (+) 0 set elems set == fold (:) [] set </pre></div></div><h1 id="g:10">Conversion </h1><h2 id="g:11">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.3.1.0/Data-Int.html#t:Int">Int</a>]<a href="src/Data-IntSet.html#elems" class="link">Source</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.3.1.0/Data-Int.html#t:Int">Int</a>]<a href="src/Data-IntSet.html#toList" class="link">Source</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.3.1.0/Data-Int.html#t:Int">Int</a>] -> <a href="Data-IntSet.html#t:IntSet">IntSet</a><a href="src/Data-IntSet.html#fromList" class="link">Source</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:12">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.3.1.0/Data-Int.html#t:Int">Int</a>]<a href="src/Data-IntSet.html#toAscList" class="link">Source</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.3.1.0/Data-Int.html#t:Int">Int</a>] -> <a href="Data-IntSet.html#t:IntSet">IntSet</a><a href="src/Data-IntSet.html#fromAscList" class="link">Source</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.3.1.0/Data-Int.html#t:Int">Int</a>] -> <a href="Data-IntSet.html#t:IntSet">IntSet</a><a href="src/Data-IntSet.html#fromDistinctAscList" class="link">Source</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:13">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.3.1.0/Data-Char.html#t:String">String</a><a href="src/Data-IntSet.html#showTree" class="link">Source</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.3.1.0/Data-Bool.html#t:Bool">Bool</a> -> <a href="../base-4.3.1.0/Data-Bool.html#t:Bool">Bool</a> -> <a href="Data-IntSet.html#t:IntSet">IntSet</a> -> <a href="../base-4.3.1.0/Data-Char.html#t:String">String</a><a href="src/Data-IntSet.html#showTreeWith" class="link">Source</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.3.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.3.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.9.2</p></div></body></html>