module Data.WeakSet
(
Set
, empty
, singleton
, set
, fromList
, fromAscList
, fromDescList
, fromDistinctAscList
, fromDistinctDescList
, powerSet
, (|&|)
, (|||)
, (|*|)
, (|+|)
, (|-|)
, (|^|)
, insert
, delete
, alterF
, 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'
, setToList
, toList
, nubSetBy
, setToMaybe
, maybeToSet
, catMaybes
, mapMaybe
, mapEither
, catEither
, traverseSet
, sequenceSet
) where
import Prelude hiding (filter, splitAt, drop, take, map)
import qualified Data.List as L
import qualified Data.Maybe as M
import Control.Applicative (liftA2)
import qualified Data.Foldable as Foldable
data Set a = Set [a]
instance Foldable Set where
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
foldr a -> b -> b
f b
d [a]
xs
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 (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)
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
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
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
`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 (t :: * -> *) a. Foldable t => t 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
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
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 b a. (b -> a -> b) -> b -> Set a -> b
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
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
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 (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t 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)