WeakSets 1.1.4.0 → 1.2.0.0

raw patch · 4 files changed

+97/−49 lines, 4 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• CHANGELOG.md +5/−1
• WeakSets.cabal +1/−1
• src/Data/WeakMap.hs +56/−40
• src/Data/WeakSet.hs +35/−7

@@ -26,4 +26,8 @@ 
 # 1.1.4.0 -- 2022-07-20
 
-* Major bug correction : instance Eq for Data.WeakMap+* Major bug correction : instance Eq for Data.WeakMap
+
+# 1.2.0.0 -- 2022-07-20
+
+* Major bug correction : instance Foldable removed for Data.WeakMap and Data.WeakSet

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

@@ -102,6 +102,7 @@ 
     -- ** Size
     , size
+    , null
 
     -- * Combine
 
@@ -146,6 +147,8 @@     , mapKeysMonotonic
 
     -- * Folds
+    , foldr
+    , foldl
     , foldrWithKey
     , foldlWithKey
     , foldMapWithKey
@@ -210,7 +213,7 @@     , inverse
     , pseudoInverse
 ) where
-import           Prelude  hiding      (lookup, map, filter, drop, take, splitAt)
+import           Prelude  hiding      (lookup, map, filter, drop, take, splitAt, foldr, foldl, null)
 import           Data.WeakSet         (Set)
 import qualified Data.WeakSet       as Set
 import           Data.WeakSet.Safe
@@ -240,9 +243,6 @@ 
 instance Monoid (Map k v) where
     mempty = Map (set [])
-    
-instance Foldable (Map k) where
-    foldr f d (Map al) = foldr (\(k,v) -> f v) d al
 
 instance Functor (Map k) where
     fmap f (Map al) = Map $ (\(k,v) -> (k,f v)) <$> al
@@ -333,7 +333,7 @@ -- This function is like `(!)` in Data.Map, it is renamed to avoid name collisions.
 (|!|) :: (Eq k) => Map k v -> k -> v
 (|!|) f key
-    | null safeResult = error "WeakMap.|!|: element not in the map"
+    | Foldable.null safeResult = error "WeakMap.|!|: element not in the map"
     | otherwise = result
     where
         safeResult = f |?| key
@@ -366,13 +366,17 @@ size :: (Eq k) => Map k a -> Int
 size m = length $ mapToList m
 
+-- | /O(1)/. Return wether the map is empty.
+null :: Map k a -> Bool
+null (Map al) = Set.null al
+
 -- | /O(n)/. Is the key a member of the map? See also `notMember`. 
 member :: (Eq k) => k -> Map k a -> Bool
-member k m = not.null $ m |?| k
+member k m = not.(Foldable.null) $ m |?| k
 
 -- | /O(n)/. Negation of `member`. 
 notMember :: (Eq k) => k -> Map k a -> Bool
-notMember k m = null $ m |?| k
+notMember k m = Foldable.null $ m |?| k
 
 -- | /O(n)/. Just like `(|?|)` but the order of argument is reversed. For backward compatibility with Data.Map.
 lookup :: (Eq k) => k -> Map k a -> Maybe a
@@ -383,7 +387,7 @@ -- This function is like `findWithDefault` (the order of the argument are reversed though).
 findWithDefault' :: (Eq k) => Map k v -> v -> k -> v
 findWithDefault' f d key
-    | null safeResult = d
+    | Foldable.null safeResult = d
     | otherwise = result
     where
         safeResult = f |?| key
@@ -404,7 +408,7 @@ -- | /O(n)/. Insert with a function, combining new value and old value. @insertWith f key value mp@ will insert the pair (key, value) into mp if key does not exist in the function. If the key does exist, the function will insert the pair (key, f new_value old_value). 
 insertWith :: (Eq k) => (v -> v -> v) -> k -> v -> Map k v -> Map k v
 insertWith comb k v f
-    | null prev = insert k v f
+    | Foldable.null prev = insert k v f
     | otherwise = insert k (comb v prev_value) f
     where
         prev = f |?| k
@@ -417,7 +421,7 @@ -- | /O(n)/. Insert with a function, combining key, new value and old value. @insertWithKey f key value mp@ will insert the pair (key, value) into mp if key does not exist in the function. If the key does exist, the function will insert the pair (key,f key new_value old_value). Note that the key passed to f is the same key passed to `insertWithKey`. 
 insertWithKey :: (Eq k) => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
 insertWithKey comb k v f
-    | null prev = insert k v f
+    | Foldable.null prev = insert k v f
     | otherwise = insert k (comb k v prev_value) f
     where
         prev = f |?| k
@@ -459,8 +463,8 @@ -- | /O(n)/. The expression (`alter` f k map) alters the value x at k, or absence thereof. alter can be used to insert, delete, or update a value in a `Map`. In short : `lookup` k (`alter` f k m) = f (`lookup` k m). 
 alter :: (Eq k) => (Maybe a -> Maybe a) -> k -> Map k a -> Map k a
 alter func key f
