mini 1.5.0.0 → 1.5.1.0

raw patch · 4 files changed

+335/−29 lines, 4 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• CHANGELOG.md +28/−0
• Mini/Data/Map.hs +244/−26
• Mini/Data/Set.hs +62/−2
• mini.cabal +1/−1

@@ -1,3 +1,31 @@+1.5.1.0 [2024-12-26]+--------------------+* Add to Mini.Data.Set:+  * 'unions'+  * 'deleteMax', 'deleteMin'+  * 'partition'+  * 'split', 'splitMax', 'splitMin'+  * 'disjoint'+* Add to Mini.Data.Map:+  * 'compose'+  * 'differenceWith', 'differenceWithKey'+  * 'intersectionWith', 'intersectionWithKey'+  * 'unionWith', 'unionWithKey'+  * 'unions', 'unionsWith', 'unionsWithKey'+  * 'adjustWithKey'+  * 'adjustMax', 'adjustMaxWithKey'+  * 'adjustMin', 'adjustMinWithKey'+  * 'deleteMax', 'deleteMin'+  * 'updateWithKey'+  * 'updateMax', 'updateMaxWithKey'+  * 'updateMin', 'updateMinWithKey'+  * 'disjoint'+  * 'isSubmapOfBy'+  * 'fmapWithKey'+  * 'partition', 'partitionWithKey'+  * 'split', 'splitMax', 'splitMin'+* Update Mini.Data.Map examples+ 1.5.0.0 [2024-12-23] -------------------- * Mini.Data.{Map,Set}:

