WeakSets 0.1.0.0 → 0.2.0.0

raw patch · 4 files changed

+97/−60 lines, 4 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• WeakSets.cabal +1/−1
• src/HomogeneousSet.hs +78/−43
• src/PureSet.hs +15/−15
• test/TestHomogeneousSet.hs +3/−1

@@ -14,7 +14,7 @@ -- PVP summary:      +-+------- breaking API changes
 --                   | | +----- non-breaking API additions
 --                   | | | +--- code changes with no API change
-version:            0.1.0.0
+version:            0.2.0.0
 
 -- A short (one-line) description of the package.
 synopsis:

@@ -15,6 +15,8 @@ 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 should collide with Data.Set.
 -}
 
 module HomogeneousSet
@@ -27,13 +29,18 @@     isIncludedIn,
     cardinal,
     isIn,
-    (|<$>|),
     (|&|),
     (|||),
     (|*|),
     (|+|),
     (|-|),
+    (|^|),
     powerSet,
+    filterSet,
+    setToMaybe,
+    maybeToSet,
+    catMaybesToSet,
+    mapMaybeToSet,
     -- * Function datatype and smart constructor
     AssociationList(..),
     Function, -- abstract type, the smart constructor is `function`
@@ -49,7 +56,8 @@     memorizeFunction,
 )
 where
-    import Data.List (intercalate, nub, nubBy, intersect, union, (\\), subsequences)
+    import              Data.List               (intercalate, nub, nubBy, intersect, union, (\\), subsequences)
+    import              Data.Maybe
     
     -- | A homogeneous set is a list of values.
     --
@@ -60,14 +68,14 @@     
     -- | The smart constructor of sets. This is the only way of instantiating a `Set`.
     --
-    -- If several elements are equal, only the first element is kept.
-    set :: (Eq a) => [a] -> Set a
-    set xs = Set (nub xs)
+    -- 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++")"
     
-    -- | Returns a boolean indicating if a `Set` is included in another one.
+    -- | 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)
@@ -77,7 +85,6 @@     instance (Eq a) => Eq (Set a) where
         x == y = x `isIncludedIn` y && y `isIncludedIn` x
         
-
     instance (Eq a) => Semigroup (Set a) where
         (Set xs) <> (Set ys) = set $ xs <> ys
         
@@ -87,54 +94,81 @@     instance Foldable Set where
         foldr f d (Set xs) = foldr f d xs
 
-    -- | Transforms a `Set` back into a list, the list returned does not have duplicate elements, the order of the original list holds.
-    setToList :: Set a -> [a]
-    setToList (Set xs) = 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
 
-    -- | Maps a function to every element of the set. We can't instantiate `Functor` because we would have to add a contraint @Eq@ to the type parameter of `Set`.
-    (|<$>|) :: (Eq b) => (a -> b) -> Set a -> Set b
-    (|<$>|) f (Set xs) = set $ f <$> xs
+    instance Monad Set where
+        (>>=) (Set xs) f = Set $ xs >>= (unsafeSetToList.f)
     
-    -- | Unsafe map of a funtion to every element of a set. The function should be injective. This function is not exported.
-    unsafeMap :: (a -> b) -> Set a -> Set b
-    unsafeMap f (Set xs) = Set $ f <$> xs
+    -- | 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
     
+    -- | Gives the underlying list of a set without removing duplicates, this function is not exported.
+    unsafeSetToList :: Set a -> [a]
+    unsafeSetToList (Set xs) = xs
+    
     -- | Size of a set.
-    cardinal :: Set a -> Int
+    cardinal :: (Eq a) => Set a -> Int
     cardinal = length.setToList
     
-    -- | Returns wether an element is in a set.
+    -- | Return wether an element is in a set.
     isIn :: (Eq a) => a -> Set a -> Bool
-    isIn x = (elem x).setToList
+    isIn x = (elem x).unsafeSetToList
     
-    -- | Returns the intersection of two sets.
+    -- | Return the intersection of two sets.
     (|&|) :: (Eq a) => Set a -> Set a -> Set a
     (|&|) (Set xs) (Set ys) = Set $ xs `intersect` ys
     
-    -- | Returns the union of two sets.
-    (|||) ::  (Eq a) => Set a -> Set a -> Set a
-    (|||) (Set xs) (Set ys) = Set $ xs `union` ys
-    
-    -- | Unsafe union where we do not check duplicates. This function is not exported.
-    (|!) :: Set a -> Set a -> Set a
-    (|!) (Set xs) (Set ys) = Set $ xs ++ ys
+    -- | Return the union of two sets.
+    (|||) ::  Set a -> Set a -> Set a
+    (|||) (Set xs) (Set ys) = Set $ xs ++ ys
     
