{-# LANGUAGE CPP #-}#if !defined(TESTING) && __GLASGOW_HASKELL__ >= 703{-# LANGUAGE Safe #-}#endif#include "containers.h"------------------------------------------------------------------------------- |-- Module : Data.Set-- Copyright : (c) Daan Leijen 2002-- License : BSD-style-- Maintainer : libraries@haskell.org-- Stability : provisional-- Portability : portable---- An efficient implementation of sets.---- These modules are intended to be imported qualified, to avoid name-- clashes with Prelude functions, e.g.---- > import Data.Set (Set)-- > import qualified Data.Set as Set---- The implementation of 'Set' is based on /size balanced/ binary trees (or-- trees of /bounded balance/) as described by:---- * Stephen Adams, \"/Efficient sets: a balancing act/\",-- Journal of Functional Programming 3(4):553-562, October 1993,-- <http://www.swiss.ai.mit.edu/~adams/BB/>.---- * J. Nievergelt and E.M. Reingold,-- \"/Binary search trees of bounded balance/\",-- SIAM journal of computing 2(1), March 1973.---- Note that the implementation is /left-biased/ -- the elements of a-- first argument are always preferred to the second, for example in-- 'union' or 'insert'. Of course, left-biasing can only be observed-- when equality is an equivalence relation instead of structural-- equality.---- /Warning/: The size of the set must not exceed @maxBound::Int@. Violation of-- this condition is not detected and if the size limit is exceeded, its-- behaviour is undefined.-----------------------------------------------------------------------------moduleData.Set(-- * Strictness properties-- $strictness-- * Set type#if !defined(TESTING)Set -- instance Eq,Ord,Show,Read,Data,Typeable#elseSet(..)#endif-- * Operators,(\\ )-- * Query,S.null ,size ,member ,notMember ,lookupLT ,lookupGT ,lookupLE ,lookupGE ,isSubsetOf ,isProperSubsetOf -- * Construction,empty ,singleton ,insert ,delete -- * Combine,union ,unions ,difference ,intersection -- * Filter,S.filter ,partition ,split ,splitMember ,splitRoot -- * Indexed,lookupIndex ,findIndex ,elemAt ,deleteAt -- * Map,S.map ,mapMonotonic -- * Folds,S.foldr ,S.foldl -- ** Strict folds,foldr' ,foldl' -- ** Legacy folds,fold -- * Min\/Max,findMin ,findMax ,deleteMin ,deleteMax ,deleteFindMin ,deleteFindMax ,maxView ,minView -- * Conversion-- ** List,elems ,toList ,fromList -- ** Ordered list,toAscList ,toDescList ,fromAscList ,fromDistinctAscList -- * Debugging,showTree ,showTreeWith ,valid #if defined(TESTING)-- Internals (for testing),bin,balanced,link,merge#endif)whereimportData.Set.Base asS-- $strictness---- This module satisfies the following strictness property:---- * Key arguments are evaluated to WHNF---- Here are some examples that illustrate the property:---- > delete undefined s == undefined