module Data.WeakSet
(
Set
, empty
, singleton
, set
, fromList
, fromAscList
, fromDescList
, fromDistinctAscList
, fromDistinctDescList
, powerSet
, (|&|)
, (|||)
, (|*|)
, (|+|)
, (|-|)
, (|^|)
, insert
, delete
, alterF
, null
, isIn
, member
, notMember
, cardinal
, size
, isIncludedIn
, isSubsetOf
, isProperSubsetOf
, disjoint
, union
, unions
, difference
, (\\)
, intersection
, cartesianProduct
, disjointUnion
, filter
, partition
, lookupIndex
, findIndex
, elemAt
, deleteAt
, take
, drop
, splitAt
, map
, mapMonotonic
, foldr
, foldl
, foldr'
, foldl'
, length
, elem
, maximum
, minimum
, sum
, product
, concat
, concat2
, concatMap
, and
, or
, any
, all
, maximumBy
, minimumBy
, notElem
, find
, setToList
, toList
, nubSetBy
, setToMaybe
, maybeToSet
, catMaybes
, mapMaybe
, mapEither
, catEither
, traverseSet
, sequenceSet
, anElement
, cartesianProductOfSets
) where
import Prelude hiding (filter, splitAt, drop, take, map, foldr, foldl, length, elem, maximum, minimum, sum, product, concat, concatMap, and, or, any, all, maximumBy, minimumBy, notElem, find, null)
import qualified Data.List as L
import qualified Data.Maybe as M
import Control.Applicative (liftA2, Alternative, (<|>))
import qualified Control.Applicative as Applicative
import qualified Data.Foldable as Foldable
data Set a = Set [a]
instance (Eq a) => Eq (Set a) where
Set a
x == :: Set a -> Set a -> Bool
== Set a
y = Set a
x Set a -> Set a -> Bool
forall a. Eq a => Set a -> Set a -> Bool
`isIncludedIn` Set a
y Bool -> Bool -> Bool
&& Set a
y Set a -> Set a -> Bool
forall a. Eq a => Set a -> Set a -> Bool
`isIncludedIn` Set a
x
instance Semigroup (Set a) where
(Set [a]
xs) <> :: Set a -> Set a -> Set a
<> (Set [a]
ys) = [a] -> Set a
forall a. [a] -> Set a
set ([a] -> Set a) -> [a] -> Set a
forall a b. (a -> b) -> a -> b
$ [a]
xs [a] -> [a] -> [a]
forall a. Semigroup a => a -> a -> a
<> [a]
ys
instance Monoid (Set a) where
mempty :: Set a
mempty = [a] -> Set a
forall a. [a] -> Set a
Set []
instance Functor Set where
fmap :: forall a b. (a -> b) -> Set a -> Set b
fmap a -> b
f (Set [a]
xs) = [b] -> Set b
forall a. [a] -> Set a
Set ([b] -> Set b) -> [b] -> Set b
forall a b. (a -> b) -> a -> b
$ a -> b
f (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [a]
xs
instance Applicative Set where
pure :: forall a. a -> Set a
pure a
x = [a] -> Set a
forall a. [a] -> Set a
Set [a
x]
<*> :: forall a b. Set (a -> b) -> Set a -> Set b
(<*>) (Set [a -> b]
fs) (Set [a]
xs) = [b] -> Set b
forall a. [a] -> Set a
Set ([b] -> Set b) -> [b] -> Set b
forall a b. (a -> b) -> a -> b
$ [a -> b]
fs [a -> b] -> [a] -> [b]
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> [a]
xs
instance Monad Set where
>>= :: forall a b. Set a -> (a -> Set b) -> Set b
(>>=) (Set [a]
xs) a -> Set b
f = [b] -> Set b
forall a. [a] -> Set a
Set ([b] -> Set b) -> [b] -> Set b
forall a b. (a -> b) -> a -> b
$ [a]
xs [a] -> (a -> [b]) -> [b]
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= (Set b -> [b]
forall a. Set a -> [a]
unsafeSetToList(Set b -> [b]) -> (a -> Set b) -> a -> [b]
forall b c a. (b -> c) -> (a -> b) -> a -> c
.a -> Set b
f)
instance Alternative Set where
<|> :: forall a. Set a -> Set a -> Set a
(<|>) = Set a -> Set a -> Set a
forall a. Set a -> Set a -> Set a
(|||)
empty :: forall a. Set a
empty = Set a
forall a. Monoid a => a
mempty
instance (Show a) => Show (Set a) where
show :: Set a -> String
show (Set [a]
xs) = String
"(set "String -> ShowS
forall a. [a] -> [a] -> [a]
++[a] -> String
forall a. Show a => a -> String
show [a]
xsString -> ShowS
forall a. [a] -> [a] -> [a]
++String
")"
empty :: Set a
empty :: forall a. Set a
empty = Set a
forall a. Monoid a => a
mempty
singleton :: a -> Set a
singleton :: forall a. a -> Set a
singleton = a -> Set a
forall (f :: * -> *) a. Applicative f => a -> f a
pure
set :: [a] -> Set a
set :: forall a. [a] -> Set a
set = [a] -> Set a
forall a. [a] -> Set a
Set
fromList :: [a] -> Set a
fromList :: forall a. [a] -> Set a
fromList = [a] -> Set a
forall a. [a] -> Set a
set
fromAscList :: [a] -> Set a
fromAscList :: forall a. [a] -> Set a
fromAscList = [a] -> Set a
forall a. [a] -> Set a
set
fromDescList :: [a] -> Set a
fromDescList :: forall a. [a] -> Set a
fromDescList = [a] -> Set a
forall a. [a] -> Set a
set
fromDistinctAscList :: [a] -> Set a
fromDistinctAscList :: forall a. [a] -> Set a
fromDistinctAscList = [a] -> Set a
forall a. [a] -> Set a
set
fromDistinctDescList :: [a] -> Set a
fromDistinctDescList :: forall a. [a] -> Set a
fromDistinctDescList = [a] -> Set a
forall a. [a] -> Set a
set
powerSet :: Set a -> Set (Set a)
powerSet :: forall a. Set a -> Set (Set a)
powerSet (Set [a]
xs) = [Set a] -> Set (Set a)
forall a. [a] -> Set a
Set ([Set a] -> Set (Set a)) -> [Set a] -> Set (Set a)
forall a b. (a -> b) -> a -> b
$ [a] -> Set a
forall a. [a] -> Set a
Set ([a] -> Set a) -> [[a]] -> [Set a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [a] -> [[a]]
forall a. [a] -> [[a]]
L.subsequences [a]
xs
insert :: a -> Set a -> Set a
insert :: forall a. a -> Set a -> Set a
insert a
x (Set [a]
xs) = [a] -> Set a
forall a. [a] -> Set a
Set (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs)
delete :: Eq a => a -> Set a -> Set a
delete :: forall a. Eq a => a -> Set a -> Set a
delete a
x (Set [a]
xs) = [a] -> Set a
forall a. [a] -> Set a
Set ([a] -> Set a) -> [a] -> Set a
forall a b. (a -> b) -> a -> b
$ (a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
L.filter (a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/= a
x) [a]
xs
alterF :: (Eq a, Functor f) => (Bool -> f Bool) -> a -> Set a -> f (Set a)
alterF :: forall a (f :: * -> *).
(Eq a, Functor f) =>
(Bool -> f Bool) -> a -> Set a -> f (Set a)
alterF Bool -> f Bool
f a
x Set a
s
| a
x a -> Set a -> Bool
forall a. Eq a => a -> Set a -> Bool
`isIn` Set a
s = (\Bool
b -> if Bool
b then Set a
s else a -> Set a -> Set a
forall a. Eq a => a -> Set a -> Set a
delete a
x Set a
s) (Bool -> Set a) -> f Bool -> f (Set a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (Bool -> f Bool
f Bool
True)
| Bool
otherwise = (\Bool
b -> if Bool
b then a -> Set a -> Set a
forall a. a -> Set a -> Set a
insert a
x Set a
s else Set a
s) (Bool -> Set a) -> f Bool -> f (Set a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (Bool -> f Bool
f Bool
False)
null :: Set a -> Bool
null :: forall a. Set a -> Bool
null (Set [a]
xs) = [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
Foldable.null [a]
xs
isIn :: (Eq a) => a -> Set a -> Bool
isIn :: forall a. Eq a => a -> Set a -> Bool
isIn a
x = (a -> [a] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
Foldable.elem a
x)([a] -> Bool) -> (Set a -> [a]) -> Set a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Set a -> [a]
forall a. Set a -> [a]
unsafeSetToList
member :: Eq a => a -> Set a -> Bool
member :: forall a. Eq a => a -> Set a -> Bool
member = a -> Set a -> Bool
forall a. Eq a => a -> Set a -> Bool
isIn
notMember :: Eq a => a -> Set a -> Bool
notMember :: forall a. Eq a => a -> Set a -> Bool
notMember a
x Set a
s = Bool -> Bool
not (Bool -> Bool) -> Bool -> Bool
forall a b. (a -> b) -> a -> b
$ a -> Set a -> Bool
forall a. Eq a => a -> Set a -> Bool
member a
x Set a
s
cardinal :: (Eq a) => Set a -> Int
cardinal :: forall a. Eq a => Set a -> Int
cardinal = ([a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
Foldable.length)([a] -> Int) -> (Set a -> [a]) -> Set a -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Set a -> [a]
forall a. Eq a => Set a -> [a]
setToList
size :: (Eq a) => Set a -> Int
size :: forall a. Eq a => Set a -> Int
size = Set a -> Int
forall a. Eq a => Set a -> Int
cardinal
isIncludedIn :: (Eq a) => Set a -> Set a -> Bool
(Set []) isIncludedIn :: forall a. Eq a => Set a -> Set a -> Bool
`isIncludedIn` Set a
_ = Bool
True
(Set (a
x:[a]
xs)) `isIncludedIn` (Set [a]
ys)
| a
x a -> [a] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`Foldable.elem` [a]
ys = ([a] -> Set a
forall a. [a] -> Set a
Set [a]
xs) Set a -> Set a -> Bool
forall a. Eq a => Set a -> Set a -> Bool
`isIncludedIn` ([a] -> Set a
forall a. [a] -> Set a
Set [a]
ys)
| Bool
otherwise = Bool
False
isSubsetOf :: (Eq a) => Set a -> Set a -> Bool
isSubsetOf :: forall a. Eq a => Set a -> Set a -> Bool
isSubsetOf = Set a -> Set a -> Bool
forall a. Eq a => Set a -> Set a -> Bool
isIncludedIn
isProperSubsetOf :: (Eq a) => Set a -> Set a -> Bool
isProperSubsetOf :: forall a. Eq a => Set a -> Set a -> Bool
isProperSubsetOf Set a
x Set a
y = Set a
x Set a -> Set a -> Bool
forall a. Eq a => a -> a -> Bool
/= Set a
y Bool -> Bool -> Bool
&& Set a
x Set a -> Set a -> Bool
forall a. Eq a => Set a -> Set a -> Bool
`isIncludedIn` Set a
y
disjoint :: (Eq a) => Set a -> Set a -> Bool
disjoint :: forall a. Eq a => Set a -> Set a -> Bool
disjoint Set a
x Set a
y = Set a -> Bool
forall a. Set a -> Bool
null (Set a -> Bool) -> Set a -> Bool
forall a b. (a -> b) -> a -> b
$ Set a
x Set a -> Set a -> Set a
forall a. Eq a => Set a -> Set a -> Set a
`intersection` Set a
y
union :: Set a -> Set a -> Set a
union :: forall a. Set a -> Set a -> Set a
union (Set [a]
xs) (Set [a]
ys) = [a] -> Set a
forall a. [a] -> Set a
Set ([a]
xs [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a]
ys)
unions :: (Foldable f) => f (Set a) -> Set a
unions :: forall (f :: * -> *) a. Foldable f => f (Set a) -> Set a
unions = (Set a -> Set a -> Set a) -> Set a -> f (Set a) -> Set a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
L.foldl Set a -> Set a -> Set a
forall a. Set a -> Set a -> Set a
union Set a
forall a. Set a
empty
difference :: (Eq a) => Set a -> Set a -> Set a
difference :: forall a. Eq a => Set a -> Set a -> Set a
difference (Set [a]
xs) Set a
y = [a] -> Set a
forall a. [a] -> Set a
Set ([a] -> Set a) -> [a] -> Set a
forall a b. (a -> b) -> a -> b
$ (a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
L.filter (Bool -> Bool
not(Bool -> Bool) -> (a -> Bool) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(a -> Set a -> Bool
forall a. Eq a => a -> Set a -> Bool
`isIn` Set a
y)) [a]
xs
(\\) :: (Eq a) => Set a -> Set a -> Set a
\\ :: forall a. Eq a => Set a -> Set a -> Set a
(\\) = Set a -> Set a -> Set a
forall a. Eq a => Set a -> Set a -> Set a
difference
intersection :: (Eq a) => Set a -> Set a -> Set a
intersection :: forall a. Eq a => Set a -> Set a -> Set a
intersection (Set [a]
xs) Set a
y = [a] -> Set a
forall a. [a] -> Set a
Set ([a] -> Set a) -> [a] -> Set a
forall a b. (a -> b) -> a -> b
$ (a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
L.filter (a -> Set a -> Bool
forall a. Eq a => a -> Set a -> Bool
`isIn` Set a
y) [a]
xs
cartesianProduct :: Set a -> Set b -> Set (a,b)
cartesianProduct :: forall a b. Set a -> Set b -> Set (a, b)
cartesianProduct (Set [a]
xs) (Set [b]
ys) = [(a, b)] -> Set (a, b)
forall a. [a] -> Set a
Set ([(a, b)] -> Set (a, b)) -> [(a, b)] -> Set (a, b)
forall a b. (a -> b) -> a -> b
$ [(a
x,b
y) | a
x <- [a]
xs, b
y <- [b]
ys]
disjointUnion :: Set a -> Set b -> Set (Either a b)
disjointUnion :: forall a b. Set a -> Set b -> Set (Either a b)
disjointUnion (Set [a]
xs) (Set [b]
ys) = [Either a b] -> Set (Either a b)
forall a. [a] -> Set a
Set ([Either a b] -> Set (Either a b))
-> [Either a b] -> Set (Either a b)
forall a b. (a -> b) -> a -> b
$ [a -> Either a b
forall a b. a -> Either a b
Left a
x | a
x <- [a]
xs] [Either a b] -> [Either a b] -> [Either a b]
forall a. [a] -> [a] -> [a]
++ [b -> Either a b
forall a b. b -> Either a b
Right b
y | b
y <- [b]
ys]
filter :: (a -> Bool) -> Set a -> Set a
filter :: forall a. (a -> Bool) -> Set a -> Set a
filter a -> Bool
p (Set [a]
xs) = [a] -> Set a
forall a. [a] -> Set a
Set ([a] -> Set a) -> [a] -> Set a
forall a b. (a -> b) -> a -> b
$ (a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
L.filter a -> Bool
p [a]
xs
partition :: (a -> Bool) -> Set a -> (Set a, Set a)
partition :: forall a. (a -> Bool) -> Set a -> (Set a, Set a)
partition a -> Bool
p (Set [a]
xs) = ([a] -> Set a
forall a. [a] -> Set a
Set ([a] -> Set a) -> [a] -> Set a
forall a b. (a -> b) -> a -> b
$ (a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
L.filter a -> Bool
p [a]
xs, [a] -> Set a
forall a. [a] -> Set a
Set ([a] -> Set a) -> [a] -> Set a
forall a b. (a -> b) -> a -> b
$ (a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
L.filter (Bool -> Bool
not(Bool -> Bool) -> (a -> Bool) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
.a -> Bool
p) [a]
xs)
lookupIndex :: (Eq a) => a -> Set a -> Maybe Int
lookupIndex :: forall a. Eq a => a -> Set a -> Maybe Int
lookupIndex a
k Set a
x = a -> [a] -> Maybe Int
forall a. Eq a => a -> [a] -> Maybe Int
L.elemIndex a
k (Set a -> [a]
forall a. Eq a => Set a -> [a]
setToList Set a
x)
findIndex :: (Eq a) => a -> Set a -> Int
findIndex :: forall a. Eq a => a -> Set a -> Int
findIndex a
k Set a
x
| Maybe Int -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
Foldable.null Maybe Int
index = String -> Int
forall a. HasCallStack => String -> a
error String
"WeakSet.findIndex: element is not in the set"
| Bool
otherwise = Int
i
where
index :: Maybe Int
index = a -> Set a -> Maybe Int
forall a. Eq a => a -> Set a -> Maybe Int
lookupIndex a
k Set a
x
Just Int
i = Maybe Int
index
elemAt :: (Eq a) => Int -> Set a -> a
elemAt :: forall a. Eq a => Int -> Set a -> a
elemAt Int
i Set a
s
| Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 Bool -> Bool -> Bool
|| Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= ([a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
Foldable.length [a]
xs) = String -> a
forall a. HasCallStack => String -> a
error String
"WeakSet.elemAt: index out of range"
| Bool
otherwise = [a] -> Int -> a
forall a. [a] -> Int -> a
(L.!!) [a]
xs Int
i
where
xs :: [a]
xs = Set a -> [a]
forall a. Eq a => Set a -> [a]
setToList Set a
s
deleteAt :: (Eq a) => Int -> Set a -> Set a
deleteAt :: forall a. Eq a => Int -> Set a -> Set a
deleteAt Int
i Set a
s = (a -> Bool) -> Set a -> Set a
forall a. (a -> Bool) -> Set a -> Set a
filter (a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/= (Int -> Set a -> a
forall a. Eq a => Int -> Set a -> a
elemAt Int
i Set a
s)) Set a
s
take :: (Eq a) => Int -> Set a -> Set a
take :: forall a. Eq a => Int -> Set a -> Set a
take Int
i Set a
s = [a] -> Set a
forall a. [a] -> Set a
Set ([a] -> Set a) -> [a] -> Set a
forall a b. (a -> b) -> a -> b
$ Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
L.take Int
i (Set a -> [a]
forall a. Eq a => Set a -> [a]
setToList Set a
s)
drop :: (Eq a) => Int -> Set a -> Set a
drop :: forall a. Eq a => Int -> Set a -> Set a
drop Int
i Set a
s = [a] -> Set a
forall a. [a] -> Set a
Set ([a] -> Set a) -> [a] -> Set a
forall a b. (a -> b) -> a -> b
$ Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
L.drop Int
i (Set a -> [a]
forall a. Eq a => Set a -> [a]
setToList Set a
s)
splitAt :: (Eq a) => Int -> Set a -> (Set a, Set a)
splitAt :: forall a. Eq a => Int -> Set a -> (Set a, Set a)
splitAt Int
i Set a
s = ([a] -> Set a
forall a. [a] -> Set a
Set [a]
x, [a] -> Set a
forall a. [a] -> Set a
Set [a]
y)
where
([a]
x,[a]
y) = Int -> [a] -> ([a], [a])
forall a. Int -> [a] -> ([a], [a])
L.splitAt Int
i (Set a -> [a]
forall a. Eq a => Set a -> [a]
setToList Set a
s)
map :: (a -> b) -> Set a -> Set b
map :: forall a b. (a -> b) -> Set a -> Set b
map = (a -> b) -> Set a -> Set b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap
mapMonotonic :: (a -> b) -> Set a -> Set b
mapMonotonic :: forall a b. (a -> b) -> Set a -> Set b
mapMonotonic = (a -> b) -> Set a -> Set b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap
foldr' :: (a -> b -> b) -> b -> Set a -> b
foldr' :: forall a b. (a -> b -> b) -> b -> Set a -> b
foldr' a -> b -> b
f b
d (Set [a]
xs) = (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Foldable.foldr' a -> b -> b
f b
d [a]
xs
foldl' :: (a -> b -> a) -> a -> Set b -> a
foldl' :: forall a b. (a -> b -> a) -> a -> Set b -> a
foldl' a -> b -> a
f a
d (Set [b]
xs) = (a -> b -> a) -> a -> [b] -> a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
Foldable.foldl' a -> b -> a
f a
d [b]
xs
unsafeSetToList :: Set a -> [a]
unsafeSetToList :: forall a. Set a -> [a]
unsafeSetToList (Set [a]
xs) = [a]
xs
setToList :: (Eq a) => Set a -> [a]
setToList :: forall a. Eq a => Set a -> [a]
setToList (Set [a]
xs) = [a] -> [a]
forall a. Eq a => [a] -> [a]
L.nub [a]
xs
toList :: (Eq a) => Set a -> [a]
toList :: forall a. Eq a => Set a -> [a]
toList = Set a -> [a]
forall a. Eq a => Set a -> [a]
setToList
setToMaybe :: Set a -> Maybe a
setToMaybe :: forall a. Set a -> Maybe a
setToMaybe = ([a] -> Maybe a
forall a. [a] -> Maybe a
M.listToMaybe)([a] -> Maybe a) -> (Set a -> [a]) -> Set a -> Maybe a
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Set a -> [a]
forall a. Set a -> [a]
unsafeSetToList
maybeToSet :: Maybe a -> Set a
maybeToSet :: forall a. Maybe a -> Set a
maybeToSet Maybe a
x = [a] -> Set a
forall a. [a] -> Set a
Set ([a] -> Set a) -> [a] -> Set a
forall a b. (a -> b) -> a -> b
$ (Maybe a -> [a]
forall a. Maybe a -> [a]
M.maybeToList) Maybe a
x
catMaybes :: Set (Maybe a) -> Set a
catMaybes :: forall a. Set (Maybe a) -> Set a
catMaybes = [a] -> Set a
forall a. [a] -> Set a
set([a] -> Set a) -> (Set (Maybe a) -> [a]) -> Set (Maybe a) -> Set a
forall b c a. (b -> c) -> (a -> b) -> a -> c
.([Maybe a] -> [a]
forall a. [Maybe a] -> [a]
M.catMaybes)([Maybe a] -> [a])
-> (Set (Maybe a) -> [Maybe a]) -> Set (Maybe a) -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Set (Maybe a) -> [Maybe a]
forall a. Set a -> [a]
unsafeSetToList
mapMaybe :: (a -> Maybe b) -> Set a -> Set b
mapMaybe :: forall a b. (a -> Maybe b) -> Set a -> Set b
mapMaybe a -> Maybe b
f = [b] -> Set b
forall a. [a] -> Set a
set([b] -> Set b) -> (Set a -> [b]) -> Set a -> Set b
forall b c a. (b -> c) -> (a -> b) -> a -> c
.((a -> Maybe b) -> [a] -> [b]
forall a b. (a -> Maybe b) -> [a] -> [b]
M.mapMaybe a -> Maybe b
f)([a] -> [b]) -> (Set a -> [a]) -> Set a -> [b]
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Set a -> [a]
forall a. Set a -> [a]
unsafeSetToList
catEither :: Set (Either a b) -> (Set a, Set b)
catEither :: forall a b. Set (Either a b) -> (Set a, Set b)
catEither (Set []) = (Set a
forall a. Set a
empty,Set b
forall a. Set a
empty)
catEither (Set (Either a b
x:[Either a b]
xs))
| Either a b -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
Foldable.null Either a b
x = (a -> Set a -> Set a
forall a. a -> Set a -> Set a
insert a
l Set a
ls, Set b
rs)
| Bool
otherwise = (Set a
ls, b -> Set b -> Set b
forall a. a -> Set a -> Set a
insert b
r Set b
rs)
where
(Set a
ls,Set b
rs) = Set (Either a b) -> (Set a, Set b)
forall a b. Set (Either a b) -> (Set a, Set b)
catEither ([Either a b] -> Set (Either a b)
forall a. [a] -> Set a
Set [Either a b]
xs)
Right b
r = Either a b
x
Left a
l = Either a b
x
mapEither :: (a -> Either b c) -> Set a -> (Set b, Set c)
mapEither :: forall a b c. (a -> Either b c) -> Set a -> (Set b, Set c)
mapEither a -> Either b c
_ (Set []) = (Set b
forall a. Set a
empty, Set c
forall a. Set a
empty)
mapEither a -> Either b c
f (Set (a
x:[a]
xs))
| Either b c -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
Foldable.null Either b c
result = (b -> Set b -> Set b
forall a. a -> Set a -> Set a
insert b
l Set b
ls, Set c
rs)
| Bool
otherwise = (Set b
ls, c -> Set c -> Set c
forall a. a -> Set a -> Set a
insert c
r Set c
rs)
where
(Set b
ls,Set c
rs) = (a -> Either b c) -> Set a -> (Set b, Set c)
forall a b c. (a -> Either b c) -> Set a -> (Set b, Set c)
mapEither a -> Either b c
f ([a] -> Set a
forall a. [a] -> Set a
Set [a]
xs)
result :: Either b c
result = a -> Either b c
f a
x
Left b
l = Either b c
result
Right c
r = Either b c
result
nubSetBy :: (a -> a -> Bool) -> Set a -> [a]
nubSetBy :: forall a. (a -> a -> Bool) -> Set a -> [a]
nubSetBy a -> a -> Bool
f (Set [a]
xs) = (a -> a -> Bool) -> [a] -> [a]
forall a. (a -> a -> Bool) -> [a] -> [a]
L.nubBy a -> a -> Bool
f [a]
xs
(|&|) :: (Eq a) => Set a -> Set a -> Set a
|&| :: forall a. Eq a => Set a -> Set a -> Set a
(|&|) = Set a -> Set a -> Set a
forall a. Eq a => Set a -> Set a -> Set a
intersection
(|||) :: Set a -> Set a -> Set a
||| :: forall a. Set a -> Set a -> Set a
(|||) = Set a -> Set a -> Set a
forall a. Set a -> Set a -> Set a
union
(|*|) :: Set a -> Set b -> Set (a,b)
|*| :: forall a b. Set a -> Set b -> Set (a, b)
(|*|) = Set a -> Set b -> Set (a, b)
forall a b. Set a -> Set b -> Set (a, b)
cartesianProduct
(|+|) :: Set a -> Set b -> Set (Either a b)
|+| :: forall a b. Set a -> Set b -> Set (Either a b)
(|+|) = Set a -> Set b -> Set (Either a b)
forall a b. Set a -> Set b -> Set (Either a b)
disjointUnion
(|^|) :: (Eq a) => Set a -> Int -> Set [a]
|^| :: forall a. Eq a => Set a -> Int -> Set [a]
(|^|) Set a
_ Int
0 = [[a]] -> Set [a]
forall a. [a] -> Set a
Set [[]]
(|^|) Set a
s Int
n = (:) (a -> [a] -> [a]) -> Set a -> Set ([a] -> [a])
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Set a
s Set ([a] -> [a]) -> Set [a] -> Set [a]
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> (Set a
s Set a -> Int -> Set [a]
forall a. Eq a => Set a -> Int -> Set [a]
|^| (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1))
(|-|) :: (Eq a) => Set a -> Set a -> Set a
|-| :: forall a. Eq a => Set a -> Set a -> Set a
(|-|) = Set a -> Set a -> Set a
forall a. Eq a => Set a -> Set a -> Set a
difference
traverseSet :: (Applicative f, Eq a) => (a -> f b) -> Set a -> f (Set b)
traverseSet :: forall (f :: * -> *) a b.
(Applicative f, Eq a) =>
(a -> f b) -> Set a -> f (Set b)
traverseSet a -> f b
f Set a
s = (a -> f (Set b) -> f (Set b)) -> f (Set b) -> Set a -> f (Set b)
forall a b. Eq a => (a -> b -> b) -> b -> Set a -> b
foldr (\a
x f (Set b)
ys -> (b -> Set b -> Set b) -> f b -> f (Set b) -> f (Set b)
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 b -> Set b -> Set b
forall a. a -> Set a -> Set a
insert (a -> f b
f a
x) f (Set b)
ys) (Set b -> f (Set b)
forall (f :: * -> *) a. Applicative f => a -> f a
pure Set b
forall a. Monoid a => a
mempty) ([a] -> Set a
forall a. [a] -> Set a
set([a] -> Set a) -> (Set a -> [a]) -> Set a -> Set a
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Set a -> [a]
forall a. Eq a => Set a -> [a]
setToList (Set a -> Set a) -> Set a -> Set a
forall a b. (a -> b) -> a -> b
$ Set a
s)
sequenceSet :: (Applicative f, Eq (f a)) => Set (f a) -> f (Set a)
sequenceSet :: forall (f :: * -> *) a.
(Applicative f, Eq (f a)) =>
Set (f a) -> f (Set a)
sequenceSet (Set [f a]
xs) = [a] -> Set a
forall a. [a] -> Set a
Set ([a] -> Set a) -> f [a] -> f (Set a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [f a] -> f [a]
forall (t :: * -> *) (f :: * -> *) a.
(Traversable t, Applicative f) =>
t (f a) -> f (t a)
sequenceA ([f a] -> [f a]
forall a. Eq a => [a] -> [a]
L.nub [f a]
xs)
anElement :: Set a -> a
anElement :: forall a. Set a -> a
anElement (Set []) = String -> a
forall a. HasCallStack => String -> a
error String
"Data.WeakSet.anElement: empty set"
anElement (Set (a
x:[a]
xs)) = a
x
cartesianProductOfSets :: (Monoid (m a), Monad m, Foldable m, Eq a) => m (Set a) -> Set (m a)
cartesianProductOfSets :: forall (m :: * -> *) a.
(Monoid (m a), Monad m, Foldable m, Eq a) =>
m (Set a) -> Set (m a)
cartesianProductOfSets m (Set a)
t = (Set a -> Set (m a) -> Set (m a))
-> Set (m a) -> m (Set a) -> Set (m a)
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Foldable.foldr (\Set a
s Set (m a)
result -> (m a -> m a -> m a
forall a. Semigroup a => a -> a -> a
(<>)(m a -> m a -> m a) -> (a -> m a) -> a -> m a -> m a
forall b c a. (b -> c) -> (a -> b) -> a -> c
.a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (a -> m a -> m a) -> Set a -> Set (m a -> m a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Set a
s) Set (m a -> m a) -> Set (m a) -> Set (m a)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> Set (m a)
result) ([m a] -> Set (m a)
forall a. [a] -> Set a
set ([m a] -> Set (m a)) -> [m a] -> Set (m a)
forall a b. (a -> b) -> a -> b
$ m a -> [m a]
forall (f :: * -> *) a. Applicative f => a -> f a
pure (m a -> [m a]) -> m a -> [m a]
forall a b. (a -> b) -> a -> b
$ m a
forall a. Monoid a => a
mempty) m (Set a)
t
foldr :: (Eq a) => (a -> b -> b) -> b -> Set a -> b
foldr :: forall a b. Eq a => (a -> b -> b) -> b -> Set a -> b
foldr a -> b -> b
f b
d Set a
s = (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Foldable.foldr a -> b -> b
f b
d (Set a -> [a]
forall a. Eq a => Set a -> [a]
setToList Set a
s)
foldl :: (Eq b) => (a -> b -> a) -> a -> Set b -> a
foldl :: forall b a. Eq b => (a -> b -> a) -> a -> Set b -> a
foldl a -> b -> a
f a
d Set b
s = (a -> b -> a) -> a -> [b] -> a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
Foldable.foldl a -> b -> a
f a
d (Set b -> [b]
forall a. Eq a => Set a -> [a]
setToList Set b
s)
length :: (Eq a) => Set a -> Int
length :: forall a. Eq a => Set a -> Int
length = Set a -> Int
forall a. Eq a => Set a -> Int
cardinal
elem :: (Eq a) => a -> Set a -> Bool
elem :: forall a. Eq a => a -> Set a -> Bool
elem a
a (Set [a]
xs) = a -> [a] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
Foldable.elem a
a [a]
xs
maximum :: (Ord a) => Set a -> a
maximum :: forall a. Ord a => Set a -> a
maximum = ([a] -> a
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
Foldable.maximum)([a] -> a) -> (Set a -> [a]) -> Set a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Set a -> [a]
forall a. Set a -> [a]
unsafeSetToList
minimum :: (Ord a) => Set a -> a
minimum :: forall a. Ord a => Set a -> a
minimum = ([a] -> a
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
Foldable.minimum)([a] -> a) -> (Set a -> [a]) -> Set a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Set a -> [a]
forall a. Set a -> [a]
unsafeSetToList
sum :: (Eq a, Num a) => Set a -> a
sum :: forall a. (Eq a, Num a) => Set a -> a
sum = ([a] -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
Foldable.sum)([a] -> a) -> (Set a -> [a]) -> Set a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Set a -> [a]
forall a. Eq a => Set a -> [a]
setToList
product :: (Eq a, Num a) => Set a -> a
product :: forall a. (Eq a, Num a) => Set a -> a
product = ([a] -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
Foldable.product)([a] -> a) -> (Set a -> [a]) -> Set a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Set a -> [a]
forall a. Eq a => Set a -> [a]
setToList
concat :: (Eq a) => Set [a] -> [a]
concat :: forall a. Eq a => Set [a] -> [a]
concat = ([[a]] -> [a]
forall (t :: * -> *) a. Foldable t => t [a] -> [a]
Foldable.concat)([[a]] -> [a]) -> (Set [a] -> [[a]]) -> Set [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Set [a] -> [[a]]
forall a. Eq a => Set a -> [a]
setToList
concat2 :: Set (Set a) -> Set a
concat2 :: forall a. Set (Set a) -> Set a
concat2 (Set [Set a]
xs) = [a] -> Set a
forall a. [a] -> Set a
Set ([a] -> Set a) -> [a] -> Set a
forall a b. (a -> b) -> a -> b
$ [a
x | Set a
s <- [Set a]
xs, a
x <- (Set a -> [a]
forall a. Set a -> [a]
unsafeSetToList Set a
s)]
concatMap :: (Eq b) => (a -> [b]) -> Set a -> [b]
concatMap :: forall b a. Eq b => (a -> [b]) -> Set a -> [b]
concatMap a -> [b]
f Set a
s = Set [b] -> [b]
forall a. Eq a => Set [a] -> [a]
concat (Set [b] -> [b]) -> Set [b] -> [b]
forall a b. (a -> b) -> a -> b
$ a -> [b]
f (a -> [b]) -> Set a -> Set [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Set a
s
and :: Set Bool -> Bool
and :: Set Bool -> Bool
and = ([Bool] -> Bool
forall (t :: * -> *). Foldable t => t Bool -> Bool
Foldable.and)([Bool] -> Bool) -> (Set Bool -> [Bool]) -> Set Bool -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Set Bool -> [Bool]
forall a. Set a -> [a]
unsafeSetToList
or :: Set Bool -> Bool
or :: Set Bool -> Bool
or = ([Bool] -> Bool
forall (t :: * -> *). Foldable t => t Bool -> Bool
Foldable.or)([Bool] -> Bool) -> (Set Bool -> [Bool]) -> Set Bool -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Set Bool -> [Bool]
forall a. Set a -> [a]
unsafeSetToList
any :: (a -> Bool) -> Set a -> Bool
any :: forall a. (a -> Bool) -> Set a -> Bool
any a -> Bool
f (Set [a]
xs) = (a -> Bool) -> [a] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
Foldable.any a -> Bool
f ([a]
xs)
all :: (a -> Bool) -> Set a -> Bool
all :: forall a. (a -> Bool) -> Set a -> Bool
all a -> Bool
f (Set [a]
xs) = (a -> Bool) -> [a] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
Foldable.all a -> Bool
f ([a]
xs)
maximumBy :: (a -> a -> Ordering) -> Set a -> a
maximumBy :: forall a. (a -> a -> Ordering) -> Set a -> a
maximumBy a -> a -> Ordering
f (Set [a]
xs) = (a -> a -> Ordering) -> [a] -> a
forall (t :: * -> *) a.
Foldable t =>
(a -> a -> Ordering) -> t a -> a
Foldable.maximumBy a -> a -> Ordering
f [a]
xs
minimumBy :: (a -> a -> Ordering) -> Set a -> a
minimumBy :: forall a. (a -> a -> Ordering) -> Set a -> a
minimumBy a -> a -> Ordering
f (Set [a]
xs) = (a -> a -> Ordering) -> [a] -> a
forall (t :: * -> *) a.
Foldable t =>
(a -> a -> Ordering) -> t a -> a
Foldable.minimumBy a -> a -> Ordering
f [a]
xs
notElem :: (Eq a) => a -> Set a -> Bool
notElem :: forall a. Eq a => a -> Set a -> Bool
notElem a
x Set a
s = Bool -> Bool
not (Bool -> Bool) -> Bool -> Bool
forall a b. (a -> b) -> a -> b
$ a -> Set a -> Bool
forall a. Eq a => a -> Set a -> Bool
elem a
x Set a
s
find :: (a -> Bool) -> Set a -> Maybe a
find :: forall a. (a -> Bool) -> Set a -> Maybe a
find a -> Bool
f (Set [a]
xs) = (a -> Bool) -> [a] -> Maybe a
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Maybe a
Foldable.find a -> Bool
f [a]
xs