-- |
--   Module      :  Data.Edison.Coll
--   Copyright   :  Copyright (c) 2006, 2008 Robert Dockins
--   License     :  MIT; see COPYRIGHT file for terms and conditions
--
--   Maintainer  :  robdockins AT fastmail DOT fm
--   Stability   :  stable
--   Portability :  GHC, Hugs (MPTC and FD)
--
--   The standard library "Data.Set" repackaged as an Edison collection.

module Data.Edison.Coll.StandardSet (
    -- * Set type
    Set,

    -- * CollX operations
    empty,singleton,fromSeq,insert,insertSeq,union,unionSeq,delete,deleteAll,
    deleteSeq,null,size,member,count,strict,

    -- * Coll operations
    toSeq,lookup,lookupM,lookupAll,lookupWithDefault,fold,fold',
    fold1,fold1',filter,partition,strictWith,structuralInvariant,

    -- * OrdCollX operations
    deleteMin,deleteMax,unsafeInsertMin,unsafeInsertMax,unsafeFromOrdSeq,
    unsafeAppend,filterLT,filterLE,filterGT,filterGE,partitionLT_GE,
    partitionLE_GT,partitionLT_GT,

    -- * OrdColl operations
    minView,minElem,maxView,maxElem,foldr,foldr',foldl,foldl',
    foldr1,foldr1',foldl1,foldl1',toOrdSeq,unsafeMapMonotonic,

    -- * SetX operations
    intersection,difference,symmetricDifference,properSubset,subset,

    -- * Set operations
    fromSeqWith,insertWith,insertSeqWith,unionl,unionr,unionWith,
    unionSeqWith,intersectionWith,

    -- * Documentation
    moduleName
) where

