module SetEq
  ( Set (..),
    emptySet,
    isEmpty,
    inSet,
    subSet,
    insertSet,
    deleteSet,
    powerSet,
    takeSet,
    list2set,
    (!!!),
  )
where

import Data.List (delete)

{-- Sets implemented as unordered lists without duplicates --}

newtype Set a = Set [a]

instance (Eq a) => Eq (Set a) where
  set1 == set2 = subSet set1 set2 && subSet set2 set1

instance (Show a) => Show (Set a) where
  showsPrec _ (Set s) str = showSet s str

showSet [] str = showString "{}" str
showSet (x : xs) str = showChar '{' (shows x (showl xs str))
  where
    showl [] str = showChar '}' str
    showl (x : xs) str = showChar ',' (shows x (showl xs str))

emptySet :: Set a
emptySet = Set []

isEmpty :: Set a -> Bool
isEmpty (Set []) = True
isEmpty _ = False

inSet :: (Eq a) => a -> Set a -> Bool
inSet x (Set s) = elem x s

subSet :: (Eq a) => Set a -> Set a -> Bool
subSet (Set []) _ = True
subSet (Set (x : xs)) set = (inSet x set) && subSet (Set xs) set

insertSet :: (Eq a) => a -> Set a -> Set a
insertSet x (Set ys)
  | inSet x (Set ys) = Set ys
  | otherwise = Set (x : ys)

deleteSet :: (Eq a) => a -> Set a -> Set a
deleteSet x (Set xs) = Set (delete x xs)

list2set :: (Eq a) => [a] -> Set a
list2set [] = Set []
list2set (x : xs) = insertSet x (list2set xs)

powerSet :: (Eq a) => Set a -> Set (Set a)
powerSet (Set xs) = Set (map (\xs -> (Set xs)) (powerList xs))

powerList :: [a] -> [[a]]
powerList [] = [[]]
powerList (x : xs) = (powerList xs) ++ (map (x :) (powerList xs))

takeSet :: (Eq a) => Int -> Set a -> Set a
takeSet n (Set xs) = Set (take n xs)

infixl 9 !!!

(!!!) :: (Eq a) => Set a -> Int -> a
(Set xs) !!! n = xs !! n