-    -- | Returns the cartesian product of two sets.
+    -- | 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]
     
-    -- | Returns the disjoint union of two sets.
+    -- | 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 difference of two sets.
+    -- | 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))
+    
+    -- | Return the difference of two sets.
     (|-|) :: (Eq a) => Set a -> Set a -> Set a
     (|-|) (Set xs) (Set ys) = Set $ xs \\ ys
     
-    -- | Returns the set of all subsets of a given set.
+    -- | Return the set of all subsets of a given set.
     powerSet :: Set a -> Set (Set a)
     powerSet (Set xs) = Set $ Set <$> subsequences xs
     
+    -- | Filter a set according to a condition.
+    filterSet :: (a -> Bool) -> Set a -> Set a
+    filterSet f (Set xs) = Set $ filter f xs
+    
+    -- | Set version of listToMaybe.
+    setToMaybe :: Set a -> Maybe a
+    setToMaybe = listToMaybe.unsafeSetToList
+    
+    -- | Set version of maybeToList.
+    maybeToSet :: Maybe a -> Set a
+    maybeToSet x = Set $ maybeToList x
+    
+    -- | Set version of catMaybes.
+    catMaybesToSet :: Set (Maybe a) -> Set a
+    catMaybesToSet = set.catMaybes.unsafeSetToList
+    
+    -- | Set version of mapMaybe.
+    mapMaybeToSet :: (a -> Maybe b) -> Set a -> Set b
+    mapMaybeToSet f = set.(mapMaybe f).unsafeSetToList
+    
     -- | A function of homogeneous sets. It is a set of pairs (key,value) such that their should only be one pair with a given key.
     --
     -- It is an abstract type, the smart constructor is `function`.
@@ -150,21 +184,21 @@     --
     -- Takes an association list and returns a function which maps to each key the value associated.
     --
-    -- If several pairs have the same keys, the first pair is kept.
-    function :: (Eq a) => AssociationList a b -> Function a b
-    function al = Function $ Set $ nubBy (\x y -> (fst x) == (fst y)) al
+    -- If several pairs have the same keys, they are kept until the user wants an association list back.
+    function :: AssociationList a b -> Function a b
+    function al = Function $ Set $ al
     
-    -- | Transforms a function back into its underlying association list.
-    functionToSet :: Function a b -> Set (a,b)
-    functionToSet (Function al) = al
+    -- | Transform a function back into its underlying association list.
+    functionToSet :: (Eq a) => Function a b -> Set (a,b)
+    functionToSet (Function (Set al)) = Set $ nubBy (\x y -> (fst x) == (fst y)) al
     
-    -- | Returns the domain of a function.
+    -- | Return the domain of a function.
     domain :: Function a b -> Set a
-    domain = (unsafeMap fst).functionToSet
+    domain (Function al) = fst <$> al
     
-    -- | Returns the image of a function. The image of a function is the set of values which are reachable by applying the function.
+    -- | Return the image of a function. The image of a function is the set of values which are reachable by applying the function.
     image :: Function a b -> Set b
-    image = (unsafeMap snd).functionToSet
+    image (Function al) = snd <$> al
         
     -- | Apply a function to a given value. If the function is not defined on the given value returns `Nothing`, otherwise returns `Just` the image.
     --
@@ -193,10 +227,11 @@         | x == k = v
         | otherwise = findWithDefault (Function (Set xs)) d x
    
-    -- | Composes two functions. If the two functions are not composable, strips the functions until they can compose.
+    -- | Compose two functions. If the two functions are not composable, strips the functions until they can compose.
     (|.|) :: (Eq a, Eq b) => Function b c -> Function a b -> Function a c
     (|.|) f2 f1 = Function $ Set [(k,(f2 |!| (f1 |!| k))) | k <- (setToList.domain $ f1), f1 |!| k `isIn` (domain f2)]
     
     -- | Memorize a Haskell function on a given finite domain.
     memorizeFunction :: (a -> b) -> Set a -> Function a b
-    memorizeFunction f (Set xs) = Function $ Set [(k, f k) | k <- xs]+    memorizeFunction f (Set xs) = Function $ Set [(k, f k) | k <- xs]
+    