-    | null lookupKey = insert key unpackedImageNothing f
-    | null result = delete key f
+    | Foldable.null lookupKey = insert key unpackedImageNothing f
+    | Foldable.null result = delete key f
     | otherwise = insert key unpackedResult f
     where
         lookupKey = f |?| key
@@ -471,14 +475,14 @@ -- | /O(n)/. The expression (`alterF` f k map) alters the value x at k, or absence thereof. `alterF` can be used to inspect, insert, delete, or update a value in a Map.      
 alterF :: (Functor f, Eq k) => (Maybe a -> f (Maybe a)) -> k -> Map k a -> f (Map k a)
 alterF func key f
-    | null lookupKey = add <$> imageNothing
+    | Foldable.null lookupKey = add <$> imageNothing
     | otherwise = treat <$> result
     where
         lookupKey = f |?| key
         result = func lookupKey
-        treat x = if null x then delete key f else insert key (fromJust x) f
+        treat x = if Foldable.null x then delete key f else insert key (fromJust x) f
         imageNothing = func Nothing
-        add x = if null x then f else insert key (fromJust x) f
+        add x = if Foldable.null x then f else insert key (fromJust x) f
 
 
 -- | /O(n)/. The expression @(update f k map)@ updates the value x at k (if it is in the map). If (f x) is Nothing, the element is deleted. If it is (Just y), the key k is bound to the new value y. 
@@ -488,8 +492,8 @@ -- | /O(n)/. The expression @(updateWithKey f k map)@ updates the value x at k (if it is in the map). If (f k x) is Nothing, the element is deleted. If it is (Just y), the key k is bound to the new value y. 
 updateWithKey :: (Eq k) => (k -> a -> Maybe a) -> k -> Map k a -> Map k a
 updateWithKey f key m
-    | null look = m
-    | null res = delete key m
+    | Foldable.null look = m
+    | Foldable.null res = delete key m
     | otherwise = insert key r m
     where
         look = m |?| key
@@ -500,8 +504,8 @@ -- | /O(n)/. Lookup and update. See also `updateWithKey`. The function returns changed value, if it is updated. Returns the original key value if the map entry is deleted. 
 updateLookupWithKey :: (Eq k) => (k -> a -> Maybe a) -> k -> Map k a -> (Maybe a, Map k a)
 updateLookupWithKey f key m
-    | null look = (Nothing, m)
-    | null res = (Just v, delete key m)
+    | Foldable.null look = (Nothing, m)
+    | Foldable.null res = (Just v, delete key m)
     | otherwise = (Just v, insert key r m)
     where
         look = m |?| key
@@ -533,11 +537,11 @@ 
 -- | The union of a list of maps: @(unions == foldl union empty)@. 
 unions :: (Eq k) => [Map k a] -> Map k a
-unions = foldl union empty
+unions = L.foldl union empty
 
 -- | The union of a list of maps, with a combining operation: @(unionsWith f == foldl (unionWith f) empty)@. 
 unionsWith :: (Eq k) => (a -> a -> a) -> [Map k a] -> Map k a
-unionsWith f = foldl (unionWith f) empty
+unionsWith f = L.foldl (unionWith f) empty
 
 
 -- Difference
@@ -633,26 +637,38 @@ -- | Eq typeclass must be added.
 --
 -- It behaves much like a regular traverse except that the traversing function also has access to the key associated with a value and the values are forced before they are installed in the result map.
-traverseWithKey :: (Applicative t, Eq k) => (k -> a -> t b) -> Map k a -> t (Map k b) 
+traverseWithKey :: (Applicative t, Eq k, Eq a) => (k -> a -> t b) -> Map k a -> t (Map k b) 
 traverseWithKey f m = foldrWithKey (\k v ys -> liftA3 insert (pure k) (f k v) ys) (pure mempty) (fromList.mapToList $ m)
 
 -- | Eq typeclass must be added. Traverse keys/values and collect the Just results.
-traverseMaybeWithKey :: (Applicative f, Eq k) => (k -> a -> f (Maybe b)) -> Map k a -> f (Map k b) 
+traverseMaybeWithKey :: (Applicative f, Eq k, Eq a) => (k -> a -> f (Maybe b)) -> Map k a -> f (Map k b) 
 traverseMaybeWithKey f m = foldrWithKey (\k v ys -> liftA3 insertMaybe (pure k) (f k v) ys) (pure mempty) (fromList.mapToList $ m)
 
 -- Folds
 
