module Math.Common.ListSet where
import Data.List (group,sort)
toListSet :: [b] -> [b]
toListSet xs :: [b]
xs = ([b] -> b) -> [[b]] -> [b]
forall a b. (a -> b) -> [a] -> [b]
map [b] -> b
forall a. [a] -> a
head ([[b]] -> [b]) -> [[b]] -> [b]
forall a b. (a -> b) -> a -> b
$ [b] -> [[b]]
forall a. Eq a => [a] -> [[a]]
group ([b] -> [[b]]) -> [b] -> [[b]]
forall a b. (a -> b) -> a -> b
$ [b] -> [b]
forall a. Ord a => [a] -> [a]
sort [b]
xs
isListSet :: [a] -> Bool
isListSet (x1 :: a
x1:x2 :: a
x2:xs :: [a]
xs) = a
x1 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x2 Bool -> Bool -> Bool
&& [a] -> Bool
isListSet (a
x2a -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs)
isListSet _ = Bool
True
union :: [a] -> [a] -> [a]
union (x :: a
x:xs :: [a]
xs) (y :: a
y:ys :: [a]
ys) =
case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
x a
y of
LT -> a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a] -> [a] -> [a]
union [a]
xs (a
ya -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
ys)
EQ -> a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a] -> [a] -> [a]
union [a]
xs [a]
ys
GT -> a
y a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a] -> [a] -> [a]
union (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs) [a]
ys
union [] ys :: [a]
ys = [a]
ys
union xs :: [a]
xs [] = [a]
xs
intersect :: [a] -> [a] -> [a]
intersect (x :: a
x:xs :: [a]
xs) (y :: a
y:ys :: [a]
ys) =
case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
x a
y of
LT -> [a] -> [a] -> [a]
intersect [a]
xs (a
ya -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
ys)
EQ -> a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a] -> [a] -> [a]
intersect [a]
xs [a]
ys
GT -> [a] -> [a] -> [a]
intersect (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs) [a]
ys
intersect _ _ = []
(x :: a
x:xs :: [a]
xs) \\ :: [a] -> [a] -> [a]
\\ (y :: a
y:ys :: [a]
ys) =
case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
x a
y of
LT -> a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: ([a]
xs [a] -> [a] -> [a]
\\ (a
ya -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
ys))
EQ -> [a]
xs [a] -> [a] -> [a]
\\ [a]
ys
GT -> (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs) [a] -> [a] -> [a]
\\ [a]
ys
[] \\ _ = []
xs :: [a]
xs \\ [] = [a]
xs
symDiff :: [a] -> [a] -> [a]
symDiff (x :: a
x:xs :: [a]
xs) (y :: a
y:ys :: [a]
ys) =
case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
x a
y of
LT -> a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a] -> [a] -> [a]
symDiff [a]
xs (a
ya -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
ys)
EQ -> [a] -> [a] -> [a]
symDiff [a]
xs [a]
ys
GT -> a
y a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a] -> [a] -> [a]
symDiff (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs) [a]
ys
symDiff [] ys :: [a]
ys = [a]
ys
symDiff xs :: [a]
xs [] = [a]
xs
disjoint :: [a] -> [a] -> Bool
disjoint xs :: [a]
xs ys :: [a]
ys = [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null ([a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
intersect [a]
xs [a]
ys)
isSubset :: [a] -> [a] -> Bool
isSubset (x :: a
x:xs :: [a]
xs) (y :: a
y:ys :: [a]
ys) =
case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
x a
y of
LT -> Bool
False
EQ -> [a] -> [a] -> Bool
isSubset [a]
xs [a]
ys
GT -> [a] -> [a] -> Bool
isSubset (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs) [a]
ys
isSubset [] _ = Bool
True
isSubset _ [] = Bool
False