WeakSets 1.5.0.0 → 1.6.0.0

raw patch · 10 files changed

+109/−226 lines, 10 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• CHANGELOG.md +5/−1
• Readme.md +1/−13
• WeakSets.cabal +6/−8
• src/Data/Simplifiable.hs +79/−0
• src/Data/WeakMap.hs +10/−0
• src/Data/WeakMap/Safe.hs +2/−0
• src/Data/WeakSet.hs +6/−1
• src/Math/PureSet.hs +0/−184
• test/AllTests.hs +0/−2
• test/TestPureSet.hs +0/−17

@@ -74,4 +74,8 @@ 
 # 1.5.0.0 -- 2023-10-10
 
-* Better bounds+* Better bounds
+
+# 1.6.0.0 -- 2023-11-03
+
+* Removing PureSet as they are useless. MonadPlus and MonadFail for Set. Simplifiable typeclass to remove duplicates in Set and Map.

@@ -5,8 +5,7 @@ This package answers three problems :   * how to make sets of types which do not implement the Ord typeclass (which is required by Data.Set), this problem is solved by `Data.WeakSet`;-* how to make maps of types which do not implement the Ord typeclass, this problem is solved by `Data.WeakMap`;-* how to make arbitrarily nested sets as set theory allows. This problem is resolved thanks to `Math.PureSet`.+* how to make maps of types which do not implement the Ord typeclass, this problem is solved by `Data.WeakMap`.  Data.WeakSet and Data.WeakMap are (almost) backward compatible with Data.Set and Data.Map. Therefore you can replace your imports of Data.Set to Data.WeakSet and Data.Map.Strict to Data.WeakMap safely. There a a few functions which require to add an Eq typeclass as a requirement. Some functions are not implemented as they really need the Ord typeclass, if you use them you should use Data.Set or Data.Map. @@ -16,10 +15,8 @@  A `WeakMap` is an association list where duplicates entries and the order of pairs are disregarded. Its stronger counterpart is Data.Map. Most of the functions related to `WeakMap` require the Eq typeclass. -A `PureSet` is a tree-like structure where duplicate branches and the order of branches is disregarded.  - ## Installation  `cabal install WeakSets`@@ -53,15 +50,6 @@ 5 ``` -Example usage of pure sets :--```haskell-ghci> import PureSet-ghci> numberToSet 3-(pureSet [(pureSet []),(pureSet [(pureSet [])]),(pureSet [(pureSet []),(pureSet [(pureSet [])])])])-ghci> putStrLn.prettify $ numberToSet 3-{{}, {{}}, {{}, {{}}}}-```  ## Contribution 

@@ -14,14 +14,14 @@ -- PVP summary:      +-+------- breaking API changes
 --                   | | +----- non-breaking API additions
 --                   | | | +--- code changes with no API change
-version:             1.5.0.0
+version:             1.6.0.0
 
 -- A short (one-line) description of the package.
 synopsis:
     Simple set types. Useful to create sets of arbitrary types and nested sets.
 
 -- A longer description of the package.
-description: This package answers two problems : how to make sets and maps of types which do not implement the Ord typeclass and how to make arbitrarily nested sets as set theory allows. The first problem is resolved thanks to `WeakSet`s  and `WeakMap`s. The second problem is resolved thanks to `PureSet`.
+description: This package answers two problems : how to make sets and maps of types which do not implement the Ord typeclass and how to make arbitrarily nested sets as set theory allows. The problems are resolved thanks to `WeakSet`s and `WeakMap`s. A `WeakSet` is like a list where duplicates are considered the same when testing for equality. A `WeakMap` is a set of couples (key,value).
 
 
 -- URL for the project homepage or repository.
@@ -44,7 +44,7 @@ 
 -- A copyright notice.
 -- copyright:
-category:           Data, Math
+category:           Data
 
 -- Extra files to be distributed with the package, such as examples or a README.
 extra-source-files: 
@@ -55,11 +55,9 @@     -- Modules exported by the library.
     exposed-modules:    Data.WeakSet,
                         Data.WeakSet.Safe,
-                        Data.WeakMap
+                        Data.WeakMap,
                         Data.WeakMap.Safe,
-                        Math.PureSet
--- Math.PureSet,
--- Data.WeakMap
+                        Data.Simplifiable
 
     -- Modules included in this library but not exported.
     -- other-modules:
@@ -92,4 +90,4 @@     -- Test dependencies.
     build-depends:    base >=4 && < 5, WeakSets
     
-    other-modules:    TestWeakSet, TestPureSet, TestWeakMap
+    other-modules:    TestWeakSet, TestWeakMap

@@ -0,0 +1,79 @@+{-| Module  : WeakSets
+Description : A container may be simplified internally by the call of a function 'simplify'. This is the case for 'WeakSet's
+ and 'WeakMap's where duplicate elements remain in the container until the end of the lifetime of the container. Calling 'simplify' on them will remove duplicate elements.
+Copyright   : Guillaume Sabbagh 2022
+License     : LGPL-3.0-or-later
+Maintainer  : guillaumesabbagh@protonmail.com
+Stability   : experimental
+Portability : portable
+
+A container may be simplified internally by the call of a function 'simplify'. This is the case for 'WeakSet's
+ and 'WeakMap's where duplicate elements remain in the container until the end of the lifetime of the container. Calling 'simplify' on them will remove duplicate elements.
+
+-}
+
+module Data.Simplifiable
+(
+    Simplifiable(..),
+)
+where
+
+    import qualified        Data.WeakSet        as Set
+    import qualified        Data.WeakMap        as Map
+    import                  Data.WeakMap.Safe
+    import qualified        Data.List           as List
+    
+    import                  Numeric.Natural
+
+
+    -- | A container may be simplified internally by the call of a function 'simplify'. This is the case for 'WeakSet's
+    -- and 'WeakMap's where duplicate elements remain in the container until the end of the lifetime of the container. Calling --'simplify' on them will remove duplicate elements.
+    class Simplifiable a where
+        -- | A function to simplify a container recursively.
+        simplify :: a -> a
+        
+    instance Simplifiable Bool where
+        simplify = id
+
+    instance Simplifiable Char where
+        simplify = id
+
+    instance Simplifiable Int where
+        simplify = id
+
+    instance Simplifiable Natural where
+        simplify = id
+
+    instance Simplifiable Float where
+        simplify = id
+
+    instance Simplifiable Double where
+        simplify = id
+        
+    instance (Simplifiable a, Simplifiable b) => Simplifiable (a,b) where
+        simplify (a,b) = (simplify a, simplify b)
+        
+    instance (Simplifiable a, Simplifiable b, Simplifiable c) => Simplifiable (a,b,c) where
+        simplify (a,b,c) = (simplify a, simplify b, simplify c)
+        
+    instance (Simplifiable a, Simplifiable b, Simplifiable c, Simplifiable d) => Simplifiable (a,b,c,d) where
+        simplify (a,b,c,d) = (simplify a, simplify b, simplify c, simplify d)
+        
+    instance (Simplifiable a, Simplifiable b, Simplifiable c, Simplifiable d, Simplifiable e) => Simplifiable (a,b,c,d,e) where
+        simplify (a,b,c,d,e) = (simplify a, simplify b, simplify c, simplify d, simplify e)
+        
+    instance (Simplifiable a, Eq a) => Simplifiable (Set.Set a) where
+        simplify s = Set.set $ Set.setToList $ simplify <$> s
+        
+    instance (Simplifiable k, Simplifiable v, Eq k) => Simplifiable (Map.Map k v) where
+        simplify m = Map.weakMap $ Map.mapToList $ simplify <|$|> m
+
+    instance (Simplifiable a) => Simplifiable [a] where
+        simplify xs = simplify <$> xs
+        
+    instance (Simplifiable a) => Simplifiable (Maybe a) where
+        simplify x = simplify <$> x
+        
+    instance (Simplifiable a, Simplifiable b) => Simplifiable (Either a b) where
+        simplify (Left a) = Left $ simplify a
+        simplify (Right a) = Right $ simplify a

