mini 1.3.0.0 → 1.3.0.1

raw patch · 4 files changed

+150/−237 lines, 4 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

CHANGELOG.md +4/−0
Mini/Data/Map.hs +78/−146
Mini/Data/Set.hs +67/−90
mini.cabal +1/−1

CHANGELOG.md view

@@ -1,3 +1,7 @@+1.3.0.1 [2024-04-14]+--------------------+* Streamline data documentation+ 1.3.0.0 [2024-03-28] -------------------- * Mini.Transformers.ParserT:

Mini/Data/Map.hs view

@@ -1,20 +1,18 @@-{- | Representation of a structure mapping unique keys to values. The internal-structure is an AVL tree.--}+-- | A structure mapping unique keys to values module Mini.Data.Map (   -- * Type   Map, -  -- * Combination-  difference,-  intersection,-  union,-   -- * Construction   empty,   fromList,   singleton, +  -- * Combination+  difference,+  intersection,+  union,+   -- * Conversion   toAscList,   toDescList,@@ -64,12 +62,7 @@  - Type  -} -{- | A map from keys of type /k/ to values of type /a/.--The internal structure is an AVL tree; a tree that is always height-balanced-(the absolute value of the level difference between the left and right-subtrees is at most 1).--}+-- | A map from keys /k/ to values /a/, internally structured as an AVL tree data Map k a   = -- | Empty bin     E@@ -93,15 +86,12 @@       (c : cs) -> c : removeTrailingComma cs  instance Functor (Map k) where-  fmap f =-    map-      E-      (\_ k a _ recl recr -> L recl k (f a) recr)-      (\_ k a _ recl recr -> B recl k (f a) recr)-      (\_ k a _ recl recr -> R recl k (f a) recr)+  fmap f = map E (go L) (go B) (go R)+   where+    go c _ k a _ recl recr = c recl k (f a) recr  instance Foldable (Map k) where-  foldr f b = map b go go go where go _ _ a r recl _ = foldr f (f a recl) r+  foldr = foldrWithKey . const  instance Traversable (Map k) where   traverse = traverseWithKey . const@@ -121,14 +111,11 @@   :: b   -- ^ Empty bin   -> (Map k a -> k -> a -> Map k a -> b -> b -> b)-  -- ^ Left-heavy bin: left child, key, value, right child, left recursion,-  -- right recursion+  -- ^ Left-heavy bin   -> (Map k a -> k -> a -> Map k a -> b -> b -> b)-  -- ^ Balanced bin: left child, key, value, right child, left recursion, right-  -- recursion+  -- ^ Balanced bin   -> (Map k a -> k -> a -> Map k a -> b -> b -> b)-  -- ^ Right-heavy bin: left child, key, value, right child, left recursion,-  -- right recursion+  -- ^ Right-heavy bin   -> Map k a   -- ^ Map   -> b@@ -138,14 +125,30 @@ map e f g h (R l k a r) = h l k a r (map e f g h l) (map e f g h r)  {-+ - Construction+ -}++-- | /O(1)/ The empty map+empty :: Map k a+empty = E++-- | /O(n log n)/ Make a map from a tail-biased list of @(key, value)@ pairs+fromList :: (Ord k) => [(k, a)] -> Map k a+fromList = foldl (flip $ uncurry insert) empty++-- | /O(1)/ Make a map with a single bin+singleton :: k -> a -> Map k a+singleton k a = B E k a E++{-  - Combination  -} --- | \(O(n \log n)\) Map difference (matching only on keys)+-- | /O(n 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)\) Left-biased map intersection (matching only on keys)+-- | /O(n log n)/ 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@@ -153,41 +156,19 @@     empty     t1 --- | \(O(n \log n)\) Left-biased map union (matching only on keys)+-- | /O(n 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  {-- - Construction- -}---- | \(O(1)\) The empty map-empty :: Map k a-empty = E--{- | \(O(n \log n)\) From a tail-biased list of @(key, value)@ pairs to a map-with bins containing the keys and values--}-fromList :: (Ord k) => [(k, a)] -> Map k a-fromList = foldl (flip $ uncurry insert) empty---- | \(O(1)\) From a key and a value to a map with a single bin-singleton :: k -> a -> Map k a-singleton k a = B E k a E--{-  - Conversion  -} -{- | \(O(n)\) From a map to a list of @(key, value)@ pairs in key-ascending-order--}+-- | /O(n)/ Turn a map into a list of @(key, value)@ pairs in ascending order toAscList :: Map k a -> [(k, a)] toAscList = foldlWithKey (\b k a -> (k, a) : b) [] -{- | \(O(n)\) From a map to a list of @(key, value)@ pairs in key-descending-order--}+-- | /O(n)/ Turn a map into a list of @(key, value)@ pairs in descending order toDescList :: Map k a -> [(k, a)] toDescList = foldrWithKey (\k a b -> (k, a) : b) [] @@ -195,17 +176,13 @@  - Fold  -} -{- | \(O(n)\) From a left-associative operation on keys and values, a starting-accumulator and a map to a thing--}+-- | /O(n)/ Reduce a map with a left-associative operation and an accumulator foldlWithKey :: (b -> k -> a -> b) -> b -> Map k a -> b foldlWithKey f b = map b go go go  where   go l k a _ _ recr = foldlWithKey f (f recr k a) l -{- | \(O(n)\) From a right-associative operation on keys and values, a starting-accumulator and a map to a thing--}+-- | /O(n)/ Reduce a map with a right-associative operation and an accumulator foldrWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b foldrWithKey f b = map b go go go  where@@ -215,33 +192,16 @@  - Modification  -} -{- | \(O(\log n)\) From an operation, a key and a map to the map adjusted by-applying the operation to the value associated with the key--}+-- | /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-    ( \l k a r recl recr ->-        case compare k0 k of-          LT -> L recl k a r-          EQ -> L l k (f a) r-          GT -> L l k a recr-    )-    ( \l k a r recl recr ->-        case compare k0 k of-          LT -> B recl k a r-          EQ -> B l k (f a) r-          GT -> B l k a recr-    )-    ( \l k a r recl recr ->-        case compare k0 k of-          LT -> R recl k a r-          EQ -> R l k (f a) r-          GT -> R l k a recr-    )+adjust 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+    GT -> c l k a recr --- | \(O(\log n)\) From a key and a map to the map without the key+-- | /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)  where@@ -737,21 +697,15 @@     (\(r, k', a') -> (checkRightB l k a r, k', a')) $       popRightL rl rk ra rr -{- | \(O(n)\) From a predicate and a map to the map with values satisfying the-predicate--}+-- | /O(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)\) From a predicate and a map to the map with keys and values-satisfying the predicate--}+-- | /O(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 -{- | \(O(\log n)\) From a key, a value and a map to the map including a bin-containing the key and the value--}+-- | /O(log n)/ Insert a key and its value into a map, overwriting if present insert :: (Ord k) => k -> a -> Map k a -> Map k a insert k0 a0 =   map@@ -940,10 +894,7 @@       (\lrl lrk lra lrr _ _ -> L (B ll lk la (insertR lrl lrk lra lrr)) k a r)       lr -{- | \(O(\log n)\) From an operation, a key and a map to the map updated by-applying the operation to the value associated with the key (setting if-'Just', deleting if 'Nothing')--}+-- | /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 =   maybe@@ -959,9 +910,7 @@  - Query  -} -{- | \(O(n \log n)\) From a map and another map to whether the former is a-submap of the latter (matching on keys and values)--}+-- | /O(n log n)/ 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 =   foldrWithKey@@ -969,9 +918,7 @@     True     p -{- | \(O(\log n)\) From a key and a map to the value associated with the key in-the map--}+-- | /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 lookup k = map Nothing go go go  where@@ -980,23 +927,23 @@     EQ -> Just a     GT -> recr -{- | \(O(\log n)\) From a map to the value associated with the maximum key in-the map--}+-- | /O(log n)/ Fetch the maximum value, or 'Nothing' if the map is empty lookupMax :: Map k a -> Maybe a lookupMax = map Nothing go go go  where-  go _ _ a r _ recr = map (Just a) go' go' go' r where go' _ _ _ _ _ _ = recr+  go _ _ a r _ recr = map (Just a) go' go' go' r+   where+    go' _ _ _ _ _ _ = recr -{- | \(O(\log n)\) From a map to the value associated with the minimum key in-the map--}+-- | /O(log n)/ Fetch the minimum value, or 'Nothing' if the map is empty lookupMin :: Map k a -> Maybe a lookupMin = map Nothing go go go  where-  go l _ a _ recl _ = map (Just a) go' go' go' l where go' _ _ _ _ _ _ = recl+  go l _ a _ recl _ = map (Just a) go' go' go' l+   where+    go' _ _ _ _ _ _ = recl --- | \(O(\log n)\) From a key and a map to whether the key is in the map+-- | /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  where@@ -1005,41 +952,31 @@     EQ -> True     GT -> recr --- | \(O(1)\) From a map to whether the map is empty+-- | /O(1)/ Check whether a map is empty null :: Map k a -> Bool null = map True go go go where go _ _ _ _ _ _ = False --- | \(O(n)\) From a map to the size of the map+-- | /O(n)/ Get the size of a map size :: Map k a -> Int-size =-  map-    0-    (\_ _ _ _ recl recr -> 1 + recl + recr)-    (\_ _ _ _ recl recr -> 1 + recl + recr)-    (\_ _ _ _ recl recr -> 1 + recl + recr)+size = map 0 go go go+ where+  go _ _ _ _ recl recr = 1 + recl + recr  {-  - Traversal  -} -{- | \(O(n)\) From a lifting operation on keys and values and a map to a lifted-map--}+-- | /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)-    (\_ k a _ recl recr -> L <$> recl <*> pure k <*> f k a <*> recr)-    (\_ k a _ recl recr -> B <$> recl <*> pure k <*> f k a <*> recr)-    (\_ k a _ recl recr -> R <$> recl <*> pure k <*> f k a <*> recr)+traverseWithKey f = map (pure E) (go L) (go B) (go R)+ where+  go c _ k a _ recl recr = c <$> recl <*> pure k <*> f k a <*> recr  {-  - Validation  -} -{- | \(O(n)\) From a map to whether its internal structure is valid, i.e.-height-balanced and ordered--}+-- | /O(n)/ Check whether a map is internally height-balanced and ordered valid :: (Ord k) => Map k a -> Bool valid = liftM2 (&&) balanced ordered  where@@ -1049,19 +986,14 @@       (\l _ _ r recl recr -> levels l - levels r == 1 && recl && recr)       (\l _ _ r recl recr -> levels l - levels r == 0 && recl && recr)       (\l _ _ r recl recr -> levels r - levels l == 1 && recl && recr)-  levels = map 0 go go go where go _ _ _ _ recl recr = 1 + max recl recr :: Int+  levels = map 0 go go go+   where+    go _ _ _ _ recl recr = 1 + max recl recr :: Int   ordered = map True go go go    where     go l k _ r recl recr =-      map-        True-        (\_ lk _ _ _ _ -> lk < k && recl && recr)-        (\_ lk _ _ _ _ -> lk < k && recl && recr)-        (\_ lk _ _ _ _ -> lk < k && recl && recr)-        l-        && map-          True-          (\_ rk _ _ _ _ -> rk > k && recl && recr)-          (\_ rk _ _ _ _ -> rk > k && recl && recr)-          (\_ rk _ _ _ _ -> rk > k && recl && recr)-          r+      map True lt lt lt l+        && map True gt gt gt r+     where+      lt _ lk _ _ _ _ = lk < k && recl && recr+      gt _ rk _ _ _ _ = rk > k && recl && recr