import Prelude hiding (null,foldr,foldl,foldr1,foldl1,foldl',lookup,filter)
import qualified Prelude
import qualified Control.Monad.Fail as Fail
import qualified Data.List

import qualified Data.Edison.Coll as C
import qualified Data.Edison.Seq as S
import qualified Data.Edison.Seq.ListSeq as L
import Data.Edison.Coll.Defaults
import Test.QuickCheck

import qualified Data.Set as DS

-- signatures for exported functions
moduleName :: String
empty      :: Set a
singleton  :: a -> Set a
fromSeq    :: (Ord a,S.Sequence seq) => seq a -> Set a
insert     :: Ord a => a -> Set a -> Set a
insertSeq  :: (Ord a,S.Sequence seq) => seq a -> Set a -> Set a
union      :: Ord a => Set a -> Set a -> Set a
unionSeq   :: (Ord a,S.Sequence seq) => seq (Set a) -> Set a
delete     :: Ord a => a -> Set a -> Set a
deleteAll  :: Ord a => a -> Set a -> Set a
deleteSeq  :: (Ord a,S.Sequence seq) => seq a -> Set a -> Set a
null       :: Set a -> Bool
size       :: Set a -> Int
member     :: Ord a => a -> Set a -> Bool
count      :: Ord a => a -> Set a -> Int
strict     :: Ord a => Set a -> Set a

toSeq      :: (Ord a,S.Sequence seq) => Set a -> seq a
lookup     :: Ord a => a -> Set a -> a
lookupM    :: (Ord a, Monad m, Fail.MonadFail m) => a -> Set a -> m a
lookupAll  :: (Ord a,S.Sequence seq) => a -> Set a -> seq a
lookupWithDefault :: Ord a => a -> a -> Set a  -> a
fold       :: (a -> b -> b) -> b -> Set a -> b
fold1      :: (a -> a -> a) -> Set a -> a
fold'      :: (a -> b -> b) -> b -> Set a -> b
fold1'     :: (a -> a -> a) -> Set a -> a
filter     :: Ord a => (a -> Bool) -> Set a -> Set a
partition  :: Ord a => (a -> Bool) -> Set a -> (Set a, Set a)
strictWith :: Ord a => (a -> b) -> Set a -> Set a

deleteMin        :: Ord a => Set a -> Set a
deleteMax        :: Ord a => Set a -> Set a
unsafeInsertMin  :: Ord a => a -> Set a -> Set a
unsafeInsertMax  :: Ord a => a -> Set a -> Set a
unsafeFromOrdSeq :: (Ord a,S.Sequence seq) => seq a -> Set a
unsafeAppend     :: Ord a => Set a -> Set a -> Set a
filterLT         :: Ord a => a -> Set a -> Set a
filterLE         :: Ord a => a -> Set a -> Set a
filterGT         :: Ord a => a -> Set a -> Set a
filterGE         :: Ord a => a -> Set a -> Set a
partitionLT_GE   :: Ord a => a -> Set a -> (Set a, Set a)
partitionLE_GT   :: Ord a => a -> Set a -> (Set a, Set a)
partitionLT_GT   :: Ord a => a -> Set a -> (Set a, Set a)

minView       :: (Ord a, Monad m, Fail.MonadFail m) => Set a -> m (a, Set a)
minElem       :: Set a -> a
maxView       :: (Ord a, Monad m, Fail.MonadFail m) => Set a -> m (a, Set a)
maxElem       :: Set a -> a
foldr         :: (a -> b -> b) -> b -> Set a -> b
foldl         :: (b -> a -> b) -> b -> Set a -> b
foldr1        :: (a -> a -> a) -> Set a -> a
foldl1        :: (a -> a -> a) -> Set a -> a
foldr'        :: (a -> b -> b) -> b -> Set a -> b
foldl'        :: (b -> a -> b) -> b -> Set a -> b
foldr1'       :: (a -> a -> a) -> Set a -> a
foldl1'       :: (a -> a -> a) -> Set a -> a
toOrdSeq      :: (Ord a,S.Sequence seq) => Set a -> seq a

intersection  :: Ord a => Set a -> Set a -> Set a
difference    :: Ord a => Set a -> Set a -> Set a
symmetricDifference :: Ord a => Set a -> Set a -> Set a
properSubset  :: Ord a => Set a -> Set a -> Bool
subset        :: Ord a => Set a -> Set a -> Bool

fromSeqWith   :: (Ord a,S.Sequence seq) => (a -> a -> a) -> seq a -> Set a
insertWith    :: Ord a => (a -> a -> a) -> a -> Set a -> Set a
insertSeqWith :: (Ord a,S.Sequence seq) => (a -> a -> a) -> seq a -> Set a -> Set a
unionl       :: Ord a => Set a -> Set a -> Set a
unionr       :: Ord a => Set a -> Set a -> Set a
unionWith    :: Ord a => (a -> a -> a) -> Set a -> Set a -> Set a
unionSeqWith :: (Ord a,S.Sequence seq) => (a -> a -> a) -> seq (Set a) -> Set a
intersectionWith :: Ord a => (a -> a -> a) -> Set a -> Set a -> Set a
unsafeMapMonotonic :: Ord a => (a -> a) -> Set a -> Set a

moduleName :: String
moduleName = String
"Data.Edison.Coll.StandardSet"

type Set = DS.Set

structuralInvariant :: Ord a => Set a -> Bool
structuralInvariant :: forall a. Ord a => Set a -> Bool
structuralInvariant = Set a -> Bool
forall a. Ord a => Set a -> Bool
DS.valid

empty :: forall a. Set a
empty              = Set a
forall a. Set a
DS.empty
singleton :: forall a. a -> Set a
singleton          = a -> Set a
forall a. a -> Set a
DS.singleton
fromSeq :: forall a (seq :: * -> *). (Ord a, Sequence seq) => seq a -> Set a
fromSeq            = seq a -> Set a
forall c a (seq :: * -> *). (CollX c a, Sequence seq) => seq a -> c
fromSeqUsingFoldr
insert :: forall a. Ord a => a -> Set a -> Set a
insert             = a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
DS.insert
insertSeq :: forall a (seq :: * -> *).
(Ord a, Sequence seq) =>
seq a -> Set a -> Set a
insertSeq          = seq a -> Set a -> Set a
forall c a (seq :: * -> *).
(CollX c a, Sequence seq) =>
seq a -> c -> c
insertSeqUsingUnion
union :: forall a. Ord a => Set a -> Set a -> Set a
union              = Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
DS.union
unionSeq :: forall a (seq :: * -> *).
(Ord a, Sequence seq) =>
seq (Set a) -> Set a
unionSeq seq (Set a)
se        = [Set a] -> Set a
forall (f :: * -> *) a. (Foldable f, Ord a) => f (Set a) -> Set a
DS.unions ([Set a] -> Set a) -> [Set a] -> Set a
forall a b. (a -> b) -> a -> b
$ seq (Set a) -> [Set a]
forall a. seq a -> [a]
forall (s :: * -> *) a. Sequence s => s a -> [a]
S.toList seq (Set a)
se
delete :: forall a. Ord a => a -> Set a -> Set a
delete             = a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
DS.delete
deleteAll :: forall a. Ord a => a -> Set a -> Set a
deleteAll          = a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
DS.delete -- by set property
deleteSeq :: forall a (seq :: * -> *).
(Ord a, Sequence seq) =>
seq a -> Set a -> Set a
deleteSeq          = seq a -> Set a -> Set a
forall c a (seq :: * -> *).
(CollX c a, Sequence seq) =>
seq a -> c -> c
deleteSeqUsingDelete
null :: forall a. Set a -> Bool
null               = Set a -> Bool
forall a. Set a -> Bool
DS.null
size :: forall a. Set a -> Int
size               = Set a -> Int
forall a. Set a -> Int
DS.size
member :: forall a. Ord a => a -> Set a -> Bool
member             = a -> Set a -> Bool
forall a. Ord a => a -> Set a -> Bool
DS.member
count :: forall a. Ord a => a -> Set a -> Int
count              = a -> Set a -> Int
forall c a. SetX c a => a -> c -> Int
countUsingMember
strict :: forall a. Ord a => Set a -> Set a
strict Set a
xs          = (a -> () -> ()) -> () -> Set a -> ()
forall a b. (a -> b -> b) -> b -> Set a -> b
DS.fold ((() -> a -> ()) -> a -> () -> ()
forall a b c. (a -> b -> c) -> b -> a -> c
flip () -> a -> ()
forall a b. a -> b -> a
const) () Set a
xs () -> Set a -> Set a
forall a b. a -> b -> b
`seq` Set a
xs

toSeq :: forall a (seq :: * -> *). (Ord a, Sequence seq) => Set a -> seq a
toSeq              = Set a -> seq a
forall c a (seq :: * -> *). (Coll c a, Sequence seq) => c -> seq a
toSeqUsingFold
lookup :: forall a. Ord a => a -> Set a -> a
lookup a
el Set a
set      = Set a -> a
forall a. Set a -> a
DS.findMin (Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
DS.intersection Set a
set (a -> Set a
forall a. a -> Set a
DS.singleton a
el))
lookupM :: forall a (m :: * -> *).
(Ord a, Monad m, MonadFail m) =>
a -> Set a -> m a
lookupM            = a -> Set a -> m a
forall c a (m :: * -> *). (Coll c a, MonadFail m) => a -> c -> m a
lookupMUsingLookupAll
lookupAll :: forall a (seq :: * -> *).
(Ord a, Sequence seq) =>
a -> Set a -> seq a
lookupAll a
el Set a
set   = Set a -> seq a
forall c a (seq :: * -> *). (Coll c a, Sequence seq) => c -> seq a
toSeqUsingFold (Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
DS.intersection Set a
set (a -> Set a
forall a. a -> Set a
DS.singleton a
el))
lookupWithDefault :: forall a. Ord a => a -> a -> Set a -> a
lookupWithDefault  = a -> a -> Set a -> a
forall c a. Coll c a => a -> a -> c -> a
lookupWithDefaultUsingLookupAll
fold :: forall a b. (a -> b -> b) -> b -> Set a -> b
fold               = (a -> b -> b) -> b -> Set a -> b
forall a b. (a -> b -> b) -> b -> Set a -> b
DS.fold
fold' :: forall a b. (a -> b -> b) -> b -> Set a -> b
fold' a -> b -> b
f b
x Set a
xs       = (b -> a -> b) -> b -> [a] -> b
forall b a. (b -> a -> b) -> b -> [a] -> b
L.foldl' ((a -> b -> b) -> b -> a -> b
forall a b c. (a -> b -> c) -> b -> a -> c
flip a -> b -> b
f) b
x (Set a -> [a]
forall a. Set a -> [a]
DS.toList Set a
xs)
fold1 :: forall a. (a -> a -> a) -> Set a -> a
fold1 a -> a -> a
f Set a
set        = let (a
x,Set a
s) = Set a -> (a, Set a)
forall a. Set a -> (a, Set a)
DS.deleteFindMin Set a
set in (a -> a -> a) -> a -> Set a -> a
forall a b. (a -> b -> b) -> b -> Set a -> b
DS.fold a -> a -> a
f a
x Set a
s
fold1' :: forall a. (a -> a -> a) -> Set a -> a
fold1' a -> a -> a
f Set a
xs        = (a -> a -> a) -> [a] -> a
forall a. (a -> a -> a) -> [a] -> a
L.foldl1' ((a -> a -> a) -> a -> a -> a
forall a b c. (a -> b -> c) -> b -> a -> c
flip a -> a -> a
f) (Set a -> [a]
forall a. Set a -> [a]
DS.toList Set a
xs)
filter :: forall a. Ord a => (a -> Bool) -> Set a -> Set a
filter             = (a -> Bool) -> Set a -> Set a
forall a. (a -> Bool) -> Set a -> Set a
DS.filter
partition :: forall a. Ord a => (a -> Bool) -> Set a -> (Set a, Set a)
partition          = (a -> Bool) -> Set a -> (Set a, Set a)
forall a. (a -> Bool) -> Set a -> (Set a, Set a)
DS.partition
strictWith :: forall a b. Ord a => (a -> b) -> Set a -> Set a
strictWith a -> b
f Set a
xs    = (a -> () -> ()) -> () -> Set a -> ()
forall a b. (a -> b -> b) -> b -> Set a -> b
DS.fold (\a
x ()
z -> a -> b
f a
x b -> () -> ()
forall a b. a -> b -> b
`seq` ()
z) () Set a
xs () -> Set a -> Set a
forall a b. a -> b -> b
`seq` Set a
xs

deleteMin :: forall a. Ord a => Set a -> Set a
deleteMin          = Set a -> Set a
forall a. Set a -> Set a
DS.deleteMin
deleteMax :: forall a. Ord a => Set a -> Set a
deleteMax          = Set a -> Set a
forall a. Set a -> Set a
DS.deleteMax
unsafeInsertMin :: forall a. Ord a => a -> Set a -> Set a
unsafeInsertMin    = a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
DS.insert
unsafeInsertMax :: forall a. Ord a => a -> Set a -> Set a
unsafeInsertMax    = a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
DS.insert
unsafeFromOrdSeq :: forall a (seq :: * -> *). (Ord a, Sequence seq) => seq a -> Set a
unsafeFromOrdSeq   = [a] -> Set a
forall a. [a] -> Set a
DS.fromDistinctAscList ([a] -> Set a) -> (seq a -> [a]) -> seq a -> Set a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. seq a -> [a]
forall a. seq a -> [a]
forall (s :: * -> *) a. Sequence s => s a -> [a]
S.toList
unsafeAppend :: forall a. Ord a => Set a -> Set a -> Set a
unsafeAppend       = Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
DS.union
filterLT :: forall a. Ord a => a -> Set a -> Set a
filterLT a
x         = (Set a, Set a) -> Set a
forall a b. (a, b) -> a
fst ((Set a, Set a) -> Set a)
-> (Set a -> (Set a, Set a)) -> Set a -> Set a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Set a -> (Set a, Set a)
forall a. Ord a => a -> Set a -> (Set a, Set a)
DS.split a
x
filterLE :: forall a. Ord a => a -> Set a -> Set a
filterLE a
x         = (a -> Bool) -> Set a -> Set a
forall a. (a -> Bool) -> Set a -> Set a
DS.filter (a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<=a
x)
filterGT :: forall a. Ord a => a -> Set a -> Set a
filterGT a
x         = (Set a, Set a) -> Set a
forall a b. (a, b) -> b
snd ((Set a, Set a) -> Set a)
-> (Set a -> (Set a, Set a)) -> Set a -> Set a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Set a -> (Set a, Set a)
forall a. Ord a => a -> Set a -> (Set a, Set a)
DS.split a
x
filterGE :: forall a. Ord a => a -> Set a -> Set a
filterGE a
x         = (a -> Bool) -> Set a -> Set a
forall a. (a -> Bool) -> Set a -> Set a
DS.filter (a -> a -> Bool
forall a. Ord a => a -> a -> Bool
>=a
x)
partitionLT_GE :: forall a. Ord a => a -> Set a -> (Set a, Set a)
partitionLT_GE a
x   = (a -> Bool) -> Set a -> (Set a, Set a)
forall a. (a -> Bool) -> Set a -> (Set a, Set a)
DS.partition (a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<a
x)
partitionLE_GT :: forall a. Ord a => a -> Set a -> (Set a, Set a)
partitionLE_GT a
x   = (a -> Bool) -> Set a -> (Set a, Set a)
forall a. (a -> Bool) -> Set a -> (Set a, Set a)
DS.partition (a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<=a
x)
partitionLT_GT :: forall a. Ord a => a -> Set a -> (Set a, Set a)
partitionLT_GT     = a -> Set a -> (Set a, Set a)
forall a. Ord a => a -> Set a -> (Set a, Set a)
DS.split

