mappings 0.2.2.0 → 0.3.0.0

raw patch · 4 files changed

+103/−16 lines, 4 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• CHANGELOG.md +8/−0
• mappings.cabal +3/−1
• src/Data/Mapping/Piecewise.hs +91/−14
• test/Data/Mapping/DecisionSpec.hs +1/−1

@@ -1,3 +1,11 @@+## [0.3.0.0] - 2023-12-06++* Extra functionality for `Data.Mapping.Piecewise`++## [0.2.2.0] - 2023-11-22++* Uses a newer version of `cond` allowing many newtypes to be derived.+ ## [0.1.0.0] - 2023-11-09  * `baseLength` and `decisionLength` functions

@@ -5,7 +5,7 @@ -- see: https://github.com/sol/hpack  name:           mappings-version:        0.2.2.0+version:        0.3.0.0 synopsis:       Types which represent functions k -> v description:    A typeclass and a number of implementations; please read README.md on github category:       Data structures@@ -19,6 +19,8 @@ extra-doc-files:     README.md     CHANGELOG.md++tested-with:    GHC==9.6.2, GHC==9.4.5, GHC==9.2.8  source-repository head   type: git

@@ -11,6 +11,7 @@ #endif import Control.Applicative (liftA3) import Data.Algebra.Boolean+import qualified Data.Map.Internal as MI import Data.Map.Strict (Map) import qualified Data.Map.Strict as M import qualified Data.Set as S@@ -24,41 +25,72 @@ -- right-continuous: values are in general defined on intervals $a -- \leq x < b$ which are closed on the left and open on the right. data Piecewise k v = Piecewise {+  -- | The value taken for sufficiently small keys   leftEnd :: v,   starts :: Map k v } deriving (Eq, Ord) -piecewiseFromAsc :: Eq k => v -> [(k,v)] -> Piecewise k v-piecewiseFromAsc k = Piecewise k . M.fromAscList+-- | The value taken for sufficiently large keys+rightEnd :: Piecewise k v -> v+rightEnd (Piecewise a m) = case M.lookupMax m of+  Nothing    -> a+  Just (_,b) -> b +-- | Assumes the keys are distinct and increasing (but consecutive+-- values may be the same, in which case the intervening keys are+-- removed)+fromAscList :: (Eq v) => v -> [(k,v)] -> Piecewise k v+fromAscList = let+  inner _ [] = []+  inner a ((y,b):r)+    | a == b    = inner a r+    | otherwise = (y,b):inner b r+  run x = Piecewise x . M.fromDistinctAscList . inner x+  in run+ instance (Show k, Show v) => Show (Piecewise k v) where   showsPrec d (Piecewise k m) =-    ("piecewiseFromAsc " <>) .+    ("fromAscList " <>) .     showsPrec d k .     (" " <>) .     showList (M.toList m) +-- | Assumes that the keys are distinct and increasing, and also that+-- consecutive values are distinct+fromAscListUnsafe :: v -> [(k,v)] -> Piecewise k v+fromAscListUnsafe k = Piecewise k . M.fromDistinctAscList++-- | Takes value `a` for keys less than `x` and `b` otherwise changeAt :: v -> k -> v -> Piecewise k v changeAt a x b = Piecewise a $ M.singleton x b -atLeast :: k -> Piecewise k Bool-atLeast k = changeAt False k True+-- | Is the value greater than or equal to `k`?+greaterThanOrEqual :: k -> Piecewise k Bool+greaterThanOrEqual k = changeAt False k True +-- | Is the value less than `k`? lessThan :: k -> Piecewise k Bool lessThan k = changeAt True k False -fromAscList :: (Ord k, Eq v) => v -> [(k,v)] -> Piecewise k v-fromAscList = let-  inner _ [] = []-  inner a ((y,b):r)-    | a == b    = inner a r-    | otherwise = (y,b):inner b r-  run x = Piecewise x . M.fromAscList . inner x-  in run+-- | Is the value greater than `k`? This is subject to the usual+-- concerns about `Enum` (it not to be used with floating-point+-- arithmetic, for example)+greaterThan :: Enum k => k -> Piecewise k Bool+greaterThan = greaterThanOrEqual . succ +-- | Is the value less than or equal to `k`? This is subject to the+-- usual concerns about `Enum` (it not to be used with floating-point+-- arithmetic, for example)+lessThanOrEqual :: Enum k => k -> Piecewise k Bool+lessThanOrEqual = lessThan . succ++-- | All values, in order of increasing key values :: Piecewise k v -> [v] values (Piecewise x m) = x : M.elems m +instance (Eq k) => Functor (Piecewise k) where+  fmap p (Piecewise a f) = fromAscListUnsafe (p a) (fmap p <$> M.toList f)+ instance Foldable (Piecewise k) where   foldMap f (Piecewise a m) = f a <> foldMap f m @@ -72,7 +104,7 @@    isConst (Piecewise a f) = if M.null f then Just a else Nothing -  mmap p (Piecewise a f) = fromAscList (p a) (fmap p <$> M.toList f)+  mmap = fmap    mtraverse p (Piecewise a f) = liftA2 fromAscList (p a) (traverse (traverse p) $ M.toList f) @@ -150,3 +182,48 @@  deriving via (AlgebraWrapper k (Piecewise k) b)   instance (Ord k, Ord b, Boolean b) => Boolean (Piecewise k b)++-- | Alter keys according to a function, assumed to be monotone (not checked)+mapKeysMonotonic :: (k -> l) -> Piecewise k v -> Piecewise l v+mapKeysMonotonic f (Piecewise a m) = Piecewise a (M.mapKeysMonotonic f m)++-- | Alter keys according to a function, assumed to be antitone (not checked)+mapKeysAntitonic :: (k -> l) -> Piecewise k v -> Piecewise l v+mapKeysAntitonic f = let++  inner a MI.Tip = (a, MI.Tip)+  inner a (MI.Bin s x b l r) = let+    (a', l') = inner a l+    (b', r') = inner b r+    in (b', MI.Bin s (f x) a' r' l')++  start (Piecewise a m) = uncurry Piecewise $ inner a m+  in start++-- | Split in two: one which assumes keys are less than `k`, and one+-- which assumes them greater than or equal to `k`.+splitPiecewise :: Ord k => k -> Piecewise k v -> (Piecewise k v, Piecewise k v)+splitPiecewise k (Piecewise a m) = case M.splitLookup k m of+  (m1, Just b, m2) -> (Piecewise a m1, Piecewise b m2)+  (m1, Nothing, m2) -> let+    p1 = Piecewise a m1+    in (p1, Piecewise (rightEnd p1) m2)++-- | Assemble two maps; it is assumed that all keys in the left-hand+-- map are less than `k` and all keys in the right-hand map are+-- greater than or equal to `k` (which is not checked).+gluePiecewise :: (Eq v) => Piecewise k v -> k -> Piecewise k v -> Piecewise k v+gluePiecewise p@(Piecewise a m) k (Piecewise c n) = let+  b = rightEnd p+  in Piecewise a (if b == c then MI.link2 m n else MI.link k c m n)++-- | This is almost a monad (with `cst` as `pure`) except that we need+-- an `Eq` instance on the values.+mjoin :: (Ord k, Eq w) => (v -> Piecewise k w) -> Piecewise k v -> Piecewise k w+mjoin f (Piecewise a m) = let+  inner p []        = p+  inner p ((k,q):l) = let+    (p',  _) = splitPiecewise k p+    (_ , q') = splitPiecewise k q+    in gluePiecewise p' k $ inner q' l+  in inner (f a) (fmap f <$> M.toList m)

@@ -114,7 +114,7 @@     let xyz = M.fromList [("X", 1), ("Y", 1), ("Z", 1)]     let monomials = M.fromList [(xy2, 1::Int), (x2y, 2), (xyz, 3)]     let f i b = if b then i else 0-    let d = M.foldlWithKey' (\t m i -> merge max t (mmap (f i) . buildAll $ fmap atLeast m)) (cst 0) monomials+    let d = M.foldlWithKey' (\t m i -> merge max t (mmap (f i) . buildAll $ fmap greaterThanOrEqual m)) (cst 0) monomials     let mapAct m = act d (\a -> M.findWithDefault 0 a $ M.fromList m)      it "should get the right monomial for w^2y^4" $ do