    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)