<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<!--Rendered using the Haskell Html Library v0.2-->
<HTML
><HEAD
><META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=UTF-8"
><TITLE
>Data.Set</TITLE
><LINK HREF="haddock.css" REL="stylesheet" TYPE="text/css"
><SCRIPT SRC="haddock-util.js" TYPE="text/javascript"
></SCRIPT
><SCRIPT TYPE="text/javascript"
>window.onload = function () {setSynopsis("mini_Data-Set.html")};</SCRIPT
></HEAD
><BODY
><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"
><TR
><TD CLASS="topbar"
><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"
><TR
><TD
><IMG SRC="haskell_icon.gif" WIDTH="16" HEIGHT="16" ALT=" "
></TD
><TD CLASS="title"
>containers-0.2.0.1: Assorted concrete container types</TD
><TD CLASS="topbut"
><A HREF="index.html"
>Contents</A
></TD
><TD CLASS="topbut"
><A HREF="doc-index.html"
>Index</A
></TD
></TR
></TABLE
></TD
></TR
><TR
><TD CLASS="modulebar"
><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"
><TR
><TD
><FONT SIZE="6"
>Data.Set</FONT
></TD
><TD ALIGN="right"
><TABLE CLASS="narrow" CELLSPACING="0" CELLPADDING="0"
><TR
><TD CLASS="infohead"
>Portability</TD
><TD CLASS="infoval"
>portable</TD
></TR
><TR
><TD CLASS="infohead"
>Stability</TD
><TD CLASS="infoval"
>provisional</TD
></TR
><TR
><TD CLASS="infohead"
>Maintainer</TD
><TD CLASS="infoval"
>libraries@haskell.org</TD
></TR
></TABLE
></TD
></TR
></TABLE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD
><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"
><TR
><TD CLASS="section4"
><B
>Contents</B
></TD
></TR
><TR
><TD
><DL
><DT
><A HREF="#1"
>Set type
</A
></DT
><DT
><A HREF="#2"
>Operators
</A
></DT
><DT
><A HREF="#3"
>Query
</A
></DT
><DT
><A HREF="#4"
>Construction
</A
></DT
><DT
><A HREF="#5"
>Combine
</A
></DT
><DT
><A HREF="#6"
>Filter
</A
></DT
><DT
><A HREF="#7"
>Map
</A
></DT
><DT
><A HREF="#8"
>Fold
</A
></DT
><DT
><A HREF="#9"
>Min/Max
</A
></DT
><DT
><A HREF="#10"
>Conversion
</A
></DT
><DD
><DL
><DT
><A HREF="#11"
>List
</A
></DT
><DT
><A HREF="#12"
>Ordered list
</A
></DT
></DL
></DD
><DT
><A HREF="#13"
>Debugging
</A
></DT
></DL
></TD
></TR
></TABLE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section1"
>Description</TD
></TR
><TR
><TD CLASS="doc"
><P
>An efficient implementation of 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 <TT
>qualified</TT
>, e.g.
</P
><PRE
> import Data.Set (Set)
import qualified Data.Set as Set
</PRE
><P
>The implementation of <TT
><A HREF="Data-Set.html#t%3ASet"
>Set</A
></TT
> 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
<TT
><A HREF="Data-Set.html#v%3Aunion"
>union</A
></TT
> or <TT
><A HREF="Data-Set.html#v%3Ainsert"
>insert</A
></TT
>. Of course, left-biasing can only be observed
when equality is an equivalence relation instead of structural
equality.
</P
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section1"
>Synopsis</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="body"
><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"
><TR
><TD CLASS="decl"
><SPAN CLASS="keyword"
>data</SPAN
> <A HREF="#t%3ASet"
>Set</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3A%5C%5C"
>(\\)</A
> :: <A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a => <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Anull"
>null</A
> :: <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
></TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Asize"
>size</A
> :: <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="../ghc-prim/GHC-Types.html#t%3AInt"
>Int</A
></TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Amember"
>member</A
> :: <A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a => a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
></TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AnotMember"
>notMember</A
> :: <A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a => a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
></TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AisSubsetOf"
>isSubsetOf</A
> :: <A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a => <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
></TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AisProperSubsetOf"
>isProperSubsetOf</A
> :: <A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a => <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
></TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Aempty"
>empty</A
> :: <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Asingleton"
>singleton</A
> :: a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Ainsert"
>insert</A
> :: <A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a => a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Adelete"
>delete</A
> :: <A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a => a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Aunion"
>union</A
> :: <A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a => <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Aunions"
>unions</A
> :: <A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a => [<A HREF="Data-Set.html#t%3ASet"
>Set</A
> a] -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Adifference"
>difference</A
> :: <A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a => <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Aintersection"
>intersection</A
> :: <A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a => <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Afilter"
>filter</A
> :: <A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a => (a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
>) -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Apartition"
>partition</A
> :: <A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a => (a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
>) -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> (<A HREF="Data-Set.html#t%3ASet"
>Set</A
> a, <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a)</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Asplit"
>split</A
> :: <A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a => a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> (<A HREF="Data-Set.html#t%3ASet"
>Set</A
> a, <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a)</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AsplitMember"
>splitMember</A
> :: <A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a => a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> (<A HREF="Data-Set.html#t%3ASet"
>Set</A
> a, <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
>, <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a)</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Amap"
>map</A
> :: (<A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a, <A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> b) => (a -> b) -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> b</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AmapMonotonic"
>mapMonotonic</A
> :: (a -> b) -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> b</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Afold"
>fold</A
> :: (a -> b -> b) -> b -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> b</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AfindMin"
>findMin</A
> :: <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AfindMax"
>findMax</A
> :: <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AdeleteMin"
>deleteMin</A
> :: <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AdeleteMax"
>deleteMax</A
> :: <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AdeleteFindMin"
>deleteFindMin</A
> :: <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> (a, <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a)</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AdeleteFindMax"
>deleteFindMax</A
> :: <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> (a, <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a)</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AmaxView"
>maxView</A
> :: <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> (a, <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a)</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AminView"
>minView</A
> :: <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> (a, <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a)</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Aelems"
>elems</A
> :: <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> [a]</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AtoList"
>toList</A
> :: <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> [a]</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AfromList"
>fromList</A
> :: <A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a => [a] -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AtoAscList"
>toAscList</A
> :: <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> [a]</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AfromAscList"
>fromAscList</A
> :: <A HREF="../base/Data-Eq.html#t%3AEq"
>Eq</A
> a => [a] -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AfromDistinctAscList"
>fromDistinctAscList</A
> :: [a] -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AshowTree"
>showTree</A
> :: <A HREF="../base/Text-Show.html#t%3AShow"
>Show</A
> a => <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="../base/Data-Char.html#t%3AString"
>String</A
></TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AshowTreeWith"
>showTreeWith</A
> :: <A HREF="../base/Text-Show.html#t%3AShow"
>Show</A
> a => <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
> -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
> -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="../base/Data-Char.html#t%3AString"
>String</A
></TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3Avalid"
>valid</A
> :: <A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a => <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
></TD
></TR
></TABLE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section1"
><A NAME="1"
><A NAME="1"
>Set type
</A
></A
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><SPAN CLASS="keyword"
>data</SPAN
> <A NAME="t:Set"
><A NAME="t%3ASet"
></A
></A
><B
>Set</B
> a </TD
></TR
><TR
><TD CLASS="body"
><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"
><TR
><TD CLASS="ndoc"
>A set of values <TT
>a</TT
>.
</TD
></TR
><TR
><TD CLASS="section4"
><IMG SRC="minus.gif" CLASS="coll" ONCLICK="toggle(this,'i:Set')" ALT="show/hide"
> Instances</TD
></TR
><TR
><TD CLASS="body"
><DIV ID="i:Set" STYLE="display:block;"
><TABLE CLASS="vanilla" CELLSPACING="1" CELLPADDING="0"
><TR
><TD CLASS="decl"
><A HREF="../base/Data-Typeable.html#t%3ATypeable1"
>Typeable1</A
> <A HREF="Data-Set.html#t%3ASet"
>Set</A
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="../base/Data-Foldable.html#t%3AFoldable"
>Foldable</A
> <A HREF="Data-Set.html#t%3ASet"
>Set</A
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="../base/Data-Eq.html#t%3AEq"
>Eq</A
> a => <A HREF="../base/Data-Eq.html#t%3AEq"
>Eq</A
> (<A HREF="Data-Set.html#t%3ASet"
>Set</A
> a)</TD
></TR
><TR
><TD CLASS="decl"
>(<A HREF="../base/Data-Data.html#t%3AData"
>Data</A
> a, <A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a) => <A HREF="../base/Data-Data.html#t%3AData"
>Data</A
> (<A HREF="Data-Set.html#t%3ASet"
>Set</A
> a)</TD
></TR
><TR
><TD CLASS="decl"
><A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a => <A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> (<A HREF="Data-Set.html#t%3ASet"
>Set</A
> a)</TD
></TR
><TR
><TD CLASS="decl"
>(<A HREF="../base/Text-Read.html#t%3ARead"
>Read</A
> a, <A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a) => <A HREF="../base/Text-Read.html#t%3ARead"
>Read</A
> (<A HREF="Data-Set.html#t%3ASet"
>Set</A
> a)</TD
></TR
><TR
><TD CLASS="decl"
><A HREF="../base/Text-Show.html#t%3AShow"
>Show</A
> a => <A HREF="../base/Text-Show.html#t%3AShow"
>Show</A
> (<A HREF="Data-Set.html#t%3ASet"
>Set</A
> a)</TD
></TR
><TR
><TD CLASS="decl"
><A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a => <A HREF="../base/Data-Monoid.html#t%3AMonoid"
>Monoid</A
> (<A HREF="Data-Set.html#t%3ASet"
>Set</A
> a)</TD
></TR
></TABLE
></DIV
></TD
></TR
></TABLE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section1"
><A NAME="2"
><A NAME="2"
>Operators
</A
></A
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:\\"
><A NAME="v%3A%5C%5C"
></A
></A
><B
>(\\)</B
> :: <A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a => <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(n+m)</EM
>. See <TT
><A HREF="Data-Set.html#v%3Adifference"
>difference</A
></TT
>.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section1"
><A NAME="3"
><A NAME="3"
>Query
</A
></A
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:null"
><A NAME="v%3Anull"
></A
></A
><B
>null</B
> :: <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
></TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(1)</EM
>. Is this the empty set?
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:size"
><A NAME="v%3Asize"
></A
></A
><B
>size</B
> :: <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="../ghc-prim/GHC-Types.html#t%3AInt"
>Int</A
></TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(1)</EM
>. The number of elements in the set.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:member"
><A NAME="v%3Amember"
></A
></A
><B
>member</B
> :: <A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a => a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
></TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(log n)</EM
>. Is the element in the set?
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:notMember"
><A NAME="v%3AnotMember"
></A
></A
><B
>notMember</B
> :: <A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a => a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
></TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(log n)</EM
>. Is the element not in the set?
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:isSubsetOf"
><A NAME="v%3AisSubsetOf"
></A
></A
><B
>isSubsetOf</B
> :: <A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a => <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
></TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(n+m)</EM
>. Is this a subset?
<TT
>(s1 <TT
><A HREF="Data-Set.html#v%3AisSubsetOf"
>isSubsetOf</A
></TT
> s2)</TT
> tells whether <TT
>s1</TT
> is a subset of <TT
>s2</TT
>.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:isProperSubsetOf"
><A NAME="v%3AisProperSubsetOf"
></A
></A
><B
>isProperSubsetOf</B
> :: <A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a => <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
></TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(n+m)</EM
>. Is this a proper subset? (ie. a subset but not equal).
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section1"
><A NAME="4"
><A NAME="4"
>Construction
</A
></A
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:empty"
><A NAME="v%3Aempty"
></A
></A
><B
>empty</B
> :: <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(1)</EM
>. The empty set.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:singleton"
><A NAME="v%3Asingleton"
></A
></A
><B
>singleton</B
> :: a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(1)</EM
>. Create a singleton set.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:insert"
><A NAME="v%3Ainsert"
></A
></A
><B
>insert</B
> :: <A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a => a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><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.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:delete"
><A NAME="v%3Adelete"
></A
></A
><B
>delete</B
> :: <A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a => a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(log n)</EM
>. Delete an element from a set.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section1"
><A NAME="5"
><A NAME="5"
>Combine
</A
></A
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:union"
><A NAME="v%3Aunion"
></A
></A
><B
>union</B
> :: <A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a => <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><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 <TT
><A HREF="Data-Set.html#v%3Aunion"
>union</A
></TT
> smallset).
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:unions"
><A NAME="v%3Aunions"
></A
></A
><B
>unions</B
> :: <A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a => [<A HREF="Data-Set.html#t%3ASet"
>Set</A
> a] -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a</TD
></TR
><TR
><TD CLASS="doc"
>The union of a list of sets: (<TT
><TT
><A HREF="Data-Set.html#v%3Aunions"
>unions</A
></TT
> == <TT
><A HREF="../base/Data-List.html#v%3Afoldl"
>foldl</A
></TT
> <TT
><A HREF="Data-Set.html#v%3Aunion"
>union</A
></TT
> <TT
><A HREF="Data-Set.html#v%3Aempty"
>empty</A
></TT
></TT
>).
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:difference"
><A NAME="v%3Adifference"
></A
></A
><B
>difference</B
> :: <A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a => <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(n+m)</EM
>. Difference of two sets.
The implementation uses an efficient <EM
>hedge</EM
> algorithm comparable with <EM
>hedge-union</EM
>.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:intersection"
><A NAME="v%3Aintersection"
></A
></A
><B
>intersection</B
> :: <A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a => <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a</TD
></TR
><TR
><TD 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 <TT
>(fromList [A],fromList [B])</TT
>.
</P
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section1"
><A NAME="6"
><A NAME="6"
>Filter
</A
></A
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:filter"
><A NAME="v%3Afilter"
></A
></A
><B
>filter</B
> :: <A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a => (a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
>) -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(n)</EM
>. Filter all elements that satisfy the predicate.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:partition"
><A NAME="v%3Apartition"
></A
></A
><B
>partition</B
> :: <A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a => (a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
>) -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> (<A HREF="Data-Set.html#t%3ASet"
>Set</A
> a, <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a)</TD
></TR
><TR
><TD CLASS="doc"
><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 <TT
><A HREF="Data-Set.html#v%3Asplit"
>split</A
></TT
>.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:split"
><A NAME="v%3Asplit"
></A
></A
><B
>split</B
> :: <A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a => a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> (<A HREF="Data-Set.html#t%3ASet"
>Set</A
> a, <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a)</TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(log n)</EM
>. The expression (<TT
><TT
><A HREF="Data-Set.html#v%3Asplit"
>split</A
></TT
> x set</TT
>) is a pair <TT
>(set1,set2)</TT
>
where <TT
>set1</TT
> comprises the elements of <TT
>set</TT
> less than <TT
>x</TT
> and <TT
>set2</TT
>
comprises the elements of <TT
>set</TT
> greater than <TT
>x</TT
>.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:splitMember"
><A NAME="v%3AsplitMember"
></A
></A
><B
>splitMember</B
> :: <A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a => a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> (<A HREF="Data-Set.html#t%3ASet"
>Set</A
> a, <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
>, <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a)</TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(log n)</EM
>. Performs a <TT
><A HREF="Data-Set.html#v%3Asplit"
>split</A
></TT
> but also returns whether the pivot
element was found in the original set.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section1"
><A NAME="7"
><A NAME="7"
>Map
</A
></A
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:map"
><A NAME="v%3Amap"
></A
></A
><B
>map</B
> :: (<A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a, <A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> b) => (a -> b) -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> b</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n*log n)</EM
>.
<TT
><TT
><A HREF="Data-Set.html#v%3Amap"
>map</A
></TT
> f s</TT
> is the set obtained by applying <TT
>f</TT
> to each element of <TT
>s</TT
>.
</P
><P
>It's worth noting that the size of the result may be smaller if,
for some <TT
>(x,y)</TT
>, <TT
>x /= y && f x == f y</TT
>
</P
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:mapMonotonic"
><A NAME="v%3AmapMonotonic"
></A
></A
><B
>mapMonotonic</B
> :: (a -> b) -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> b</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n)</EM
>. The
</P
><P
><TT
><TT
><A HREF="Data-Set.html#v%3AmapMonotonic"
>mapMonotonic</A
></TT
> f s == <TT
><A HREF="Data-Set.html#v%3Amap"
>map</A
></TT
> f s</TT
>, but works only when <TT
>f</TT
> 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
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section1"
><A NAME="8"
><A NAME="8"
>Fold
</A
></A
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:fold"
><A NAME="v%3Afold"
></A
></A
><B
>fold</B
> :: (a -> b -> b) -> b -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> b</TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(n)</EM
>. Fold over the elements of a set in an unspecified order.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section1"
><A NAME="9"
><A NAME="9"
>Min/Max
</A
></A
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:findMin"
><A NAME="v%3AfindMin"
></A
></A
><B
>findMin</B
> :: <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> a</TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(log n)</EM
>. The minimal element of a set.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:findMax"
><A NAME="v%3AfindMax"
></A
></A
><B
>findMax</B
> :: <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> a</TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(log n)</EM
>. The maximal element of a set.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:deleteMin"
><A NAME="v%3AdeleteMin"
></A
></A
><B
>deleteMin</B
> :: <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(log n)</EM
>. Delete the minimal element.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:deleteMax"
><A NAME="v%3AdeleteMax"
></A
></A
><B
>deleteMax</B
> :: <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(log n)</EM
>. Delete the maximal element.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:deleteFindMin"
><A NAME="v%3AdeleteFindMin"
></A
></A
><B
>deleteFindMin</B
> :: <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> (a, <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a)</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(log n)</EM
>. Delete and find the minimal element.
</P
><PRE
> deleteFindMin set = (findMin set, deleteMin set)
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:deleteFindMax"
><A NAME="v%3AdeleteFindMax"
></A
></A
><B
>deleteFindMax</B
> :: <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> (a, <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a)</TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(log n)</EM
>. Delete and find the maximal element.
</P
><PRE
> deleteFindMax set = (findMax set, deleteMax set)
</PRE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:maxView"
><A NAME="v%3AmaxView"
></A
></A
><B
>maxView</B
> :: <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> (a, <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a)</TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(log n)</EM
>. Retrieves the maximal key of the set, and the set
stripped of that element, or <TT
><A HREF="../base/Data-Maybe.html#v%3ANothing"
>Nothing</A
></TT
> if passed an empty set.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:minView"
><A NAME="v%3AminView"
></A
></A
><B
>minView</B
> :: <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="../base/Data-Maybe.html#t%3AMaybe"
>Maybe</A
> (a, <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a)</TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(log n)</EM
>. Retrieves the minimal key of the set, and the set
stripped of that element, or <TT
><A HREF="../base/Data-Maybe.html#v%3ANothing"
>Nothing</A
></TT
> if passed an empty set.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section1"
><A NAME="10"
><A NAME="10"
>Conversion
</A
></A
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section2"
><A NAME="11"
><A NAME="11"
>List
</A
></A
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:elems"
><A NAME="v%3Aelems"
></A
></A
><B
>elems</B
> :: <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> [a]</TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(n)</EM
>. The elements of a set.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:toList"
><A NAME="v%3AtoList"
></A
></A
><B
>toList</B
> :: <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> [a]</TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(n)</EM
>. Convert the set to a list of elements.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:fromList"
><A NAME="v%3AfromList"
></A
></A
><B
>fromList</B
> :: <A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a => [a] -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(n*log n)</EM
>. Create a set from a list of elements.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section2"
><A NAME="12"
><A NAME="12"
>Ordered list
</A
></A
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:toAscList"
><A NAME="v%3AtoAscList"
></A
></A
><B
>toAscList</B
> :: <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> [a]</TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(n)</EM
>. Convert the set to an ascending list of elements.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:fromAscList"
><A NAME="v%3AfromAscList"
></A
></A
><B
>fromAscList</B
> :: <A HREF="../base/Data-Eq.html#t%3AEq"
>Eq</A
> a => [a] -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><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
>
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:fromDistinctAscList"
><A NAME="v%3AfromDistinctAscList"
></A
></A
><B
>fromDistinctAscList</B
> :: [a] -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a</TD
></TR
><TR
><TD CLASS="doc"
><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
>
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section1"
><A NAME="13"
><A NAME="13"
>Debugging
</A
></A
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:showTree"
><A NAME="v%3AshowTree"
></A
></A
><B
>showTree</B
> :: <A HREF="../base/Text-Show.html#t%3AShow"
>Show</A
> a => <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="../base/Data-Char.html#t%3AString"
>String</A
></TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(n)</EM
>. Show the tree that implements the set. The tree is shown
in a compressed, hanging format.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:showTreeWith"
><A NAME="v%3AshowTreeWith"
></A
></A
><B
>showTreeWith</B
> :: <A HREF="../base/Text-Show.html#t%3AShow"
>Show</A
> a => <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
> -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
> -> <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="../base/Data-Char.html#t%3AString"
>String</A
></TD
></TR
><TR
><TD CLASS="doc"
><P
><EM
>O(n)</EM
>. The expression (<TT
>showTreeWith hang wide map</TT
>) shows
the tree that implements the set. If <TT
>hang</TT
> is
<TT
>True</TT
>, a <EM
>hanging</EM
> tree is shown otherwise a rotated tree is shown. If
<TT
>wide</TT
> is <TT
><A HREF="../ghc-prim/GHC-Bool.html#v%3ATrue"
>True</A
></TT
>, 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
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="decl"
><A NAME="v:valid"
><A NAME="v%3Avalid"
></A
></A
><B
>valid</B
> :: <A HREF="../base/Data-Ord.html#t%3AOrd"
>Ord</A
> a => <A HREF="Data-Set.html#t%3ASet"
>Set</A
> a -> <A HREF="../ghc-prim/GHC-Bool.html#t%3ABool"
>Bool</A
></TD
></TR
><TR
><TD CLASS="doc"
><EM
>O(n)</EM
>. Test if the internal set structure is valid.
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="botbar"
>Produced by <A HREF="http://www.haskell.org/haddock/"
>Haddock</A
> version 2.4.2</TD
></TR
></TABLE
></BODY
></HTML
>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
70ec89744a04da80369b4702b2c37256
>
files
>
423
