mini 1.4.1.0 → 1.4.2.0

raw patch · 5 files changed

+207/−39 lines, 5 filesdep ~basePVP ok

version bump matches the API change (PVP)

Dependency ranges changed: base

API changes (from Hackage documentation)

Files

• CHANGELOG.md +17/−0
• Mini/Data/Map.hs +101/−13
• Mini/Data/Set.hs +52/−13
• Mini/Transformers/ParserT.hs +11/−6
• mini.cabal +26/−7

@@ -1,3 +1,20 @@+1.4.2.0 [2024-12-07]+--------------------+* Mini.Data.Set:+  * Add 'lookup{GE,GT,LE,LT}' functions+* Mini.Data.Map:+  * Add 'lookup{GE,GT,LE,LT}' functions+  * Add 'insertWith', 'insertWithKey'+  * Add 'fromListWith', 'fromListWithKey'+* Mini.Transformers.ParserT:+  * Add combinators 'findFirst', 'findLast'+  * Fix '<|>' failure message propagation+* Documentation:+  * Fix time complexity+  * Add examples for 'insertWith', 'insertWithKey'+  * Add examples for 'fromListWith', 'fromListWithKey'+  * Update package description+ 1.4.1.0 [2024-11-01] -------------------- * Mini.Data.Set: Add Semigroup/Monoid instances