@@ -145,6 +145,8 @@     , mapKeys
     , mapKeysWith
     , mapKeysMonotonic
+    , mapKeysAndValues
+    , (<|$|>)
 
     -- * Folds
     , foldr
@@ -634,6 +636,14 @@ -- | Alias of `mapKeys` defined for backward compatibility.
 mapKeysMonotonic ::  (k1 -> k2) -> Map k1 a -> Map k2 a
 mapKeysMonotonic = mapKeys
+
+-- | Map a function to the couples (key,value).
+mapKeysAndValues :: ((k1,v1) -> (k2,v2)) -> Map k1 v1 -> Map k2 v2
+mapKeysAndValues f (Map s) = (Map $ f <$> s) 
+
+-- | Alias of 'mapKeysAndValues'.
+(<|$|>) :: ((k1,v1) -> (k2,v2)) -> Map k1 v1 -> Map k2 v2
+(<|$|>) = mapKeysAndValues
 
 -- | Eq typeclass must be added.
 --

@@ -25,6 +25,8 @@     , inverse
     , pseudoInverse
     , enumerateMaps
+    , mapKeysAndValues
+    , (<|$|>)
 )
 where
     import              Data.WeakMap

@@ -172,6 +172,7 @@ import  qualified   Data.Maybe      as      M
 import              Control.Applicative    (liftA2, Alternative, (<|>))
 import  qualified   Control.Applicative as  Applicative
+import  qualified   Control.Monad       as  Monad
 import  qualified   Data.Foldable as     Foldable
 
 -- | A weak set is a list of values such that the duplicate elements and the order of the elements are disregarded.
@@ -198,7 +199,12 @@ 
 instance Monad Set where
     (>>=) (Set xs) f = Set $ xs >>= (unsafeSetToList.f)
+    
+instance Monad.MonadFail Set where
+    fail _ = (set [])
 
+instance Monad.MonadPlus Set
+
 instance Alternative Set where
     (<|>) = (|||)
     empty = mempty
@@ -208,7 +214,6 @@ 
     
 -- Construction
-
 
 -- | Alias of mempty. Defined for backward compatibility with Data.Set.
 empty :: Set a