+-- | /O(n^2)/. Fold the values in the map using the given right-associative binary operator.
+--
+-- Note that an Eq constraint must be added.
+foldr :: (Eq k) => (a -> b -> b) -> b -> Map k a -> b 
+foldr f d m = L.foldr (\(k,v) a -> f v a) d (mapToList m)
+
+-- | /O(n^2)/. Fold the values in the map using the given left-associative binary operator.
+--
+-- Note that an Eq constraint must be added.
+foldl :: (Eq k) => (a -> b -> a) -> a -> Map k b -> a 
+foldl f d m = L.foldl (\a (k,v) -> f a v) d (mapToList m)
+
 -- | `foldrWithKey` from the left.
-foldlWithKey :: (b -> k -> a -> b) -> b -> Map k a -> b
-foldlWithKey f d (Map al) = foldl (\b (k,v) -> f b k v) d al
+foldlWithKey :: (Eq k, Eq a) => (b -> k -> a -> b) -> b -> Map k a -> b
+foldlWithKey f d (Map al) = Set.foldl (\b (k,v) -> f b k v) d al
 
 -- | Fold with key.
-foldrWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b
-foldrWithKey f d (Map al) = foldr (\(k,v) -> f k v) d al
+foldrWithKey :: (Eq a, Eq k) =>(k -> a -> b -> b) -> b -> Map k a -> b
+foldrWithKey f d (Map al) = Set.foldr (\(k,v) -> f k v) d al
 
 -- |  Fold the keys and values in the map using the given monoid.
-foldMapWithKey :: Monoid m => (k -> a -> m) -> Map k a -> m
-foldMapWithKey f (Map al) = foldr (\(k,v) m -> (f k v) <> m) mempty al
+foldMapWithKey :: (Eq a, Eq k, Monoid m) => (k -> a -> m) -> Map k a -> m
+foldMapWithKey f (Map al) = Set.foldr (\(k,v) m -> (f k v) <> m) mempty al
 
 
 -- Strict folds
@@ -660,20 +676,20 @@ 
 
 -- | Strict foldr.
-foldr' :: (a -> b -> b) -> b -> Map k a -> b
-foldr' = Foldable.foldr'
+foldr' :: (Eq k) => (a -> b -> b) -> b -> Map k a -> b
+foldr' f d m = L.foldr (\(k,v) a -> f v a) d (mapToList m)
 
 -- | Strict foldl.
-foldl' :: (b -> a -> b) -> b -> Map k a -> b
-foldl' = Foldable.foldl'
+foldl' :: (Eq k) => (b -> a -> b) -> b -> Map k a -> b
+foldl' f d m = L.foldl' (\a (k,v) -> f a v) d (mapToList m)
 
 -- | Strict `foldrWithKey`.
 foldlWithKey' :: (b -> k -> a -> b) -> b -> Map k a -> b
-foldlWithKey' f d (Map al) = Foldable.foldl' (\b (k,v) -> f b k v) d al
+foldlWithKey' f d (Map al) = Set.foldl' (\b (k,v) -> f b k v) d al
 
 -- | Strict `foldrWithKey`.
 foldrWithKey' :: (k -> a -> b -> b) -> b -> Map k a -> b
-foldrWithKey' f d (Map al) = Foldable.foldr' (\(k,v) -> f k v) d al
+foldrWithKey' f d (Map al) = Set.foldr' (\(k,v) -> f k v) d al
 
 
 
@@ -802,7 +818,7 @@     where
         (ls,rs) = Set.mapEither customF al
         customF (k,v)
-            | null result = Left (k,l)
+            | Foldable.null result = Left (k,l)
             | otherwise = Right (k,r)
             where
                 result = f k v
@@ -820,7 +836,7 @@ 
 -- | /O(max(m^2,n^2))/. Returns True if the keys of the first map is included in the keys of the second and the predicate evaluation at their value is True.
 isSubmapOfBy :: Eq k => (a -> b -> Bool) -> Map k a -> Map k b -> Bool
