<!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.Set</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-Set.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>Safe</td></tr></table><p class="caption">Data.Set</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 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.Set (Set)
import qualified Data.Set as Set
</pre><p>The implementation of <code><a href="Data-Set.html#t:Set">Set</a></code> is based on <em>size balanced</em> binary trees (or
trees of <em>bounded balance</em>) as described by:
</p><ul><li> Stephen Adams, "<em>Efficient sets: a balancing act</em>",
Journal of Functional Programming 3(4):553-562, October 1993,
<a href="http://www.swiss.ai.mit.edu/~adams/BB/">http://www.swiss.ai.mit.edu/~adams/BB/</a>.
</li><li> J. Nievergelt and E.M. Reingold,
"<em>Binary search trees of bounded balance</em>",
SIAM journal of computing 2(1), March 1973.
</li></ul><p>Note that the implementation is <em>left-biased</em> -- the elements of a
first argument are always preferred to the second, for example in
<code><a href="Data-Set.html#v:union">union</a></code> or <code><a href="Data-Set.html#v:insert">insert</a></code>. Of course, left-biasing can only be observed
when equality is an equivalence relation instead of structural
equality.
</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:Set">Set</a> a</li><li class="src short"><a href="#v:-92--92-">(\\)</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> a => <a href="Data-Set.html#t:Set">Set</a> a -> <a href="Data-Set.html#t:Set">Set</a> a -> <a href="Data-Set.html#t:Set">Set</a> a</li><li class="src short"><a href="#v:null">null</a> :: <a href="Data-Set.html#t:Set">Set</a> 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-Set.html#t:Set">Set</a> 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-Ord.html#t:Ord">Ord</a> a => a -> <a href="Data-Set.html#t:Set">Set</a> 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-Ord.html#t:Ord">Ord</a> a => a -> <a href="Data-Set.html#t:Set">Set</a> 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="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> a => <a href="Data-Set.html#t:Set">Set</a> a -> <a href="Data-Set.html#t:Set">Set</a> 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="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> a => <a href="Data-Set.html#t:Set">Set</a> a -> <a href="Data-Set.html#t:Set">Set</a> 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-Set.html#t:Set">Set</a> a</li><li class="src short"><a href="#v:singleton">singleton</a> :: a -> <a href="Data-Set.html#t:Set">Set</a> a</li><li class="src short"><a href="#v:insert">insert</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> a => a -> <a href="Data-Set.html#t:Set">Set</a> a -> <a href="Data-Set.html#t:Set">Set</a> a</li><li class="src short"><a href="#v:delete">delete</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> a => a -> <a href="Data-Set.html#t:Set">Set</a> a -> <a href="Data-Set.html#t:Set">Set</a> a</li><li class="src short"><a href="#v:union">union</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> a => <a href="Data-Set.html#t:Set">Set</a> a -> <a href="Data-Set.html#t:Set">Set</a> a -> <a href="Data-Set.html#t:Set">Set</a> a</li><li class="src short"><a href="#v:unions">unions</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> a => [<a href="Data-Set.html#t:Set">Set</a> a] -> <a href="Data-Set.html#t:Set">Set</a> a</li><li class="src short"><a href="#v:difference">difference</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> a => <a href="Data-Set.html#t:Set">Set</a> a -> <a href="Data-Set.html#t:Set">Set</a> a -> <a href="Data-Set.html#t:Set">Set</a> a</li><li class="src short"><a href="#v:intersection">intersection</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> a => <a href="Data-Set.html#t:Set">Set</a> a -> <a href="Data-Set.html#t:Set">Set</a> a -> <a href="Data-Set.html#t:Set">Set</a> a</li><li class="src short"><a href="#v:filter">filter</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> a => (a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Set.html#t:Set">Set</a> a -> <a href="Data-Set.html#t:Set">Set</a> a</li><li class="src short"><a href="#v:partition">partition</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> a => (a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Set.html#t:Set">Set</a> a -> (<a href="Data-Set.html#t:Set">Set</a> a, <a href="Data-Set.html#t:Set">Set</a> a)</li><li class="src short"><a href="#v:split">split</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> a => a -> <a href="Data-Set.html#t:Set">Set</a> a -> (<a href="Data-Set.html#t:Set">Set</a> a, <a href="Data-Set.html#t:Set">Set</a> a)</li><li class="src short"><a href="#v:splitMember">splitMember</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> a => a -> <a href="Data-Set.html#t:Set">Set</a> a -> (<a href="Data-Set.html#t:Set">Set</a> a, <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>, <a href="Data-Set.html#t:Set">Set</a> a)</li><li class="src short"><a href="#v:map">map</a> :: (<a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> a, <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> b) => (a -> b) -> <a href="Data-Set.html#t:Set">Set</a> a -> <a href="Data-Set.html#t:Set">Set</a> b</li><li class="src short"><a href="#v:mapMonotonic">mapMonotonic</a> :: (a -> b) -> <a href="Data-Set.html#t:Set">Set</a> a -> <a href="Data-Set.html#t:Set">Set</a> b</li><li class="src short"><a href="#v:foldr">foldr</a> :: (a -> b -> b) -> b -> <a href="Data-Set.html#t:Set">Set</a> a -> b</li><li class="src short"><a href="#v:foldl">foldl</a> :: (a -> b -> a) -> a -> <a href="Data-Set.html#t:Set">Set</a> b -> a</li><li class="src short"><a href="#v:foldr-39-">foldr'</a> :: (a -> b -> b) -> b -> <a href="Data-Set.html#t:Set">Set</a> a -> b</li><li class="src short"><a href="#v:foldl-39-">foldl'</a> :: (a -> b -> a) -> a -> <a href="Data-Set.html#t:Set">Set</a> b -> a</li><li class="src short"><a href="#v:fold">fold</a> :: (a -> b -> b) -> b -> <a href="Data-Set.html#t:Set">Set</a> a -> b</li><li class="src short"><a href="#v:findMin">findMin</a> :: <a href="Data-Set.html#t:Set">Set</a> a -> a</li><li class="src short"><a href="#v:findMax">findMax</a> :: <a href="Data-Set.html#t:Set">Set</a> a -> a</li><li class="src short"><a href="#v:deleteMin">deleteMin</a> :: <a href="Data-Set.html#t:Set">Set</a> a -> <a href="Data-Set.html#t:Set">Set</a> a</li><li class="src short"><a href="#v:deleteMax">deleteMax</a> :: <a href="Data-Set.html#t:Set">Set</a> a -> <a href="Data-Set.html#t:Set">Set</a> a</li><li class="src short"><a href="#v:deleteFindMin">deleteFindMin</a> :: <a href="Data-Set.html#t:Set">Set</a> a -> (a, <a href="Data-Set.html#t:Set">Set</a> a)</li><li class="src short"><a href="#v:deleteFindMax">deleteFindMax</a> :: <a href="Data-Set.html#t:Set">Set</a> a -> (a, <a href="Data-Set.html#t:Set">Set</a> a)</li><li class="src short"><a href="#v:maxView">maxView</a> :: <a href="Data-Set.html#t:Set">Set</a> a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> (a, <a href="Data-Set.html#t:Set">Set</a> a)</li><li class="src short"><a href="#v:minView">minView</a> :: <a href="Data-Set.html#t:Set">Set</a> a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> (a, <a href="Data-Set.html#t:Set">Set</a> a)</li><li class="src short"><a href="#v:elems">elems</a> :: <a href="Data-Set.html#t:Set">Set</a> a -> [a]</li><li class="src short"><a href="#v:toList">toList</a> :: <a href="Data-Set.html#t:Set">Set</a> a -> [a]</li><li class="src short"><a href="#v:fromList">fromList</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> a => [a] -> <a href="Data-Set.html#t:Set">Set</a> a</li><li class="src short"><a href="#v:toAscList">toAscList</a> :: <a href="Data-Set.html#t:Set">Set</a> a -> [a]</li><li class="src short"><a href="#v:fromAscList">fromAscList</a> :: <a href="../base-4.5.1.0/Data-Eq.html#t:Eq">Eq</a> a => [a] -> <a href="Data-Set.html#t:Set">Set</a> a</li><li class="src short"><a href="#v:fromDistinctAscList">fromDistinctAscList</a> :: [a] -> <a href="Data-Set.html#t:Set">Set</a> a</li><li class="src short"><a href="#v:showTree">showTree</a> :: <a href="../base-4.5.1.0/Text-Show.html#t:Show">Show</a> a => <a href="Data-Set.html#t:Set">Set</a> 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/Text-Show.html#t:Show">Show</a> 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-Set.html#t:Set">Set</a> a -> <a href="../base-4.5.1.0/Data-String.html#t:String">String</a></li><li class="src short"><a href="#v:valid">valid</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> a => <a href="Data-Set.html#t:Set">Set</a> a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</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:Set" class="def">Set</a> a </p><div class="doc"><p>A set of values <code>a</code>.
</p></div><div class="subs instances"><p id="control.i:Set" class="caption collapser" onclick="toggleSection('i:Set')">Instances</p><div id="section.i:Set" class="show"><table><tr><td class="src"><a href="../base-4.5.1.0/Data-Typeable-Internal.html#t:Typeable1">Typeable1</a> <a href="Data-Set.html#t:Set">Set</a></td><td class="doc empty"> </td></tr><tr><td class="src"><a href="../base-4.5.1.0/Data-Foldable.html#t:Foldable">Foldable</a> <a href="Data-Set.html#t:Set">Set</a></td><td class="doc empty"> </td></tr><tr><td class="src"><a href="../base-4.5.1.0/Data-Eq.html#t:Eq">Eq</a> a => <a href="../base-4.5.1.0/Data-Eq.html#t:Eq">Eq</a> (<a href="Data-Set.html#t:Set">Set</a> 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, <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> a) => <a href="../base-4.5.1.0/Data-Data.html#t:Data">Data</a> (<a href="Data-Set.html#t:Set">Set</a> 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 => <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> (<a href="Data-Set.html#t:Set">Set</a> 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, <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> a) => <a href="../base-4.5.1.0/Text-Read.html#t:Read">Read</a> (<a href="Data-Set.html#t:Set">Set</a> 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 => <a href="../base-4.5.1.0/Text-Show.html#t:Show">Show</a> (<a href="Data-Set.html#t:Set">Set</a> 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 => <a href="../base-4.5.1.0/Data-Monoid.html#t:Monoid">Monoid</a> (<a href="Data-Set.html#t:Set">Set</a> 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 => <a href="../deepseq-1.3.0.0/Control-DeepSeq.html#t:NFData">NFData</a> (<a href="Data-Set.html#t:Set">Set</a> 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="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> a => <a href="Data-Set.html#t:Set">Set</a> a -> <a href="Data-Set.html#t:Set">Set</a> a -> <a href="Data-Set.html#t:Set">Set</a> a</p><div class="doc"><p><em>O(n+m)</em>. See <code><a href="Data-Set.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-Set.html#t:Set">Set</a> 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 this the empty set?
</p></div></div><div class="top"><p class="src"><a name="v:size" class="def">size</a> :: <a href="Data-Set.html#t:Set">Set</a> a -> <a href="../base-4.5.1.0/Data-Int.html#t:Int">Int</a></p><div class="doc"><p><em>O(1)</em>. The number of elements in 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-Ord.html#t:Ord">Ord</a> a => a -> <a href="Data-Set.html#t:Set">Set</a> a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></p><div class="doc"><p><em>O(log n)</em>. Is the element in 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-Ord.html#t:Ord">Ord</a> a => a -> <a href="Data-Set.html#t:Set">Set</a> a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></p><div class="doc"><p><em>O(log n)</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="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> a => <a href="Data-Set.html#t:Set">Set</a> a -> <a href="Data-Set.html#t:Set">Set</a> 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-Set.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="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> a => <a href="Data-Set.html#t:Set">Set</a> a -> <a href="Data-Set.html#t:Set">Set</a> 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-Set.html#t:Set">Set</a> 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 -> <a href="Data-Set.html#t:Set">Set</a> a</p><div class="doc"><p><em>O(1)</em>. Create a singleton set.
</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-Ord.html#t:Ord">Ord</a> a => a -> <a href="Data-Set.html#t:Set">Set</a> a -> <a href="Data-Set.html#t:Set">Set</a> a</p><div class="doc"><p><em>O(log n)</em>. Insert an element in a set.
If the set already contains an element equal to the given value,
it is replaced with the new value.
</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-Ord.html#t:Ord">Ord</a> a => a -> <a href="Data-Set.html#t:Set">Set</a> a -> <a href="Data-Set.html#t:Set">Set</a> a</p><div class="doc"><p><em>O(log n)</em>. Delete an element from a set.
</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="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> a => <a href="Data-Set.html#t:Set">Set</a> a -> <a href="Data-Set.html#t:Set">Set</a> a -> <a href="Data-Set.html#t:Set">Set</a> a</p><div class="doc"><p><em>O(n+m)</em>. The union of two sets, preferring the first set when
equal elements are encountered.
The implementation uses the efficient <em>hedge-union</em> algorithm.
Hedge-union is more efficient on (bigset <code><a href="Data-Set.html#v:union">union</a></code> smallset).
</p></div></div><div class="top"><p class="src"><a name="v:unions" class="def">unions</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> a => [<a href="Data-Set.html#t:Set">Set</a> a] -> <a href="Data-Set.html#t:Set">Set</a> a</p><div class="doc"><p>The union of a list of sets: (<code><code><a href="Data-Set.html#v:unions">unions</a></code> == <code><a href="Data-Set.html#v:foldl">foldl</a></code> <code><a href="Data-Set.html#v:union">union</a></code> <code><a href="Data-Set.html#v:empty">empty</a></code></code>).
</p></div></div><div class="top"><p class="src"><a name="v:difference" class="def">difference</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> a => <a href="Data-Set.html#t:Set">Set</a> a -> <a href="Data-Set.html#t:Set">Set</a> a -> <a href="Data-Set.html#t:Set">Set</a> a</p><div class="doc"><p><em>O(n+m)</em>. Difference of two sets.
The implementation uses an efficient <em>hedge</em> algorithm comparable with <em>hedge-union</em>.
</p></div></div><div class="top"><p class="src"><a name="v:intersection" class="def">intersection</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> a => <a href="Data-Set.html#t:Set">Set</a> a -> <a href="Data-Set.html#t:Set">Set</a> a -> <a href="Data-Set.html#t:Set">Set</a> a</p><div class="doc"><p><em>O(n+m)</em>. The intersection of two sets.
Elements of the result come from the first set, so for example
</p><pre> import qualified Data.Set as S
data AB = A | B deriving Show
instance Ord AB where compare _ _ = EQ
instance Eq AB where _ == _ = True
main = print (S.singleton A `S.intersection` S.singleton B,
S.singleton B `S.intersection` S.singleton A)
</pre><p>prints <code>(fromList [A],fromList [B])</code>.
</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-Ord.html#t:Ord">Ord</a> a => (a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Set.html#t:Set">Set</a> a -> <a href="Data-Set.html#t:Set">Set</a> a</p><div class="doc"><p><em>O(n)</em>. Filter all elements that satisfy the 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-Ord.html#t:Ord">Ord</a> a => (a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>) -> <a href="Data-Set.html#t:Set">Set</a> a -> (<a href="Data-Set.html#t:Set">Set</a> a, <a href="Data-Set.html#t:Set">Set</a> a)</p><div class="doc"><p><em>O(n)</em>. Partition the set into two sets, one with all elements that satisfy
the predicate and one with all elements that don't satisfy the predicate.
See also <code><a href="Data-Set.html#v:split">split</a></code>.
</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-Ord.html#t:Ord">Ord</a> a => a -> <a href="Data-Set.html#t:Set">Set</a> a -> (<a href="Data-Set.html#t:Set">Set</a> a, <a href="Data-Set.html#t:Set">Set</a> a)</p><div class="doc"><p><em>O(log n)</em>. The expression (<code><code><a href="Data-Set.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></div></div><div class="top"><p class="src"><a name="v:splitMember" class="def">splitMember</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> a => a -> <a href="Data-Set.html#t:Set">Set</a> a -> (<a href="Data-Set.html#t:Set">Set</a> a, <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a>, <a href="Data-Set.html#t:Set">Set</a> a)</p><div class="doc"><p><em>O(log n)</em>. Performs a <code><a href="Data-Set.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-Ord.html#t:Ord">Ord</a> a, <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> b) => (a -> b) -> <a href="Data-Set.html#t:Set">Set</a> a -> <a href="Data-Set.html#t:Set">Set</a> b</p><div class="doc"><p><em>O(n*log n)</em>.
<code><code><a href="Data-Set.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><div class="top"><p class="src"><a name="v:mapMonotonic" class="def">mapMonotonic</a> :: (a -> b) -> <a href="Data-Set.html#t:Set">Set</a> a -> <a href="Data-Set.html#t:Set">Set</a> b</p><div class="doc"><p><em>O(n)</em>. The
</p><p><code><code><a href="Data-Set.html#v:mapMonotonic">mapMonotonic</a></code> f s == <code><a href="Data-Set.html#v:map">map</a></code> f s</code>, but works only when <code>f</code> is monotonic.
<em>The precondition is not checked.</em>
Semi-formally, we have:
</p><pre> and [x < y ==> f x < f y | x <- ls, y <- ls]
==> mapMonotonic f s == map f s
where ls = toList s
</pre></div></div><h1 id="g:8">Folds
</h1><div class="top"><p class="src"><a name="v:foldr" class="def">foldr</a> :: (a -> b -> b) -> b -> <a href="Data-Set.html#t:Set">Set</a> 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-Set.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-Set.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 -> b -> a) -> a -> <a href="Data-Set.html#t:Set">Set</a> b -> 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-Set.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-Set.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 -> b -> b) -> b -> <a href="Data-Set.html#t:Set">Set</a> a -> b</p><div class="doc"><p><em>O(n)</em>. A strict version of <code><a href="Data-Set.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 -> b -> a) -> a -> <a href="Data-Set.html#t:Set">Set</a> b -> a</p><div class="doc"><p><em>O(n)</em>. A strict version of <code><a href="Data-Set.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 -> b -> b) -> b -> <a href="Data-Set.html#t:Set">Set</a> 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-Set.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-Set.html#t:Set">Set</a> a -> a</p><div class="doc"><p><em>O(log n)</em>. The minimal element of a set.
</p></div></div><div class="top"><p class="src"><a name="v:findMax" class="def">findMax</a> :: <a href="Data-Set.html#t:Set">Set</a> a -> a</p><div class="doc"><p><em>O(log n)</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-Set.html#t:Set">Set</a> a -> <a href="Data-Set.html#t:Set">Set</a> a</p><div class="doc"><p><em>O(log n)</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-Set.html#t:Set">Set</a> a -> <a href="Data-Set.html#t:Set">Set</a> a</p><div class="doc"><p><em>O(log n)</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-Set.html#t:Set">Set</a> a -> (a, <a href="Data-Set.html#t:Set">Set</a> a)</p><div class="doc"><p><em>O(log n)</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-Set.html#t:Set">Set</a> a -> (a, <a href="Data-Set.html#t:Set">Set</a> a)</p><div class="doc"><p><em>O(log n)</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-Set.html#t:Set">Set</a> a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> (a, <a href="Data-Set.html#t:Set">Set</a> a)</p><div class="doc"><p><em>O(log n)</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-Set.html#t:Set">Set</a> a -> <a href="../base-4.5.1.0/Data-Maybe.html#t:Maybe">Maybe</a> (a, <a href="Data-Set.html#t:Set">Set</a> a)</p><div class="doc"><p><em>O(log n)</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-Set.html#t:Set">Set</a> a -> [a]</p><div class="doc"><p><em>O(n)</em>. The elements of a set.
</p></div></div><div class="top"><p class="src"><a name="v:toList" class="def">toList</a> :: <a href="Data-Set.html#t:Set">Set</a> a -> [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-Ord.html#t:Ord">Ord</a> a => [a] -> <a href="Data-Set.html#t:Set">Set</a> a</p><div class="doc"><p><em>O(n*log n)</em>. Create a set from a list of elements.
</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-Set.html#t:Set">Set</a> a -> [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-Eq.html#t:Eq">Eq</a> a => [a] -> <a href="Data-Set.html#t:Set">Set</a> a</p><div class="doc"><p><em>O(n)</em>. Build a set from an ascending list in linear time.
<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] -> <a href="Data-Set.html#t:Set">Set</a> a</p><div class="doc"><p><em>O(n)</em>. Build a set from an ascending list of distinct elements in linear time.
<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="../base-4.5.1.0/Text-Show.html#t:Show">Show</a> a => <a href="Data-Set.html#t:Set">Set</a> 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/Text-Show.html#t:Show">Show</a> 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-Set.html#t:Set">Set</a> 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>showTreeWith hang wide map</code>) shows
the tree that implements the set. If <code>hang</code> is
<code>True</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><pre> Set> putStrLn $ showTreeWith True False $ fromDistinctAscList [1..5]
4
+--2
| +--1
| +--3
+--5
Set> putStrLn $ showTreeWith True True $ fromDistinctAscList [1..5]
4
|
+--2
| |
| +--1
| |
| +--3
|
+--5
Set> putStrLn $ showTreeWith False True $ fromDistinctAscList [1..5]
+--5
|
4
|
| +--3
| |
+--2
|
+--1
</pre></div></div><div class="top"><p class="src"><a name="v:valid" class="def">valid</a> :: <a href="../base-4.5.1.0/Data-Ord.html#t:Ord">Ord</a> a => <a href="Data-Set.html#t:Set">Set</a> a -> <a href="../base-4.5.1.0/Data-Bool.html#t:Bool">Bool</a></p><div class="doc"><p><em>O(n)</em>. Test if the internal set structure is valid.
</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>