minView :: forall a (m :: * -> *).
(Ord a, Monad m, MonadFail m) =>
Set a -> m (a, Set a)
minView Set a
set        = if Set a -> Bool
forall a. Set a -> Bool
DS.null Set a
set
                        then String -> m (a, Set a)
forall a. String -> m a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail (String
moduleName String -> String -> String
forall a. [a] -> [a] -> [a]
++ String
".minView: failed")
                        else (a, Set a) -> m (a, Set a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Set a -> (a, Set a)
forall a. Set a -> (a, Set a)
DS.deleteFindMin Set a
set)
minElem :: forall a. Set a -> a
minElem            = Set a -> a
forall a. Set a -> a
DS.findMin

maxView :: forall a (m :: * -> *).
(Ord a, Monad m, MonadFail m) =>
Set a -> m (a, Set a)
maxView Set a
set        = if Set a -> Bool
forall a. Set a -> Bool
DS.null Set a
set
                        then String -> m (a, Set a)
forall a. String -> m a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail (String
moduleName String -> String -> String
forall a. [a] -> [a] -> [a]
++ String
".maxView: failed")
                        else (a, Set a) -> m (a, Set a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Set a -> (a, Set a)
forall a. Set a -> (a, Set a)
DS.deleteFindMax Set a
set)
maxElem :: forall a. Set a -> a
maxElem            = Set a -> a
forall a. Set a -> a
DS.findMax

