{-| Module  : WeakSets
Description : Homogeneous sets are sets which can contain only one type of values. They are more flexible than Data.Set because they do not require the objects contained to be orderable.
Copyright   : Guillaume Sabbagh 2022
License     : LGPL-3.0-or-later
Maintainer  : guillaumesabbagh@protonmail.com
Stability   : experimental
Portability : portable

Homogeneous sets are sets which can contain only one type of values.

They are more flexible than Data.Set because they do not require the objects contained to be orderable.

The datatype only assumes its components are equatable, it is therefore slower than the Data.Set datatype.

We use this datatype because most of the datatypes we care about are not orderable.

Inline functions related to homogeneous sets are written between pipes @|@.

Function names should not collide with Prelude but may collide with Data.Set.
-}

module Data.WeakSets.HomogeneousSet
(
    -- * Set datatype and smart constructor
    Set, -- abstract type, the smart constructor is `set`
    set, -- the smart constructor for `Set`
    -- * Set related functions
    setToList,
    isIncludedIn,
    cardinal,
    isIn,
    (|&|),
    (|||),
    (|*|),
    (|+|),
    (|-|),
    (|^|),
    powerSet,
    filterSet,
    nubSetBy,
    -- * Functions to work with `Maybe`
    setToMaybe,
    maybeToSet,
    catMaybesToSet,
    mapMaybeToSet,
)
where
    import              Data.List               (intercalate, nub, nubBy, intersect, union, (\\), subsequences)
    import              Data.Maybe
    
    -- | A homogeneous set is a list of values.
    --
    -- The only differences are that we don't want duplicate elements and we don't need the order of the list elements.
    --
    -- To force these constraints, the `Set` constructor is abstract and is not exported. The only way to construct a set is to use the smart constructor `set` which ensures the previous conditions.
    data Set a = Set [a]
    
    -- | /O(1)/. The smart constructor of sets. This is the only way of instantiating a `Set`.
    --
    -- If several elements are equal, they are kept until the user wants a list back.
    set :: [a] -> Set a
    set xs = Set xs
    
    instance (Show a) => Show (Set a) where
        show (Set xs) = "(set "++show xs++")"
    
    -- | /O(n^2)/. Return a boolean indicating if a `Set` is included in another one.
    isIncludedIn :: (Eq a) => Set a -> Set a -> Bool
    (Set []) `isIncludedIn` _ = True
    (Set (x:xs)) `isIncludedIn` (Set ys)
        | x `elem` ys = (Set xs) `isIncludedIn` (Set ys)
        | otherwise = False
    
    instance (Eq a) => Eq (Set a) where
        x == y = x `isIncludedIn` y && y `isIncludedIn` x
        
    instance Semigroup (Set a) where
        (Set xs) <> (Set ys) = set $ xs <> ys
        
    instance Monoid (Set a) where
        mempty = Set []
    
    instance Foldable Set where
        foldr f d (Set xs) = foldr f d xs

    instance Functor Set where
        fmap f (Set xs) = Set $ f <$> xs
    
    instance Applicative Set where
        pure x = Set [x]
        (<*>) (Set fs) (Set xs) = Set $ fs <*> xs

    instance Monad Set where
        (>>=) (Set xs) f = Set $ xs >>= (unsafeSetToList.f)
    
    -- | /O(n)/. Transform a `Set` back into a list, the list returned does not have duplicate elements, the order of the original list holds.
    setToList :: (Eq a) => Set a -> [a]
    setToList (Set xs) = nub xs
    
    -- | /O(1)/. Gives the underlying list of a set without removing duplicates, this function is not exported.
    unsafeSetToList :: Set a -> [a]
    unsafeSetToList (Set xs) = xs
    
    -- | /O(n)/. Size of a set.
    cardinal :: (Eq a) => Set a -> Int
    cardinal = length.setToList
    
    -- | /O(n)/. Return wether an element is in a set.
    isIn :: (Eq a) => a -> Set a -> Bool
    isIn x = (elem x).unsafeSetToList
    
    -- | /O(n*m)/. Return the intersection of two sets.
    (|&|) :: (Eq a) => Set a -> Set a -> Set a
    (|&|) (Set xs) (Set ys) = Set $ xs `intersect` ys
    
    -- | /O(n)/. Return the union of two sets.
    (|||) ::  Set a -> Set a -> Set a
    (|||) (Set xs) (Set ys) = Set $ xs ++ ys
    
    -- | /O(n*m)/. Return the cartesian product of two sets.
    (|*|) ::  Set a -> Set b -> Set (a,b)
    (|*|) (Set xs) (Set ys) = Set $ [(x,y) | x <- xs, y <- ys]
    
    -- | /O(n)/. Return the disjoint union of two sets.
    (|+|) :: Set a -> Set b -> Set (Either a b)
    (|+|) (Set xs) (Set ys) = Set $ [Left x | x <- xs] ++ [Right y | y <- ys]
    
    -- | Returns the cartesian product of a set with itself n times.
    (|^|) :: (Num a, Eq a) => Set a -> a -> Set [a]
    (|^|) _ 0 = Set [[]]
    (|^|) s n = (:) <$> s <*> (s |^| (n-1))
    
    -- | /O(n*m)/. Return the difference of two sets.
    (|-|) :: (Eq a) => Set a -> Set a -> Set a
    (|-|) (Set xs) (Set ys) = Set $ xs \\ ys
    
    -- | Return the set of all subsets of a given set.
    powerSet :: Set a -> Set (Set a)
    powerSet (Set xs) = Set $ Set <$> subsequences xs
    
    -- | /O(n)/. Filter a set according to a condition.
    filterSet :: (a -> Bool) -> Set a -> Set a
    filterSet f (Set xs) = Set $ filter f xs
    
    -- | /O(1)/. Set version of listToMaybe.
    setToMaybe :: Set a -> Maybe a
    setToMaybe = listToMaybe.unsafeSetToList
    
    -- | /O(1)/. Set version of maybeToList.
    maybeToSet :: Maybe a -> Set a
    maybeToSet x = Set $ maybeToList x
    
    -- | /O(n)/. Set version of catMaybes.
    catMaybesToSet :: Set (Maybe a) -> Set a
    catMaybesToSet = set.catMaybes.unsafeSetToList
    
    -- | /O(n)/. Set version of mapMaybe.
    mapMaybeToSet :: (a -> Maybe b) -> Set a -> Set b
    mapMaybeToSet f = set.(mapMaybe f).unsafeSetToList

    -- | /O(n)/. Remove duplicates in the set using your own equality function.
    nubSetBy :: (a -> a -> Bool) -> Set a -> Set a
    nubSetBy f (Set xs) = Set $ nubBy f xs