@@ -1,184 +0,0 @@-{-| 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 2022
-License     : GPL-3
-Maintainer  : guillaumesabbagh@protonmail.com
-Stability   : experimental
-Portability : portable
-
-Pure sets are nested sets which only contain other sets all the way down. They allow to explore basic set theory.
-
-Every mathematical object is a set, usual constructions such as Von Neumann numbers and Kuratowski pairs are implemented.
-
-It is a tree where the order of the branches does not matter.
-
-Functions with the same name as pure set functions are suffixed with the letter 'P' for pure to avoid name collision.
--}
-
-module Math.PureSet 
-(
-    -- * `PureSet` datatype
-    PureSet(..),
-    pureSet,
-    -- * Mathematical constructions using sets
-    emptySet,
-    singleton,
-    pair,
-    first,
-    second,
-    maybeFirst,
-    maybeSecond,
-    cartesianProduct,
-    numberToSet,
-    (||||),
-    (&&&&),
-    isInP,
-    isIncludedInP,
-    card,
-    powerSetP,
-    -- * Formatting functions
-    prettify,
-    formatPureSet,
-)
-where
-    import Data.WeakSet (Set)
-    import Data.WeakSet.Safe
-    import qualified Data.WeakSet as S
-    import Data.List    (intersect, nub, intercalate, subsequences)
-    import Data.Maybe   (fromJust, catMaybes)
-    
-    -- | A `PureSet` is a `Set` of other pure sets.
-    data PureSet = PureSet (Set PureSet) deriving (Eq, Show)
-    
-    -- | Construct a `PureSet` from a list of pure sets.
-    pureSet :: [PureSet] -> PureSet
-    pureSet = (PureSet).set
-    
-    -- | Peel a `PureSet` into a `Set`.
-    pureSetToSet :: PureSet -> Set PureSet
-    pureSetToSet (PureSet xs) = xs
-    
-    -- | Construct the empty set.
-    emptySet :: PureSet
-    emptySet = pureSet []
-  
-    -- | Construct the singleton containing a given set.
-    singleton :: PureSet -> PureSet
-    singleton x = pureSet $ [x]
-    
-    -- | 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]]
-    
-    -- | Return the first element of a pair according to Kuratowski's definition of a tuple.
-    first :: PureSet -> PureSet
-    first (PureSet s)
-        | length l == 2 = anElement f
-        | length l == 1 = if card (anElement s) == 1 then (anElement.pureSetToSet.anElement $ s) else  (error $ "Math.PureSet.first : malformed pair " ++ (show s))
-        | otherwise = error $ "Math.PureSet.first : malformed pair " ++ (show s)
-        where
-            l = setToList s
-            a = l !! 0
-            b = l !! 1
-            PureSet f = if card a == 1 then a else b
-            
-    -- | Return the second element of a pair according to Kuratowski's definition of a tuple.
-    second :: PureSet -> PureSet
-    second i@(PureSet s)
-        | length l == 1 = if card (anElement s) == 1 then (anElement.pureSetToSet.anElement $ s) else  (error $ "Math.PureSet.second : malformed pair " ++ (show s))
-        | length l == 2 = if r2 !! 0 == first i then r2 !! 1 else (if r2 !! 1 == first i then r2 !! 0 else (error $ "Math.PureSet.second : malformed pair " ++ (show s)))
-        | otherwise = error $ "Math.PureSet.second : malformed pair " ++ (show s)
-        where
-            l = setToList s
-            a = l !! 0
-            b = l !! 1
-            PureSet r = if card a == 2 then a else b
-            r2 = setToList r
-    
-    -- | Return the first element of a pair if possible.
-    maybeFirst :: PureSet -> Maybe PureSet
-    maybeFirst (PureSet s)
-        | length l == 2 = Just $ anElement f
-        | length l == 1 = if card (anElement s) == 1 then Just (anElement.pureSetToSet.anElement $ s) else Nothing
-        | otherwise = Nothing
-        where
-            l = setToList s
-            a = l !! 0
-            b = l !! 1
-            PureSet f = if card a == 1 then a else b
-    
-    -- | Return the second element of a pair if possible.
-    maybeSecond :: PureSet -> Maybe PureSet
-    maybeSecond i@(PureSet s)
-        | length l == 1 = if card (anElement s) == 1 then Just (anElement.pureSetToSet.anElement $ s) else Nothing
-        | length l == 2 = if length r2 /= 2 then Nothing else (if r2 !! 0 == first i then Just (r2 !! 1) else (if r2 !! 1 == first i then Just (r2 !! 0) else Nothing))
-        | otherwise = Nothing
-        where
-            l = setToList s
-            a = l !! 0
-            b = l !! 1
-            PureSet r = if card a == 2 then a else b
-            r2 = setToList r
-    
-    -- | 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]
-    
-    -- | Union of two pure sets.
-    (||||) :: PureSet -> PureSet -> PureSet
-    (||||) (PureSet xs) (PureSet ys) = PureSet $ xs ||| ys
-    
-    -- | Intersection of two pure sets.
-    (&&&&) :: PureSet -> PureSet -> PureSet
-    (&&&&) (PureSet xs) (PureSet ys) = PureSet $ xs |&| ys
-    
-    -- | Difference of two pure sets.
-    (\\\\) :: PureSet -> PureSet -> PureSet
-    (\\\\) (PureSet xs) (PureSet ys) = PureSet $ xs |-| ys
-   
-    -- | 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)))
-    
-    -- | Return wether a pure set is in another one.
-    isInP :: PureSet -> PureSet -> Bool
-    isInP x (PureSet xs) = x `isIn` xs
-    
-    -- | Return wether a pure set is included in another one.
-    isIncludedInP :: PureSet -> PureSet -> Bool
-    isIncludedInP (PureSet xs) (PureSet ys) = xs `isIncludedIn` ys
-    
-    -- | Return the size of a pure set.
-    card :: PureSet -> Int
-    card (PureSet xs) = cardinal xs
-    
-    -- | Return the set of subsets of a given set.
-    powerSetP :: PureSet -> PureSet
-    powerSetP (PureSet xs) = PureSet $ PureSet <$> S.powerSet xs
-    
-    -- | Prettify a pure set according to usual mathematical notation.
-    prettify :: PureSet -> String
-    prettify (PureSet xs)
-        | cardinal xs == 0 = "{}"
-        | otherwise = "{" ++ (intercalate ", " $ prettify <$> setToList xs) ++ "}"
-        
-    -- | Format pure sets such that if numbers are recognized, they are transformed into integer and if pairs are recognized, they are transformed into pairs.
-    formatPureSet :: PureSet -> String
-    formatPureSet x
-        | (not.null) $ toNumber x = show.fromJust $ toNumber x
-        | (not.null) $ toPair x = fromJust.toPair $ x
-        | otherwise = "{"++intercalate "," (formatPureSet <$> (setToList.pureSetToSet $ x))++"}"
-            where
-                toNumber s@(PureSet xs)
-                    | s == emptySet = Just 0
-                    | otherwise =   let
-                                        numbers = setToList $ toNumber <$> xs
-                                        anyMissing = null $ foldr1 (>>) numbers
-                                        maxNb = maximum $ catMaybes numbers
-                                    in 
-                                        if (not anyMissing) && (set (Just <$> [0..maxNb])) == (set numbers) then Just (maxNb + 1) else Nothing
-                toPair x
-                    | null (maybeSecond x) || null (maybeFirst x) = Nothing
-                    | otherwise = Just $ "(" ++ (formatPureSet.first $ x) ++ "," ++ (formatPureSet.second $ x) ++ ")"   
-    