foldr :: forall a b. (a -> b -> b) -> b -> Set a -> b
foldr   a -> b -> b
f b
x Set a
set     = (a -> b -> b) -> b -> [a] -> b
forall a b. (a -> b -> b) -> b -> [a] -> b
L.foldr   a -> b -> b
f b
x (Set a -> [a]
forall a. Set a -> [a]
DS.toAscList Set a
set)
foldr' :: forall a b. (a -> b -> b) -> b -> Set a -> b
foldr'  a -> b -> b
f b
x Set a
set     = (a -> b -> b) -> b -> [a] -> b
forall a b. (a -> b -> b) -> b -> [a] -> b
L.foldr'  a -> b -> b
f b
x (Set a -> [a]
forall a. Set a -> [a]
DS.toAscList Set a
set)
foldr1 :: forall a. (a -> a -> a) -> Set a -> a
foldr1  a -> a -> a
f   Set a
set     = (a -> a -> a) -> [a] -> a
forall a. (a -> a -> a) -> [a] -> a
L.foldr1  a -> a -> a
f   (Set a -> [a]
forall a. Set a -> [a]
DS.toAscList Set a
set)
foldr1' :: forall a. (a -> a -> a) -> Set a -> a
foldr1' a -> a -> a
f   Set a
set     = (a -> a -> a) -> [a] -> a
forall a. (a -> a -> a) -> [a] -> a
L.foldr1' a -> a -> a
f   (Set a -> [a]
forall a. Set a -> [a]
DS.toAscList Set a
set)
foldl :: forall b a. (b -> a -> b) -> b -> Set a -> b
foldl   b -> a -> b
f b
x Set a
set     = (b -> a -> b) -> b -> [a] -> b
forall b a. (b -> a -> b) -> b -> [a] -> b
L.foldl   b -> a -> b
f b
x (Set a -> [a]
forall a. Set a -> [a]
DS.toAscList Set a
set)
foldl' :: forall b a. (b -> a -> b) -> b -> Set a -> b
foldl'  b -> a -> b
f b
x Set a
set     = (b -> a -> b) -> b -> [a] -> b
forall b a. (b -> a -> b) -> b -> [a] -> b
L.foldl'  b -> a -> b
f b
x (Set a -> [a]
forall a. Set a -> [a]
DS.toAscList Set a
set)
foldl1 :: forall a. (a -> a -> a) -> Set a -> a
foldl1  a -> a -> a
f   Set a
set     = (a -> a -> a) -> [a] -> a
forall a. (a -> a -> a) -> [a] -> a
L.foldl1  a -> a -> a
f   (Set a -> [a]
forall a. Set a -> [a]
DS.toAscList Set a
set)
foldl1' :: forall a. (a -> a -> a) -> Set a -> a
foldl1' a -> a -> a
f   Set a
set     = (a -> a -> a) -> [a] -> a
forall a. (a -> a -> a) -> [a] -> a
L.foldl1' a -> a -> a
f   (Set a -> [a]
forall a. Set a -> [a]
DS.toAscList Set a
set)

toOrdSeq :: forall a (seq :: * -> *). (Ord a, Sequence seq) => Set a -> seq a
toOrdSeq           = [a] -> seq a
forall a. [a] -> seq a
forall (s :: * -> *) a. Sequence s => [a] -> s a
S.fromList ([a] -> seq a) -> (Set a -> [a]) -> Set a -> seq a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Set a -> [a]
forall a. Set a -> [a]
DS.toAscList

intersection :: forall a. Ord a => Set a -> Set a -> Set a
intersection       = Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
DS.intersection
difference :: forall a. Ord a => Set a -> Set a -> Set a
difference         = Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
DS.difference
symmetricDifference :: forall a. Ord a => Set a -> Set a -> Set a
symmetricDifference = Set a -> Set a -> Set a
forall c a. SetX c a => c -> c -> c
symmetricDifferenceUsingDifference
properSubset :: forall a. Ord a => Set a -> Set a -> Bool
properSubset       = Set a -> Set a -> Bool
forall a. Ord a => Set a -> Set a -> Bool
DS.isProperSubsetOf
subset :: forall a. Ord a => Set a -> Set a -> Bool
subset             = Set a -> Set a -> Bool
forall a. Ord a => Set a -> Set a -> Bool
DS.isSubsetOf

fromSeqWith :: forall a (seq :: * -> *).
(Ord a, Sequence seq) =>
(a -> a -> a) -> seq a -> Set a
fromSeqWith        = (a -> a -> a) -> seq a -> Set a
forall c a (seq :: * -> *).
(Set c a, Sequence seq) =>
(a -> a -> a) -> seq a -> c
fromSeqWithUsingInsertWith
insertWith :: forall a. Ord a => (a -> a -> a) -> a -> Set a -> Set a
insertWith a -> a -> a
f a
x Set a
set = case a -> Set a -> Maybe a
forall a (m :: * -> *).
(Ord a, Monad m, MonadFail m) =>
a -> Set a -> m a
lookupM a
x Set a
set of
                        Maybe a
Nothing -> a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
DS.insert a
x Set a
set
                        Just a