Mini/Data/Set.hs view

@@ -1,22 +1,18 @@-{-# LANGUAGE LambdaCase #-}--{- | Representation of a structure containing unique elements. The internal-structure is an AVL tree.--}+-- | A structure containing unique elements module Mini.Data.Set (   -- * Type   Set, -  -- * Combination-  difference,-  intersection,-  union,-   -- * Construction   empty,   fromList,   singleton, +  -- * Combination+  difference,+  intersection,+  union,+   -- * Conversion   toAscList,   toDescList,@@ -56,12 +52,7 @@  - Type  -} -{- | A set containing elements of type /a/.--The internal structure is an AVL tree; a tree that is always height-balanced-(the absolute value of the level difference between the left and right-subtrees is at most 1).--}+-- | A set containing elements of type /a/, internally structured as an AVL tree data Set a   = -- | Empty node     E@@ -79,13 +70,14 @@     go _ a _ recl recr = recl <> show a <> "," <> recr     curl = wrap "{" "}" . removeTrailingComma     wrap open close s = open <> s <> close-    removeTrailingComma = \case-      [] -> []-      [_] -> []-      (c : cs) -> c : removeTrailingComma cs+    removeTrailingComma [] = []+    removeTrailingComma "," = []+    removeTrailingComma (c : cs) = c : removeTrailingComma cs  instance Foldable Set where-  foldr f b = set b go go go where go _ a r recl _ = foldr f (f a recl) r+  foldr f b = set b go go go+   where+    go _ a r recl _ = foldr f (f a recl) r  {-  - Primitive recursion@@ -96,14 +88,11 @@   :: b   -- ^ Empty node   -> (Set a -> a -> Set a -> b -> b -> b)-  -- ^ Left-heavy node: left child, element, right child, left recursion, right-  -- recursion+  -- ^ Left-heavy node   -> (Set a -> a -> Set a -> b -> b -> b)-  -- ^ Balanced node: left child, element, right child, left recursion, right-  -- recursion+  -- ^ Balanced node   -> (Set a -> a -> Set a -> b -> b -> b)-  -- ^ Right-heavy node: left child, element, right child, left recursion, right-  -- recursion+  -- ^ Right-heavy node   -> Set a   -- ^ Set   -> b@@ -113,48 +102,46 @@ set e f g h (R l a r) = h l a r (set e f g h l) (set e f g h r)  {-- - Combination- -}---- | \(O(n \log n)\) Set difference-difference :: (Ord a) => Set a -> Set a -> Set a-difference = foldr delete---- | \(O(n \log n)\) Set intersection-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)\) Set union-union :: (Ord a) => Set a -> Set a -> Set a-union = foldr insert--{-  - Construction  -} --- | \(O(1)\) The empty set+-- | /O(1)/ The empty set empty :: Set a empty = E -{- | \(O(n \log n)\) From a tail-biased list of elements to a set containing the-elements--}+-- | /O(n log n)/ Make a set from a tail-biased list of values fromList :: (Ord a) => [a] -> Set a fromList = foldl (flip insert) empty --- | \(O(1)\) From an element to a set with a single element+-- | /O(1)/ Make a set with a single value singleton :: a -> Set a singleton a = B E a E  {-+ - Combination+ -}++-- | /O(n 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 via left-biased matching+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 via left-biased matching+union :: (Ord a) => Set a -> Set a -> Set a+union = foldr insert++{-  - Conversion  -} --- | \(O(n)\) From a set to a list of elements in ascending order+-- | /O(n)/ Turn a set into a list of values in ascending order toAscList :: Set a -> [a] toAscList = foldl (flip (:)) [] --- | \(O(n)\) From a set to a list of elements in descending order+-- | /O(n)/ Turn a set into a list of values in descending order toDescList :: Set a -> [a] toDescList = foldr (:) [] @@ -162,7 +149,7 @@  - Modification  -} --- | \(O(\log n)\) From an element and a set to the set without the element+-- | /O(log n)/ Delete a value from a set delete :: (Ord a) => a -> Set a -> Set a delete a0 t = bool t (go t) (a0 `member` t)  where@@ -579,13 +566,11 @@   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)\) From a predicate and a set to the set with elements satisfying the-predicate--}+-- | /O(n)/ Keep the values 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 --- | \(O(\log n)\) From an element and a set to the set including the element+-- | /O(log n)/ Insert a value into a set, overwriting if present insert :: (Ord a) => a -> Set a -> Set a insert a0 =   set@@ -754,27 +739,27 @@  - Query  -} -{- | \(O(n \log n)\) From a set and another set to whether the former is a-subset of the latter--}+-- | /O(n log n)/ Check whether the values 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 --- | \(O(\log n)\) From a set to the maximum element of the set+-- | /O(log n)/ Fetch the maximum value, or 'Nothing' if the set is empty lookupMax :: Set a -> Maybe a lookupMax = set Nothing go go go  where-  go _ a r _ recr = set (Just a) go' go' go' r where go' _ _ _ _ _ = recr+  go _ a r _ recr = set (Just a) go' go' go' r+   where+    go' _ _ _ _ _ = recr --- | \(O(\log n)\) From a set to the minimum element of the set+-- | /O(log n)/ Fetch the minimum value, or 'Nothing' if the set is empty lookupMin :: Set a -> Maybe a lookupMin = set Nothing go go go  where-  go l a _ recl _ = set (Just a) go' go' go' l where go' _ _ _ _ _ = recl+  go l a _ recl _ = set (Just a) go' go' go' l+   where+    go' _ _ _ _ _ = recl -{- | \(O(\log n)\) From an element and a set to whether the element is in the-set--}+-- | /O(log n)/ Check whether a value is in a set member :: (Ord a) => a -> Set a -> Bool member a = set False go go go  where@@ -783,26 +768,23 @@     EQ -> True     GT -> recr --- | \(O(1)\) From a set to whether the set is empty+-- | /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)\) From a set to the size of the set+-- | /O(n)/ Get the size of a set size :: Set a -> Int-size =-  set-    0-    (\_ _ _ recl recr -> 1 + recl + recr)-    (\_ _ _ recl recr -> 1 + recl + recr)-    (\_ _ _ recl recr -> 1 + recl + recr)+size = set 0 go go go+ where+  go _ _ _ recl recr = 1 + recl + recr  {-  - Validation  -} -{- | \(O(n)\) From a set to whether its internal structure is valid, i.e.-height-balanced and ordered--}+-- | /O(n)/ Check whether a set is internally height-balanced and ordered valid :: (Ord a) => Set a -> Bool valid = liftM2 (&&) balanced ordered  where@@ -812,19 +794,14 @@       (\l _ r recl recr -> levels l - levels r == 1 && recl && recr)       (\l _ r recl recr -> levels l - levels r == 0 && recl && recr)       (\l _ r recl recr -> levels r - levels l == 1 && recl && recr)-  levels = set 0 go go go where go _ _ _ recl recr = 1 + max recl recr :: Int+  levels = set 0 go go go+   where+    go _ _ _ recl recr = 1 + max recl recr :: Int   ordered = set True go go go    where     go l a r recl recr =-      set-        True-        (\_ la _ _ _ -> la < a && recl && recr)-        (\_ la _ _ _ -> la < a && recl && recr)-        (\_ la _ _ _ -> la < a && recl && recr)-        l-        && set-          True-          (\_ ra _ _ _ -> ra > a && recl && recr)-          (\_ ra _ _ _ -> ra > a && recl && recr)-          (\_ ra _ _ _ -> ra > a && recl && recr)-          r+      set True lt lt lt l+        && set True gt gt gt r+     where+      lt _ la _ _ _ = la < a && recl && recr+      gt _ ra _ _ _ = ra > a && recl && recr

mini.cabal view

@@ -1,6 +1,6 @@ cabal-version:      2.4 name:               mini-version:            1.3.0.0+version:            1.3.0.1 license:            MIT license-file:       LICENSE copyright:          (c) 2023-2024 Victor Wallsten