module Math.Common.ListSet where

import Data.List (group,sort)
-- versions of Data.List functions which assume that the lists are ascending sets (no repeated elements)


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

-- Note that an ListSet.elem turned out to be slower than Data.List.elem

-- (Perhaps because it's slower when x `notElem` xs)