-- Copyright (c) David Amos, 2008. All rights reserved.
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 xs = map head $ group $ sort xs
isListSet (x1:x2:xs) = x1 < x2 && isListSet (x2:xs)
isListSet _ = True
union (x:xs) (y:ys) =
case compare x y of
LT -> x : union xs (y:ys)
EQ -> x : union xs ys
GT -> y : union (x:xs) ys
union xs ys = xs ++ ys -- one of them is null
intersect (x:xs) (y:ys) =
case compare x y of
LT -> intersect xs (y:ys)
EQ -> x : intersect xs ys
GT -> intersect (x:xs) ys
intersect _ _ = []
(x:xs) \\ (y:ys) =
case compare x y of
LT -> x : (xs \\ (y:ys))
EQ -> xs \\ ys
GT -> (x:xs) \\ ys
[] \\ _ = []
xs \\ [] = xs
symDiff (x:xs) (y:ys) =
case compare x y of
LT -> x : symDiff xs (y:ys)
EQ -> symDiff xs ys
GT -> y : symDiff (x:xs) ys
symDiff xs ys = xs ++ ys -- one of them is null
disjoint xs ys = null (intersect xs ys)
isSubset (x:xs) (y:ys) =
case compare x y of
LT -> False
EQ -> isSubset xs ys
GT -> isSubset (x:xs) ys
isSubset [] _ = True
isSubset _ [] = False
-- Note that an ListSet.elem turned out to be slower than Data.List.elem
-- (Perhaps because it's slower when x `notElem` xs)