@@ -1,6 +1,6 @@ {-| Module  : WeakSets
 Description : Pure sets are nested sets which only contain other sets all the way down. They allow to explore basic set theory.
-Copyright   : Guillaume Sabbagh 2021
+Copyright   : Guillaume Sabbagh 2022
 License     : GPL-3
 Maintainer  : guillaumesabbagh@protonmail.com
 Stability   : experimental
@@ -47,27 +47,27 @@     instance Show PureSet where
         show (PureSet xs) = "(pureSet "++ show (setToList xs) ++")"
     
-    -- | Constructs a `PureSet` from a list of pure sets.
+    -- | Construct a `PureSet` from a list of pure sets.
     pureSet :: [PureSet] -> PureSet
     pureSet = (PureSet).set
     
-    -- | Peels a `PureSet` into a `Set`.
+    -- | Peel a `PureSet` into a `Set`.
     pureSetToSet :: PureSet -> Set PureSet
     pureSetToSet (PureSet xs) = xs
     
-    -- | Constructs the empty set.
+    -- | Construct the empty set.
     emptySet :: PureSet
     emptySet = pureSet []
   
-    -- | Constructs the singleton containing a given set.
+    -- | Construct the singleton containing a given set.
     singleton :: PureSet -> PureSet
     singleton x = pureSet $ [x]
     
-    -- | Constructs an ordered pair from two sets according to Kuratowski's definition of a tuple.
+    -- | Construct an ordered pair from two sets according to Kuratowski's definition of a tuple.
     pair :: PureSet -> PureSet -> PureSet
     pair x y = PureSet $ set [singleton x, pureSet $ [x,y]]
     
-    -- | Constructs the cartesian product of two sets.
+    -- | Construct the cartesian product of two sets.
     cartesianProduct :: PureSet -> PureSet -> PureSet
     cartesianProduct (PureSet xs) (PureSet ys) = pureSet $ [pair x y | x <- setToList xs, y <- setToList ys]
     
@@ -83,28 +83,28 @@     (\\\\) :: PureSet -> PureSet -> PureSet
     (\\\\) (PureSet xs) (PureSet ys) = PureSet $ xs |-| ys
    
-    -- | Transforms a number into its Von Neumann construction
+    -- | Transform a number into its Von Neumann construction
     numberToSet :: (Num a, Eq a) => a -> PureSet
     numberToSet 0 = emptySet
     numberToSet n = (numberToSet (n-1)) |||| (singleton (numberToSet (n-1)))
     
-    -- | Returns wether a pure set is in another one.
+    -- | Return wether a pure set is in another one.
     isInP :: PureSet -> PureSet -> Bool
     isInP x (PureSet xs) = x `isIn` xs
     
-    -- | Returns wether a pure set is included in another one.
+    -- | Return wether a pure set is included in another one.
     isIncludedInP :: PureSet -> PureSet -> Bool
     isIncludedInP (PureSet xs) (PureSet ys) = xs `isIncludedIn` ys
     
-    -- | Returns the size of a pure set.
+    -- | Return the size of a pure set.
     card :: PureSet -> Int
     card (PureSet xs) = cardinal xs
     
-    -- | Returns the set of subsets of a given set.
+    -- | Return the set of subsets of a given set.
     powerSetP :: PureSet -> PureSet
-    powerSetP (PureSet xs) = PureSet $ PureSet |<$>| powerSet xs
+    powerSetP (PureSet xs) = PureSet $ PureSet <$> powerSet xs
     
-    -- | Prettiffies a pure set according to usual mathematical notation.
+    -- | Prettiffy a pure set according to usual mathematical notation.
     prettify :: PureSet -> String
     prettify (PureSet xs)
         | cardinal xs == 0 = "{}"
@@ -120,7 +120,7 @@                 toNumber s@(PureSet xs)
                     | s == emptySet = Just 0
                     | otherwise =   let
-                                        numbers = setToList $ toNumber |<$>| xs
+                                        numbers = setToList $ toNumber <$> xs
                                         anyMissing = null $ foldr1 (>>) numbers
                                         maxNb = maximum $ catMaybes numbers
                                     in 

@@ -13,12 +13,14 @@             putStrLn $ show $ (set [1,2]) `isIncludedIn` s1
             putStrLn $ show $ cardinal s1
             putStrLn $ show $ 3 `isIn` s1
-            putStrLn $ show $ (+1) |<$>| s1
+            putStrLn $ show $ (+1) <$> s1
+            putStrLn $ show $ (+) <$> s1 <*> s2
             putStrLn $ show $ s1 |&| s2
             putStrLn $ show $ s1 ||| s2
             putStrLn $ show $ s1 |*| s2
             putStrLn $ show $ s1 |+| s2
             putStrLn $ show $ s1 |-| s2
+            putStrLn $ show $ s1 |^| 3
             putStrLn $ show $ powerSet s1
             let f = function $ zip (setToList s1) (setToList s2)
             let g = function $ zip (setToList s2) (setToList s1)