@@ -11,9 +11,19 @@   singleton,    -- * Combination+  compose,   difference,+  differenceWith,+  differenceWithKey,   intersection,+  intersectionWith,+  intersectionWithKey,   union,+  unionWith,+  unionWithKey,+  unions,+  unionsWith,+  unionsWithKey,    -- * Conversion   toAscList,@@ -25,16 +35,37 @@    -- * Modification   adjust,+  adjustWithKey,+  adjustMax,+  adjustMaxWithKey,+  adjustMin,+  adjustMinWithKey,   delete,+  deleteMax,+  deleteMin,   filter,   filterWithKey,   insert,   insertWith,   insertWithKey,   update,+  updateWithKey,+  updateMax,+  updateMaxWithKey,+  updateMin,+  updateMinWithKey, +  -- * Partition+  partition,+  partitionWithKey,+  split,+  splitMax,+  splitMin,+   -- * Query+  disjoint,   isSubmapOf,+  isSubmapOfBy,   lookup,   lookupGE,   lookupGT,@@ -47,6 +78,7 @@   size,    -- * Traversal+  fmapWithKey,   traverseWithKey,    -- * Validation@@ -94,9 +126,11 @@   fmap,   foldl,   foldr,+  fst,   max,   maybe,   mempty,+  not,   pure,   show,   traverse,@@ -112,6 +146,7 @@   (<>),   (==),   (>),+  (||),  )  {-@@ -139,9 +174,7 @@   show = show . toAscList  instance Functor (Map k) where-  fmap f = map E (go L) (go B) (go R)-   where-    go c _ k a _ recl = c recl k (f a)+  fmap = fmapWithKey . const  instance Foldable (Map k) where   foldr = foldrWithKey . const@@ -205,10 +238,40 @@  - Combination  -} +-- | /O(n log m)/ Compose the keys of one set with the values of another+compose :: (Ord b, Ord a) => Map b c -> Map a b -> Map a c+compose bc =+  foldrWithKey+    (\a b ac -> maybe ac (\c -> insert a c ac) $ lookup b bc)+    empty+ -- | /O(m log n)/ Subtract a map by another via key matching difference :: (Ord k) => Map k a -> Map k b -> Map k a difference = foldrWithKey (\k _ b -> delete k b) +-- | /O(m log n)/ Subtract a map by another, updating bins of matching keys+differenceWith+  :: (Ord k) => (a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a+differenceWith = differenceWithKey . const++-- | /O(m log n)/ Subtract a map by another, updating bins of matching keys+differenceWithKey+  :: (Ord k) => (k -> a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a+differenceWithKey f t =+  foldrWithKey+    ( \k b t' ->+        maybe+          t'+          ( \a ->+              maybe+                (delete k t')+                (\a' -> insert k a' t')+                $ f k a b+          )+          $ lookup k t+    )+    t+ -- | /O(n log m)/ Intersect a map with another via left-biased key matching intersection :: (Ord k) => Map k a -> Map k b -> Map k a intersection t1 t2 =@@ -217,10 +280,43 @@     empty     t1 +-- | /O(n log m)/ Intersect a map with another by key matching, combining values+intersectionWith :: (Ord k) => (a -> b -> c) -> Map k a -> Map k b -> Map k c+intersectionWith = intersectionWithKey . const++-- | /O(n log m)/ Intersect a map with another by key matching, combining values+intersectionWithKey+  :: (Ord k) => (k -> a -> b -> c) -> Map k a -> Map k b -> Map k c+intersectionWithKey f t1 t2 =+  foldrWithKey+    (\k a c -> maybe c (\b -> insert k (f k a b) c) $ lookup k t2)+    empty+    t1+ -- | /O(m log n)/ Unite a map with another via left-biased key matching union :: (Ord k) => Map k a -> Map k a -> Map k a union = flip $ foldrWithKey insert +-- | /O(m log n)/ Unite a map with another, combining values of matching keys+unionWith :: (Ord k) => (a -> a -> a) -> Map k a -> Map k a -> Map k a+unionWith = unionWithKey . const++-- | /O(m log n)/ Unite a map with another, combining values of matching keys+unionWithKey :: (Ord k) => (k -> a -> a -> a) -> Map k a -> Map k a -> Map k a+unionWithKey f = flip $ foldrWithKey (insertWithKey f)++-- | Unite a collection of maps via left-biased key matching+unions :: (Foldable t, Ord k) => t (Map k a) -> Map k a+unions = foldr union empty++-- | Unite a collection of maps, combining values of matching keys+unionsWith :: (Foldable t, Ord k) => (a -> a -> a) -> t (Map k a) -> Map k a+unionsWith = unionsWithKey . const++-- | Unite a collection of maps, combining values of matching keys+unionsWithKey :: (Foldable t, Ord k) => (k -> a -> a -> a) -> t (Map k a) -> Map k a+unionsWithKey f = foldr (unionWithKey f) empty+ {-  - Conversion  -}@@ -255,13 +351,41 @@  -- | /O(log n)/ Adjust with an operation the value of a key in a map adjust :: (Ord k) => (a -> a) -> k -> Map k a -> Map k a-adjust f k0 = map E (go L) (go B) (go R)+adjust = adjustWithKey . const++-- | /O(log n)/ Adjust with an operation the value of a key in a map+adjustWithKey :: (Ord k) => (k -> a -> a) -> k -> Map k a -> Map k a+adjustWithKey f k0 = map E (go L) (go B) (go R)  where   go c l k a r recl recr = case compare k0 k of     LT -> c recl k a r-    EQ -> c l k (f a) r+    EQ -> c l k (f k a) r     GT -> c l k a recr +-- | /O(log n)/ Adjust with an operation the value of the maximum key in a map+adjustMax :: (a -> a) -> Map k a -> Map k a+adjustMax = adjustMaxWithKey . const++-- | /O(log n)/ Adjust with an operation the value of the maximum key in a map+adjustMaxWithKey :: (k -> a -> a) -> Map k a -> Map k a+adjustMaxWithKey f = map E (go L) (go B) (go R)+ where+  go c l k a r _ recr = map (c l k (f k a) r) go' go' go' r+   where+    go' _ _ _ _ _ _ = c l k a recr++-- | /O(log n)/ Adjust with an operation the value of the minimum key in a map+adjustMin :: (a -> a) -> Map k a -> Map k a+adjustMin = adjustMinWithKey . const++-- | /O(log n)/ Adjust with an operation the value of the minimum key in a map+adjustMinWithKey :: (k -> a -> a) -> Map k a -> Map k a+adjustMinWithKey f = map E (go L) (go B) (go R)+ where+  go c l k a r recl _ = map (c l k (f k a) r) go' go' go' l+   where+    go' _ _ _ _ _ _ = c recl k a r+ -- | /O(log n)/ Delete a key from a map delete :: (Ord k) => k -> Map k a -> Map k a delete k0 t = bool t (go t) (k0 `member` t)@@ -758,6 +882,14 @@     (\(r, k', a') -> (checkRightB l k a r, k', a')) $       popRightL rl rk ra rr +-- | /O(log n)/ Delete the maximum key from a map+deleteMax :: (Ord k) => Map k a -> Map k a+deleteMax t = maybe t (flip delete t . fst) $ lookupMax t++-- | /O(log n)/ Delete the minimum key from a map+deleteMin :: (Ord k) => Map k a -> Map k a+deleteMin t = maybe t (flip delete t . fst) $ lookupMin t+ -- | /O(n log n)/ Keep the bins whose values satisfy a predicate filter :: (Ord k) => (a -> Bool) -> Map k a -> Map k a filter p = foldrWithKey (\k a b -> bool b (insert k a b) $ p a) empty@@ -965,25 +1097,105 @@  -- | /O(log n)/ Modify the value of a key or delete its bin with an operation update :: (Ord k) => (a -> Maybe a) -> k -> Map k a -> Map k a-update f k t =+update = updateWithKey . const++-- | /O(log n)/ Modify the value of a key or delete its bin with an operation+updateWithKey :: (Ord k) => (k -> a -> Maybe a) -> k -> Map k a -> Map k a+updateWithKey f k t =   maybe     t     ( maybe         (delete k t)-        (\a -> insert k a t)-        . f+        (\a' -> insert k a' t)+        . f k     )     $ lookup k t +-- | /O(log n)/ Modify the value of the maximum key or delete its bin+updateMax :: (Ord k) => (a -> Maybe a) -> Map k a -> Map k a+updateMax = updateMaxWithKey . const++-- | /O(log n)/ Modify the value of the maximum key or delete its bin+updateMaxWithKey :: (Ord k) => (k -> a -> Maybe a) -> Map k a -> Map k a+updateMaxWithKey f t =+  maybe+    t+    ( \(k, a) ->+        maybe+          (delete k t)+          (\a' -> insert k a' t)+          $ f k a+    )+    $ lookupMax t++-- | /O(log n)/ Modify the value of the minimum key or delete its bin+updateMin :: (Ord k) => (a -> Maybe a) -> Map k a -> Map k a+updateMin = updateMinWithKey . const++-- | /O(log n)/ Modify the value of the minimum key or delete its bin+updateMinWithKey :: (Ord k) => (k -> a -> Maybe a) -> Map k a -> Map k a+updateMinWithKey f t =+  maybe+    t+    ( \(k, a) ->+        maybe+          (delete k t)+          (\a' -> insert k a' t)+          $ f k a+    )+    $ lookupMin t+ {-+ - Partition+ -}++-- | /O(n log n)/ Partition a map with a predicate into @(true, false)@ submaps+partition :: (Ord k) => (a -> Bool) -> Map k a -> (Map k a, Map k a)+partition = partitionWithKey . const++-- | /O(n log n)/ Partition a map with a predicate into @(true, false)@ submaps+partitionWithKey :: (Ord k) => (k -> a -> Bool) -> Map k a -> (Map k a, Map k a)+partitionWithKey p =+  foldrWithKey+    (\k a (t1, t2) -> bool (t1, insert k a t2) (insert k a t1, t2) $ p k a)+    (empty, empty)++-- | /O(n log n)/ Split a map by a key into @(lt, eq, gt)@ submaps+split :: (Ord k) => k -> Map k a -> (Map k a, Maybe a, Map k a)+split k0 =+  foldrWithKey+    ( \k a (t1, a', t2) -> case compare k k0 of+        LT -> (insert k a t1, a', t2)+        EQ -> (t1, Just a, t2)+        GT -> (t1, a', insert k a t2)+    )+    (empty, Nothing, empty)++-- | /O(log n)/ Split a map by its maximum key+splitMax :: (Ord k) => Map k a -> Maybe ((k, a), Map k a)+splitMax t = (\ka -> (ka, deleteMax t)) <$> lookupMax t++-- | /O(log n)/ Split a map by its minimum key+splitMin :: (Ord k) => Map k a -> Maybe ((k, a), Map k a)+splitMin t = (\ka -> (ka, deleteMin t)) <$> lookupMin t++{-  - Query  -} +-- | /O(m log n)/ Check whether two maps have no keys in common+disjoint :: (Ord k) => Map k a -> Map k a -> Bool+disjoint t1 = not . foldrWithKey (\k _ b -> k `member` t1 || b) False+ -- | /O(n log m)/ Check whether the bins of one map exist in the other isSubmapOf :: (Ord k, Eq a) => Map k a -> Map k a -> Bool-isSubmapOf t1 t2 =+isSubmapOf = isSubmapOfBy (==)++-- | /O(n log m)/ Check if the bins of one map exist in the other by combination+isSubmapOfBy :: (Ord k) => (a -> b -> Bool) -> Map k a -> Map k b -> Bool+isSubmapOfBy p t1 t2 =   foldrWithKey-    (\k a b -> maybe False ((&& b) . (== a)) $ lookup k t2)+    (\k a b -> maybe False ((&& b) . p a) $ lookup k t2)     True     t1 @@ -1050,9 +1262,9 @@  -- | /O(log n)/ Check whether a key is in a map member :: (Ord k) => k -> Map k a -> Bool-member k = map False go go go+member k0 = map False go go go  where-  go _ k' _ _ recl recr = case compare k k' of+  go _ k _ _ recl recr = case compare k0 k of     LT -> recl     EQ -> True     GT -> recr@@ -1069,6 +1281,12 @@  - Traversal  -} +-- | /O(n)/ Apply an operation across a map, transforming its values+fmapWithKey :: (k -> a -> b) -> Map k a -> Map k b+fmapWithKey f = map E (go L) (go B) (go R)+ where+  go c _ k a _ recl = c recl k (f k a)+ -- | /O(n)/ Lift a map with a lifting operation on keys and values traverseWithKey :: (Applicative f) => (k -> a -> f b) -> Map k a -> f (Map k b) traverseWithKey f = map (pure E) (go L) (go B) (go R)@@ -1110,7 +1328,7 @@ pairs with identical keys, the rightmost one is kept.  >>> fromList [('a',1),('b',2),('c',3),('b',4),('a',5)]-{('a',5),('b',4),('c',3)}+[('a',5),('b',4),('c',3)]  'fromListWith', 'fromListWithKey': If a list of @(key, value)@ pairs contains pairs with identical keys, the leftmost one is inserted as is and the subsequent@@ -1119,18 +1337,18 @@ value as the right operand.  >>> fromListWith (<>) [(1,"a"),(2,"b"),(1,"c"),(1,"d")]-{(1,"dca"),(2,"b")}+[(1,"dca"),(2,"b")] >>> let f k new old = old <> ", " <> show k <> new >>> fromListWithKey f [(1,"a"),(2,"b"),(1,"c"),(1,"d")]-{(1,"a, 1c, 1d"),(2,"b")}+[(1,"a, 1c, 1d"),(2,"b")] -'intersection', 'union': /left-biased/ means that if the operands contain bins-with identical keys, the bins from the /left/ operand is kept.+'intersection', 'union', 'unions': /left-biased/ means that if the operands+contain bins with identical keys, the bins from the /left/ operand is kept.  >>> fromList [('a',1),('b',2)] `intersection` fromList [('c',3),('b',4),('a',5)]-{('a',1),('b',2)}+[('a',1),('b',2)] >>> fromList [('a',1),('b',2)] `union` fromList [('c',3),('b',4),('a',5)]-{('a',1),('b',2),('c',3)}+[('a',1),('b',2),('c',3)]  'insertWith', 'insertWithKey': If the key does not exist in the map, it is inserted with the given value as is. Otherwise, the existing value is adjusted@@ -1138,14 +1356,14 @@ the existing value as the right operand.  >>> insertWith (<>) 1 "foo" $ fromList [(2,"bar"),(3,"baz")]-{(1,"foo"),(2,"bar"),(3,"baz")}+[(1,"foo"),(2,"bar"),(3,"baz")] >>> insertWith (<>) 2 "foo" $ fromList [(2,"bar"),(3,"baz")]-{(2,"foobar"),(3,"baz")}+[(2,"foobar"),(3,"baz")] >>> let f k new old = k + new - old >>> insertWithKey f 1 2 $ fromList [(2,3),(3,5)]-{(1,2),(2,3),(3,5)}+[(1,2),(2,3),(3,5)] >>> insertWithKey f 2 7 $ fromList [(2,3),(3,5)]-{(2,6),(3,5)}+[(2,6),(3,5)]  'update': If the key does not exist, the map is unchanged. If the key exists and the result of the operation is @Just x@, the value of the corresponding bin is@@ -1154,9 +1372,9 @@  >>> f a = if a == 2 then Just 9 else Nothing >>> update f 'c' $ fromList [('a',1),('b',2)]-{('a',1),('b',2)}+[('a',1),('b',2)] >>> update f 'b' $ fromList [('a',1),('b',2)]-{('a',1),('b',9)}+[('a',1),('b',9)] >>> update f 'a' $ fromList [('a',1),('b',2)]-{('b',2)}+[('b',2)] -}

@@ -12,6 +12,7 @@   difference,   intersection,   union,+  unions,    -- * Conversion   toAscList,@@ -19,10 +20,19 @@    -- * Modification   delete,+  deleteMax,+  deleteMin,   filter,   insert, +  -- * Partition+  partition,+  split,+  splitMax,+  splitMin,+   -- * Query+  disjoint,   isSubsetOf,   lookupGE,   lookupGT,@@ -69,13 +79,16 @@   ),   Semigroup,   Show,+  any,   compare,   error,   flip,   foldl,   foldr,   max,+  maybe,   mempty,+  not,   show,   uncurry,   ($),@@ -84,6 +97,7 @@   (-),   (.),   (<),+  (<$>),   (<>),   (==),   (>),@@ -182,6 +196,10 @@ union :: (Ord a) => Set a -> Set a -> Set a union = flip $ foldr insert +-- | Unite a collection of sets+unions :: (Foldable t, Ord a) => t (Set a) -> Set a+unions = foldr union empty+ {-  - Conversion  -}@@ -615,6 +633,14 @@   popRightBR l a rl ra rr = first (checkRightB l a) $ popRightR rl ra rr   popRightBL l a rl ra rr = first (checkRightB l a) $ popRightL rl ra rr +-- | /O(log n)/ Delete the maximum element from a set+deleteMax :: (Ord a) => Set a -> Set a+deleteMax t = maybe t (flip delete t) $ lookupMax t++-- | /O(log n)/ Delete the minimum element from a set+deleteMin :: (Ord a) => Set a -> Set a+deleteMin t = maybe t (flip delete t) $ lookupMin t+ -- | /O(n log n)/ Keep the elements satisfying a predicate filter :: (Ord a) => (a -> Bool) -> Set a -> Set a filter p = foldr (\a b -> bool b (insert a b) $ p a) empty@@ -785,9 +811,43 @@       lr  {-+ - Partition+ -}++-- | /O(n log n)/ Partition a set with a predicate into @(true, false)@ subsets+partition :: (Ord a) => (a -> Bool) -> Set a -> (Set a, Set a)+partition p =+  foldr+    (\a (t1, t2) -> bool (t1, insert a t2) (insert a t1, t2) $ p a)+    (empty, empty)++-- | /O(n log n)/ Split a set by an element into @(lt, eq, gt)@ subsets+split :: (Ord a) => a -> Set a -> (Set a, Bool, Set a)+split a0 =+  foldr+    ( \a (t1, a', t2) -> case compare a a0 of+        LT -> (insert a t1, a', t2)+        EQ -> (t1, True, t2)+        GT -> (t1, a', insert a t2)+    )+    (empty, False, empty)++-- | /O(log n)/ Split a set by its maximum element+splitMax :: (Ord a) => Set a -> Maybe (a, Set a)+splitMax t = (\a -> (a, deleteMax t)) <$> lookupMax t++-- | /O(log n)/ Split a set by its minimum element+splitMin :: (Ord a) => Set a -> Maybe (a, Set a)+splitMin t = (\a -> (a, deleteMin t)) <$> lookupMin t++{-  - Query  -} +-- | /O(m log n)/ Check whether two sets have no elements in common+disjoint :: (Ord a) => Set a -> Set a -> Bool+disjoint t1 = not . any (`member` t1)+ -- | /O(n log m)/ Check whether the elements of a set exist in the other isSubsetOf :: (Ord a) => Set a -> Set a -> Bool isSubsetOf t1 t2 = foldr (\a b -> a `member` t2 && b) True t1@@ -846,9 +906,9 @@  -- | /O(log n)/ Check whether an element is in a set member :: (Ord a) => a -> Set a -> Bool-member a = set False go go go+member a0 = set False go go go  where-  go _ a' _ recl recr = case compare a a' of+  go _ a _ recl recr = case compare a0 a of     LT -> recl     EQ -> True     GT -> recr

@@ -1,6 +1,6 @@ cabal-version:      3.0 name:               mini-version:            1.5.0.0+version:            1.5.1.0 license:            MIT license-file:       LICENSE author:             Victor Wallsten <victor.wallsten@protonmail.com>