-isSubmapOfBy p m1 m2 = (keys' m1) `isIncludedIn` (keys' m2) && (and $ test <$> keys' m1)
+isSubmapOfBy p m1 m2 = (keys' m1) `isIncludedIn` (keys' m2) && (Set.and $ test <$> keys' m1)
     where
         test k = p (m1 |!| k) (m2 |!| k)
 
@@ -830,7 +846,7 @@ 
 -- | /O(max(m^2,n^2))/. Returns True if the keys of the first map is strictly included in the keys of the second and the predicate evaluation at their value is True.
 isProperSubmapOfBy :: Eq k => (a -> b -> Bool) -> Map k a -> Map k b -> Bool
-isProperSubmapOfBy p m1 m2 = (keys' m1) `Set.isProperSubsetOf` (keys' m2) && (and $ test <$> keys' m1)
+isProperSubmapOfBy p m1 m2 = (keys' m1) `Set.isProperSubsetOf` (keys' m2) && (Set.and $ test <$> keys' m1)
     where
         test k = p (m1 |!| k) (m2 |!| k)
 
@@ -846,7 +862,7 @@ -- | /O(n^2)/. Return the index of a key, which is its zero-based index in the sequence. The index is a number from 0 up to, but not including, the size of the map. Calls error when the key is not a member of the map.
 findIndex :: Eq k => k -> Map k a -> Int
 findIndex k m
-    | null index = error "WeakSet.findIndex: element is not in the set"
+    | Foldable.null index = error "WeakSet.findIndex: element is not in the set"
     | otherwise = i
     where
         index = lookupIndex k m
@@ -864,7 +880,7 @@ updateListAt :: Int -> (a -> Maybe a) -> [a] -> [a]
 updateListAt _ _ [] = []
 updateListAt 0 f (x : xs)
-    | null result = xs
+    | Foldable.null result = xs
     | otherwise = r : xs
     where
         result = f x

@@ -78,6 +78,7 @@     , alterF
 
     -- -- * Query
+    , null
     , isIn
     , member
     , notMember
@@ -115,6 +116,11 @@     , mapMonotonic
 
     -- * Folds
+    , foldr
+    , foldl
+    , and
+    , or
+    
     -- ** Strict folds
     , foldr'
     , foldl'
@@ -141,7 +147,7 @@     , sequenceSet
     
 ) where
-import              Prelude         hiding (filter, splitAt, drop, take, map)
+import              Prelude         hiding (filter, splitAt, drop, take, map, foldr, foldl, null, and, or)
 import  qualified   Data.List       as      L
 import  qualified   Data.Maybe      as      M
 import              Control.Applicative    (liftA2)
@@ -152,8 +158,6 @@ -- 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 `fromList` or `set` which ensures the previous conditions.
 data Set a = Set [a]
 
-instance Foldable Set where
-    foldr f d (Set xs) = foldr f d xs
     
 instance (Eq a) => Eq (Set a) where
     x == y = x `isIncludedIn` y && y `isIncludedIn` x
@@ -257,6 +261,9 @@     
 -- Query
 
+-- | /O(1)/. Return wether the set is empty.
+null :: Set a -> Bool
+null (Set xs) = Foldable.null xs
 
 -- | /O(n)/. Return wether an element is in a set.
 isIn :: (Eq a) => a -> Set a -> Bool
@@ -352,7 +359,7 @@ -- | O(n^2). Return the index of an element, which is its zero-based index in the sorted sequence of elements. The index is a number from 0 up to, but not including, the size of the set. Calls error when the element is not a member of the set.
 findIndex :: (Eq a) => a -> Set a -> Int
 findIndex k x
-    | null index = error "WeakSet.findIndex: element is not in the set"
+    | Foldable.null index = error "WeakSet.findIndex: element is not in the set"
     | otherwise = i
     where
         index = lookupIndex k x
@@ -452,7 +459,7 @@ catEither :: Set (Either a b) -> (Set a, Set b)
 catEither (Set []) = (empty,empty)
 catEither (Set (x:xs))
-    | null x = (insert l ls, rs)
+    | Foldable.null x = (insert l ls, rs)
     | otherwise = (ls, insert r rs)
     where
         (ls,rs) = catEither (Set xs)
@@ -464,7 +471,7 @@ mapEither :: (a -> Either b c) -> Set a -> (Set b, Set c)
 mapEither _ (Set []) = (empty, empty)
 mapEither f (Set (x:xs))
-    | null result = (insert l ls, rs)
+    | Foldable.null result = (insert l ls, rs)
     | otherwise = (ls, insert r rs)
     where
         (ls,rs) = mapEither f (Set xs)
@@ -515,4 +522,25 @@ 
 -- | Set is not a Traversable because of the Eq typeclass requirement.
 sequenceSet :: (Applicative f, Eq (f a)) => Set (f a) -> f (Set a)
-sequenceSet (Set xs) = Set <$> sequenceA (L.nub xs)+sequenceSet (Set xs) = Set <$> sequenceA (L.nub xs)
+
+-- | /O(n^2)/. Fold the elements in the set using the given right-associative binary operator.
+--
+-- Note that an Eq constraint must be added.
+foldr :: (Eq a) => (a -> b -> b) -> b -> Set a -> b
+foldr f d s = Foldable.foldr f d (setToList s)
+
+-- | /O(n^2)/. Fold the elements in the set using the given right-associative binary operator.
+--
+-- Note that an Eq constraint must be added.
+foldl :: (Eq b) => (a -> b -> a) -> a -> Set b -> a
+foldl f d s = Foldable.foldl f d (setToList s)
+
+-- | Conjunction of a set of booleans.
+and :: Set Bool -> Bool
+and (Set xs) = Foldable.and xs
+
+
+-- | Disjunction of a set of booleans.
+or :: Set Bool -> Bool
+or (Set xs) = Foldable.or xs