@@ -1,12 +1,10 @@ module Main (main) where
     import qualified TestWeakSet                as WSET
     import qualified TestWeakMap                as WMAP
-    import qualified TestPureSet                as PSET
 
     main :: IO ()
     main = do
         putStrLn "Beginning of the test."
         WSET.main
         WMAP.main
-        PSET.main
         putStrLn "End of the tests."

@@ -1,17 +0,0 @@-module TestPureSet where
-    import Math.PureSet
-    import Data.List (intercalate)
-    
-    -- | Tests all functions related to pure sets.
-    main :: IO ()
-    main = do
-            putStrLn "Beginning of TestPureSet"
-            putStrLn.show $ emptySet
-            putStrLn.show $ singleton $ emptySet
-            putStrLn.show $ pair emptySet emptySet
-            putStrLn.show $ numberToSet <$> [0,3]
-            putStrLn $ intercalate "\n" $ formatPureSet <$> numberToSet <$> [0..3]
-            putStrLn.prettify $ pureSet [pureSet [pureSet []],pureSet [], pureSet [],pureSet [pureSet [],pureSet [pureSet [pureSet [pureSet [pureSet []]]]]]]
-            putStrLn.formatPureSet $ pureSet [pureSet [pureSet []],pureSet [], pureSet [],pureSet [pureSet [],pureSet [pureSet [pureSet [pureSet [pureSet []]]]]]]
-            putStrLn "End of TestPureSet"
-