--------------------------------------------------------------------------------
-- |
-- Module : Data.List.Set
-- Copyright : (C) Frank Staals
-- License : see the LICENSE file
-- Maintainer : Frank Staals
--------------------------------------------------------------------------------
module Data.List.Set( Set, singleton
, insert, delete
, union, intersection, difference
, fromList, insertAll
) where
import qualified Data.List as List
--------------------------------------------------------------------------------
-- | A Set of @a@\'s, implemented using a simple list. The only
-- advantage of this implementation over 'Data.Set' from containers is
-- that most operations require only @'Eq a'@ rather than @'Ord a'@.
newtype Set a = Set { toList :: [a] }
deriving (Show,Read,Functor,Foldable,Traversable)
instance Eq a => Eq (Set a) where
(Set xs) == (Set ys) = all (`elem` ys) xs && all (`elem` xs) ys
instance Eq a => Semigroup (Set a) where
(Set xs) <> s = insertAll xs s
instance Eq a => Monoid (Set a) where
mempty = Set []
-- | Creates a singleton set.
singleton :: a -> Set a
singleton x = Set [x]
-- | \(O(n)\) Inserts an element in the set
insert :: Eq a => a -> Set a -> Set a
insert x s@(Set xs) | x `elem` s = s
| otherwise = Set (x:xs)
-- | \( O(n^2) \) Insert an element in a set.
insertAll :: Eq a => [a] -> Set a -> Set a
insertAll xs s = List.foldl' (flip insert) s xs
-- | \( O(n^2) \) Create a set from a finite list of elements.
fromList :: Eq a => [a] -> Set a
fromList = flip insertAll mempty
-- | \(O(n)\) Deletes an element from the set
delete :: Eq a => a -> Set a -> Set a
delete x (Set xs) = Set $ go xs
where
go = \case
[] -> []
(y:ys) | x == y -> ys -- found the element, no need to continue looking
| otherwise -> y:go ys
-- | \(O(n^2)\) Computes the union of two sets
union :: Eq a => Set a -> Set a -> Set a
union = (<>)
-- | \(O(n^2)\) Computes the intersection of two sets
intersection :: Eq a => Set a -> Set a -> Set a
(Set xs) `intersection` (Set ys) = Set (xs `List.intersect` ys)
-- | \(O(n^2)\) Computes the difference of two sets
difference :: Eq a => Set a -> Set a -> Set a
(Set xs) `difference` (Set ys) = Set $ xs List.\\ ys