x' -> a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
DS.insert (a -> a -> a
f a
x a
x') Set a
set
insertSeqWith :: forall a (seq :: * -> *).
(Ord a, Sequence seq) =>
(a -> a -> a) -> seq a -> Set a -> Set a
insertSeqWith      = (a -> a -> a) -> seq a -> Set a -> Set a
forall c a (seq :: * -> *).
(Set c a, Sequence seq) =>
(a -> a -> a) -> seq a -> c -> c
insertSeqWithUsingInsertWith
unionl :: forall a. Ord a => Set a -> Set a -> Set a
unionl             = Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
DS.union
unionr :: forall a. Ord a => Set a -> Set a -> Set a
unionr             = (Set a -> Set a -> Set a) -> Set a -> Set a -> Set a
forall a b c. (a -> b -> c) -> b -> a -> c
flip Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
DS.union
unionWith :: forall a. Ord a => (a -> a -> a) -> Set a -> Set a -> Set a
unionWith          = (a -> a -> a) -> Set a -> Set a -> Set a
forall c a. OrdSet c a => (a -> a -> a) -> c -> c -> c
unionWithUsingOrdLists
unionSeqWith :: forall a (seq :: * -> *).
(Ord a, Sequence seq) =>
(a -> a -> a) -> seq (Set a) -> Set a
unionSeqWith       = (a -> a -> a) -> seq (Set a) -> Set a
forall c a (seq :: * -> *).
(Set c a, Sequence seq) =>
(a -> a -> a) -> seq c -> c
unionSeqWithUsingReducer
intersectionWith :: forall a. Ord a => (a -> a -> a) -> Set a -> Set a -> Set a
intersectionWith   = (a -> a -> a) -> Set a -> Set a -> Set a
forall c a. OrdSet c a => (a -> a -> a) -> c -> c -> c
intersectionWithUsingOrdLists
unsafeMapMonotonic :: forall a. Ord a => (a -> a) -> Set a -> Set a
unsafeMapMonotonic = (a -> a) -> Set a -> Set a
forall a b. (a -> b) -> Set a -> Set b
DS.mapMonotonic



instance Ord a => C.CollX (Set a) a where
  {singleton :: a -> Set a
singleton = a -> Set a
forall a. a -> Set a
singleton; fromSeq :: forall (seq :: * -> *). Sequence seq => seq a -> Set a
fromSeq = seq a -> Set a
forall a (seq :: * -> *). (Ord a, Sequence seq) => seq a -> Set a
fromSeq; insert :: a -> Set a -> Set a
insert = a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
insert;
   insertSeq :: forall (seq :: * -> *). Sequence seq => seq a -> Set a -> Set a
insertSeq = seq a -> Set a -> Set a
forall a (seq :: * -> *).
(Ord a, Sequence seq) =>
seq a -> Set a -> Set a
insertSeq; unionSeq :: forall (seq :: * -> *). Sequence seq => seq (Set a) -> Set a
unionSeq = seq (Set a) -> Set a
forall a (seq :: * -> *).
(Ord a, Sequence seq) =>
seq (Set a) -> Set a
unionSeq;
   delete :: a -> Set a -> Set a
delete = a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
delete; deleteAll :: a -> Set a -> Set a
deleteAll = a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
deleteAll; deleteSeq :: forall (seq :: * -> *). Sequence seq => seq a -> Set a -> Set a
deleteSeq = seq a -> Set a -> Set a
forall a (seq :: * -> *).
(Ord a, Sequence seq) =>
seq a -> Set a -> Set a
deleteSeq;
   null :: Set a -> Bool
null = Set a -> Bool
forall a. Set a -> Bool
null; size :: Set a -> Int
size = Set a -> Int
forall a. Set a -> Int
size; member :: a -> Set a -> Bool
member = a -> Set a -> Bool
forall a. Ord a => a -> Set a -> Bool
member; count :: a -> Set a -> Int
count = a -> Set a -> Int
forall a. Ord a => a -> Set a -> Int
count;
   strict :: Set a -> Set a
strict = Set a -> Set a
forall a. Ord a => Set a -> Set a
strict;
   structuralInvariant :: Set a -> Bool
structuralInvariant = Set a -> Bool
forall a. Ord a => Set a -> Bool
structuralInvariant; instanceName :: Set a -> String
instanceName Set a
_ = String
moduleName}

instance Ord a => C.OrdCollX (Set a) a where
  {deleteMin :: Set a -> Set a
deleteMin = Set a -> Set a
forall a. Ord a => Set a -> Set a
deleteMin; deleteMax :: Set a -> Set a
deleteMax = Set a -> Set a
forall a. Ord a => Set a -> Set a
deleteMax;
   unsafeInsertMin :: a -> Set a -> Set a
unsafeInsertMin = a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
unsafeInsertMin; unsafeInsertMax :: a -> Set a -> Set a
unsafeInsertMax = a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
unsafeInsertMax;
   unsafeFromOrdSeq :: forall (seq :: * -> *). Sequence seq => seq a -> Set a
unsafeFromOrdSeq = seq a -> Set a
forall a (seq :: * -> *). (Ord a, Sequence seq) => seq a -> Set a
unsafeFromOrdSeq; unsafeAppend :: Set a -> Set a -> Set a
unsafeAppend = Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
unsafeAppend;
   filterLT :: a -> Set a -> Set a
filterLT = a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
filterLT; filterLE :: a -> Set a -> Set a
filterLE = a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
filterLE; filterGT :: a -> Set a -> Set a
filterGT = a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
filterGT;
   filterGE :: a -> Set a -> Set a
filterGE = a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
filterGE; partitionLT_GE :: a -> Set a -> (Set a, Set a)
partitionLT_GE = a -> Set a -> (Set a, Set a)
forall a. Ord a => a -> Set a -> (Set a, Set a)
partitionLT_GE;
   partitionLE_GT :: a -> Set a -> (Set a, Set a)
partitionLE_GT = a -> Set a -> (Set a, Set a)
forall a. Ord a => a -> Set a -> (Set a, Set a)
partitionLE_GT; partitionLT_GT :: a -> Set a -> (Set a, Set a)
partitionLT_GT = a -> Set a -> (Set a, Set a)
forall a. Ord a => a -> Set a -> (Set a, Set a)
partitionLT_GT}

instance Ord a => C.Coll (Set a) a where
  {toSeq :: forall (seq :: * -> *). Sequence seq => Set a -> seq a
toSeq = Set a -> seq a
forall a (seq :: * -> *). (Ord a, Sequence seq) => Set a -> seq a
toSeq; lookup :: a -> Set a -> a
lookup = a -> Set a -> a
forall a. Ord a => a -> Set a -> a
lookup; lookupM :: forall (m :: * -> *). MonadFail m => a -> Set a -> m a
lookupM = a -> Set a -> m a
forall a (m :: * -> *).
(Ord a, Monad m, MonadFail m) =>
a -> Set a -> m a
lookupM;
   lookupAll :: forall (seq :: * -> *). Sequence seq => a -> Set a -> seq a
lookupAll = a -> Set a -> seq a
forall a (seq :: * -> *).
(Ord a, Sequence seq) =>
a -> Set a -> seq a
lookupAll; lookupWithDefault :: a -> a -> Set a -> a
lookupWithDefault = a -> a -> Set a -> a
forall a. Ord a => a -> a -> Set a -> a
lookupWithDefault;
   fold :: forall b. (a -> b -> b) -> b -> Set a -> b
fold = (a -> b -> b) -> b -> Set a -> b
forall a b. (a -> b -> b) -> b -> Set a -> b
fold; fold' :: forall b. (a -> b -> b) -> b -> Set a -> b
fold' = (a -> b -> b) -> b -> Set a -> b
forall a b. (a -> b -> b) -> b -> Set a -> b
fold'; fold1 :: (a -> a -> a) -> Set a -> a
fold1 = (a -> a -> a) -> Set a -> a
forall a. (a -> a -> a) -> Set a -> a
fold1; fold1' :: (a -> a -> a) -> Set a -> a
fold1' = (a -> a -> a) -> Set a -> a
forall a. (a -> a -> a) -> Set a -> a
fold1';
   filter :: (a -> Bool) -> Set a -> Set a
filter = (a -> Bool) -> Set a -> Set a
forall a. Ord a => (a -> Bool) -> Set a -> Set a
filter; partition :: (a -> Bool) -> Set a -> (Set a, Set a)
partition = (a -> Bool) -> Set a -> (Set a, Set a)
forall a. Ord a => (a -> Bool) -> Set a -> (Set a, Set a)
partition; strictWith :: forall b. (a -> b) -> Set a -> Set a
strictWith = (a -> b) -> Set a -> Set a
forall a b. Ord a => (a -> b) -> Set a -> Set a
strictWith}

instance Ord a => C.OrdColl (Set a) a where
  {minView :: forall (m :: * -> *). MonadFail m => Set a -> m (a, Set a)
minView = Set a -> m (a, Set a)
forall a (m :: * -> *).
(Ord a, Monad m, MonadFail m) =>
Set a -> m (a, Set a)
minView; minElem :: Set a -> a
minElem = Set a -> a
forall a. Set a -> a
minElem; maxView :: forall (m :: * -> *). MonadFail m => Set a -> m (a, Set a)
maxView = Set a -> m (a, Set a)
forall a (m :: * -> *).
(Ord a, Monad m, MonadFail m) =>
Set a -> m (a, Set a)
maxView;
   maxElem :: Set a -> a
maxElem = Set a -> a
forall a. Set a -> a
maxElem; foldr :: forall b. (a -> b -> b) -> b -> Set a -> b
foldr = (a -> b -> b) -> b -> Set a -> b
forall a b. (a -> b -> b) -> b -> Set a -> b
foldr; foldr' :: forall b. (a -> b -> b) -> b -> Set a -> b
foldr' = (a -> b -> b) -> b -> Set a -> b
forall a b. (a -> b -> b) -> b -> Set a -> b
foldr'; foldl :: forall b. (b -> a -> b) -> b -> Set a -> b
foldl = (b -> a -> b) -> b -> Set a -> b
forall b a. (b -> a -> b) -> b -> Set a -> b
foldl;
   foldl' :: forall b. (b -> a -> b) -> b -> Set a -> b
foldl' = (b -> a -> b) -> b -> Set a -> b
forall b a. (b -> a -> b) -> b -> Set a -> b
foldl'; foldr1 :: (a -> a -> a) -> Set a -> a
foldr1 = (a -> a -> a) -> Set a -> a
forall a. (a -> a -> a) -> Set a -> a
foldr1; foldr1' :: (a -> a -> a) -> Set a -> a
foldr1' = (a -> a -> a) -> Set a -> a
forall a. (a -> a -> a) -> Set a -> a
foldr1';
   foldl1 :: (a -> a -> a) -> Set a -> a
foldl1 = (a -> a -> a) -> Set a -> a
forall a. (a -> a -> a) -> Set a -> a
foldl1; foldl1' :: (a -> a -> a) -> Set a -> a
foldl1' = (a -> a -> a) -> Set a -> a
forall a. (a -> a -> a) -> Set a -> a
foldl1'; toOrdSeq :: forall (seq :: * -> *). Sequence seq => Set a -> seq a
toOrdSeq = Set a -> seq a
forall a (seq :: * -> *). (Ord a, Sequence seq) => Set a -> seq a
toOrdSeq;
   unsafeMapMonotonic :: (a -> a) -> Set a -> Set a
unsafeMapMonotonic = (a -> a) -> Set a -> Set a
forall a. Ord a => (a -> a) -> Set a -> Set a
unsafeMapMonotonic }

instance Ord a => C.SetX (Set a) a where
  {intersection :: Set a -> Set a -> Set a
intersection = Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
intersection; difference :: Set a -> Set a -> Set a
difference = Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
difference;
   symmetricDifference :: Set a -> Set a -> Set a
symmetricDifference = Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
symmetricDifference;
   properSubset :: Set a -> Set a -> Bool
properSubset = Set a -> Set a -> Bool
forall a. Ord a => Set a -> Set a -> Bool
properSubset; subset :: Set a -> Set a -> Bool
subset = Set a -> Set a -> Bool
forall a. Ord a => Set a -> Set a -> Bool
subset}

instance Ord a => C.Set (Set a) a where
  {fromSeqWith :: forall (seq :: * -> *).
Sequence seq =>
(a -> a -> a) -> seq a -> Set a
fromSeqWith = (a -> a -> a) -> seq a -> Set a
forall a (seq :: * -> *).
(Ord a, Sequence seq) =>
(a -> a -> a) -> seq a -> Set a
fromSeqWith; insertWith :: (a -> a -> a) -> a -> Set a -> Set a
insertWith = (a -> a -> a) -> a -> Set a -> Set a
forall a. Ord a => (a -> a -> a) -> a -> Set a -> Set a
insertWith;
   insertSeqWith :: forall (seq :: * -> *).
Sequence seq =>
(a -> a -> a) -> seq a -> Set a -> Set a
insertSeqWith = (a -> a -> a) -> seq a -> Set a -> Set a
forall a (seq :: * -> *).
(Ord a, Sequence seq) =>
(a -> a -> a) -> seq a -> Set a -> Set a
insertSeqWith; unionl :: Set a -> Set a -> Set a
unionl = Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
unionl; unionr :: Set a -> Set a -> Set a
unionr = Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
unionr;
   unionWith :: (a -> a -> a) -> Set a -> Set a -> Set a
unionWith = (a -> a -> a) -> Set a -> Set a -> Set a
forall a. Ord a => (a -> a -> a) -> Set a -> Set a -> Set a
unionWith; unionSeqWith :: forall (seq :: * -> *).
Sequence seq =>
(a -> a -> a) -> seq (Set a) -> Set a
unionSeqWith = (a -> a -> a) -> seq (Set a) -> Set a
forall a (seq :: * -> *).
(Ord a, Sequence seq) =>
(a -> a -> a) -> seq (Set a) -> Set a
unionSeqWith;
   intersectionWith :: (a -> a -> a) -> Set a -> Set a -> Set a
intersectionWith = (a -> a -> a) -> Set a -> Set a -> Set a
forall a. Ord a => (a -> a -> a) -> Set a -> Set a -> Set a
intersectionWith}

instance Ord a => C.OrdSetX (Set a) a

instance Ord a => C.OrdSet (Set a) a