@@ -6,6 +6,8 @@   -- * Construction   empty,   fromList,+  fromListWith,+  fromListWithKey,   singleton,    -- * Combination@@ -27,11 +29,17 @@   filter,   filterWithKey,   insert,+  insertWith,+  insertWithKey,   update,    -- * Query   isSubmapOf,   lookup,+  lookupGE,+  lookupGT,+  lookupLE,+  lookupLT,   lookupMax,   lookupMin,   member,@@ -48,6 +56,9 @@   -- $examples ) where +import Control.Applicative (+  (<|>),+ ) import Control.Monad (   liftM2,  )@@ -189,6 +200,14 @@ fromList :: (Ord k) => [(k, a)] -> Map k a fromList = foldl (flip $ uncurry insert) empty +-- | /O(n log n)/ Make a map from a list of pairs, combining matching keys+fromListWith :: (Ord k) => (a -> a -> a) -> [(k, a)] -> Map k a+fromListWith = fromListWithKey . const++-- | /O(n log n)/ Make a map from a list of pairs, combining matching keys+fromListWithKey :: (Ord k) => (k -> a -> a -> a) -> [(k, a)] -> Map k a+fromListWithKey f = foldl (flip . uncurry $ insertWithKey f) empty+ -- | /O(1)/ Make a map with a single bin singleton :: k -> a -> Map k a singleton k a = B E k a E@@ -197,11 +216,11 @@  - Combination  -} --- | /O(n log n)/ Subtract a map by another via key matching+-- | /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(n log n)/ Intersect a map with another via left-biased key matching+-- | /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 =   foldrWithKey@@ -209,7 +228,7 @@     empty     t1 --- | /O(n log n)/ Unite a map with another via left-biased key matching+-- | /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 t = foldrWithKey (\k a b -> bool b (insert k a b) . not $ k `member` t) t @@ -750,11 +769,11 @@     (\(r, k', a') -> (checkRightB l k a r, k', a')) $       popRightL rl rk ra rr --- | /O(n)/ Keep the bins whose values satisfy a predicate+-- | /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 --- | /O(n)/ Keep the bins whose keys and values satisfy a predicate+-- | /O(n log n)/ Keep the bins whose keys and values satisfy a predicate filterWithKey :: (Ord k) => (k -> a -> Bool) -> Map k a -> Map k a filterWithKey p = foldrWithKey (\k a b -> bool b (insert k a b) $ p k a) empty @@ -947,6 +966,14 @@       (\lrl lrk lra lrr _ _ -> L (B ll lk la (insertR lrl lrk lra lrr)) k a r)       lr +-- | /O(log n)/ Insert a key and its value, combining new and old if present+insertWith :: (Ord k) => (a -> a -> a) -> k -> a -> Map k a -> Map k a+insertWith = insertWithKey . const++-- | /O(log n)/ Insert a key and its value, combining new and old if present+insertWithKey :: (Ord k) => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a+insertWithKey f k a t = bool (insert k a t) (adjust (f k a) k t) $ k `member` t+ -- | /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 =@@ -963,13 +990,13 @@  - Query  -} --- | /O(n log n)/ Check whether the bins of one map exist in the other+-- | /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 p q =+isSubmapOf t1 t2 =   foldrWithKey-    (\k a b -> maybe False ((&& b) . (== a)) $ lookup k q)+    (\k a b -> maybe False ((&& b) . (== a)) $ lookup k t2)     True-    p+    t1  -- | /O(log n)/ Fetch the value of a key in a map, or 'Nothing' if absent lookup :: (Ord k) => k -> Map k a -> Maybe a@@ -980,6 +1007,42 @@     EQ -> Just a     GT -> recr +-- | /O(log n)/ Fetch the least bin greater than or equal to a key+lookupGE :: (Ord k) => k -> Map k a -> Maybe (k, a)+lookupGE k0 = map Nothing go go go+ where+  go _ k a _ recl recr = case compare k k0 of+    LT -> recr+    EQ -> Just (k, a)+    GT -> recl <|> Just (k, a)++-- | /O(log n)/ Fetch the least bin strictly greater than a key+lookupGT :: (Ord k) => k -> Map k a -> Maybe (k, a)+lookupGT k0 = map Nothing go go go+ where+  go _ k a _ recl recr = case compare k k0 of+    LT -> recr+    EQ -> recr+    GT -> recl <|> Just (k, a)++-- | /O(log n)/ Fetch the greatest bin less than or equal to a key+lookupLE :: (Ord k) => k -> Map k a -> Maybe (k, a)+lookupLE k0 = map Nothing go go go+ where+  go _ k a _ recl recr = case compare k k0 of+    LT -> recr <|> Just (k, a)+    EQ -> Just (k, a)+    GT -> recl++-- | /O(log n)/ Fetch the greatest bin strictly less than a key+lookupLT :: (Ord k) => k -> Map k a -> Maybe (k, a)+lookupLT k0 = map Nothing go go go+ where+  go _ k a _ recl recr = case compare k k0 of+    LT -> recr <|> Just (k, a)+    EQ -> recl+    GT -> recl+ -- | /O(log n)/ Fetch the bin with the maximum key, or 'Nothing' if empty lookupMax :: Map k a -> Maybe (k, a) lookupMax = map Nothing go go go@@ -1011,9 +1074,7 @@  -- | /O(n)/ Get the size of a map size :: Map k a -> Int-size = map 0 go go go- where-  go _ _ _ _ recl recr = 1 + recl + recr+size = map 0 go go go where go _ _ _ _ recl recr = 1 + recl + recr  {-  - Traversal@@ -1057,11 +1118,23 @@  {- $examples 'fromList': /tail-biased/ means that if a list of @(key, value)@ pairs contains-pairs with identical keys, the one closest to the end of the list is kept.+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)} +'fromListWith', 'fromListWithKey': If a list of @(key, value)@ pairs contains+pairs with identical keys, the leftmost one is inserted as is and the subsequent+ones adjust the value with the combining function left-associatively. The+combining function takes the new value as the left operand, and the existing+value as the right operand.++>>> fromListWith (<>) [(1,"a"),(2,"b"),(1,"c"),(1,"d")]+{(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")}+ 'intersection', 'union': /left-biased/ means that if the operands contain bins with identical keys, the bins from the /left/ operand is kept. @@ -1069,6 +1142,21 @@ {('a',1),('b',2)} >>> fromList [('a',1),('b',2)] `union` fromList [('c',3),('b',4),('a',5)] {('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+with the combining function, which takes the given value as the left operand and+the existing value as the right operand.++>>> insertWith (<>) 1 "foo" $ fromList [(2,"bar"),(3,"baz")]+{(1,"foo"),(2,"bar"),(3,"baz")}+>>> insertWith (<>) 2 "foo" $ fromList [(2,"bar"),(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)}+>>> insertWithKey f 2 7 $ fromList [(2,3),(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

@@ -24,6 +24,10 @@    -- * Query   isSubsetOf,+  lookupGE,+  lookupGT,+  lookupLE,+  lookupLT,   lookupMax,   lookupMin,   member,@@ -34,6 +38,9 @@   valid, ) where +import Control.Applicative (+  (<|>),+ ) import Control.Monad (   liftM2,  )@@ -168,15 +175,15 @@  - Combination  -} --- | /O(n log n)/ Subtract a set by another+-- | /O(m log n)/ Subtract a set by another difference :: (Ord a) => Set a -> Set a -> Set a difference = foldr delete --- | /O(n log n)/ Intersect a set with another+-- | /O(m log n)/ Intersect a set with another intersection :: (Ord a) => Set a -> Set a -> Set a intersection t = foldr (\a b -> bool b (insert a b) (a `member` t)) empty --- | /O(n log n)/ Unite a set with another+-- | /O(m log n)/ Unite a set with another union :: (Ord a) => Set a -> Set a -> Set a union = foldr insert @@ -613,9 +620,9 @@   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(n)/ Keep the elements satisfying a predicate+-- | /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+filter p = foldr (\a b -> bool b (insert a b) $ p a) empty  -- | /O(log n)/ Insert an element into a set insert :: (Ord a) => a -> Set a -> Set a@@ -786,10 +793,46 @@  - Query  -} --- | /O(n log n)/ Check whether the elements of a set exist in the other+-- | /O(n log m)/ Check whether the elements of a set exist in the other isSubsetOf :: (Ord a) => Set a -> Set a -> Bool-isSubsetOf p q = foldr (\a b -> a `member` q && b) True p+isSubsetOf t1 t2 = foldr (\a b -> a `member` t2 && b) True t1 +-- | /O(log n)/ Fetch the least element greater than or equal to the given one+lookupGE :: (Ord a) => a -> Set a -> Maybe a+lookupGE a0 = set Nothing go go go+ where+  go _ a _ recl recr = case compare a a0 of+    LT -> recr+    EQ -> Just a+    GT -> recl <|> Just a++-- | /O(log n)/ Fetch the least element strictly greater than the given one+lookupGT :: (Ord a) => a -> Set a -> Maybe a+lookupGT a0 = set Nothing go go go+ where+  go _ a _ recl recr = case compare a a0 of+    LT -> recr+    EQ -> recr+    GT -> recl <|> Just a++-- | /O(log n)/ Fetch the greatest element less than or equal to the given one+lookupLE :: (Ord a) => a -> Set a -> Maybe a+lookupLE a0 = set Nothing go go go+ where+  go _ a _ recl recr = case compare a a0 of+    LT -> recr <|> Just a+    EQ -> Just a+    GT -> recl++-- | /O(log n)/ Fetch the greatest element strictly less than the given one+lookupLT :: (Ord a) => a -> Set a -> Maybe a+lookupLT a0 = set Nothing go go go+ where+  go _ a _ recl recr = case compare a a0 of+    LT -> recr <|> Just a+    EQ -> recl+    GT -> recl+ -- | /O(log n)/ Fetch the maximum element, or 'Nothing' if the set is empty lookupMax :: Set a -> Maybe a lookupMax = set Nothing go go go@@ -817,15 +860,11 @@  -- | /O(1)/ Check whether a set is empty null :: Set a -> Bool-null = set True go go go- where-  go _ _ _ _ _ = False+null = set True go go go where go _ _ _ _ _ = False  -- | /O(n)/ Get the size of a set size :: Set a -> Int-size = set 0 go go go- where-  go _ _ _ recl recr = 1 + recl + recr+size = set 0 go go go where go _ _ _ recl recr = 1 + recl + recr  {-  - Validation

@@ -35,6 +35,8 @@   option,   reject,   accept,+  findFirst,+  findLast, ) where  import Control.Applicative (@@ -121,12 +123,7 @@   m <|> n = ParserT $ \ss ->     runParserT m ss       >>= either-        ( \e1 ->-            either-              (const $ Left e1)-              Right-              <$> runParserT n ss-        )+        (const $ runParserT n ss)         (pure . Right)  instance (Monad m) => Monad (ParserT s m) where@@ -261,3 +258,11 @@     >>= either       (pure . Left)       (pure . Right . (,ss) . fst)++-- | Find and parse the first instance of @p@ via @findFirst p@+findFirst :: (Monad m, Eq s, Show s) => ParserT s m a -> ParserT s m a+findFirst p = p <|> (item *> findFirst p)++-- | Find and parse the last instance of @p@ via @findLast p@+findLast :: (Monad m, Eq s, Show s) => ParserT s m a -> ParserT s m a+findLast p = findFirst p >>= flip option (findLast p)

@@ -1,6 +1,6 @@-cabal-version:      2.4+cabal-version:      3.0 name:               mini-version:            1.4.1.0+version:            1.4.2.0 license:            MIT license-file:       LICENSE author:             Victor Wallsten <victor.wallsten@protonmail.com>@@ -9,11 +9,30 @@ bug-reports:        https://gitlab.com/vicwall/mini/issues synopsis:           Minimal essentials description:-  A minimal yet powerful library of essentials: data structures, lenses,-  transformers, and parsing. Uncompromisingly light on dependencies. Easily-  navigable code base, keeping indirection and clutter to a minimum.+  Everyday essentials: data structures, lenses, transformers, and parsing.++  Uncompromisingly light on dependencies.++  Easily navigable code base, keeping indirection and clutter to a minimum. category:           library-tested-with:        GHC == 9.4.8+tested-with:+  , GHC == 9.10.1+  , GHC == 9.8.4+  , GHC == 9.8.2+  , GHC == 9.8.1+  , GHC == 9.6.6+  , GHC == 9.6.5+  , GHC == 9.6.1+  , GHC == 9.4.8+  , GHC == 9.4.1+  , GHC == 9.2.8+  , GHC == 9.2.1+  , GHC == 9.0.2+  , GHC == 9.0.1+  , GHC == 8.10.7+  , GHC == 8.10.1+  , GHC == 8.8.4+  , GHC == 8.8.1 extra-doc-files:    CHANGELOG.md extra-source-files: .editorconfig                     .hlint.yaml@@ -36,7 +55,7 @@     Mini.Transformers.ParserT     Mini.Transformers.MaybeT   build-depends:-    base == 4.*+    base >= 4.13.0.0 && < 5   default-language:     Haskell2010   default-extensions: