Add Data.IntSet.mapMonotonic. (#664)
authorJavran Cheng <Javran.c@gmail.com>
Wed, 24 Jul 2019 10:36:02 +0000 (03:36 -0700)
committerDavid Feuer <David.Feuer@gmail.com>
Wed, 24 Jul 2019 10:36:02 +0000 (06:36 -0400)
* Add Data.IntSet.mapMonotonic.

This patch fills in the missing piece for Data.IntSet,
since Data.{Map,IntMap} and Data.Set all have this function.
(for Map variant it's `mapKeysMonotonic`)

* test mapMonotonic property on id and linear.

containers-tests/tests/intset-properties.hs
containers/src/Data/IntSet.hs
containers/src/Data/IntSet/Internal.hs

index c2a7f0a..1233858 100644 (file)
@@ -337,6 +337,21 @@ prop_foldL' s = foldl' (flip (:)) [] s == List.foldl' (flip (:)) [] (toList s)
 prop_map :: IntSet -> Bool
 prop_map s = map id s == s
 
+-- Note: we could generate an arbitrary strictly monotonic function by
+-- restricting f using @\x y -> x < y ==> f x < f y@
+-- but this will be inefficient given the probability of actually finding
+-- a function that meets the criteria.
+-- For now we settle on identity function and arbitrary linear functions
+-- f x = a*x + b (with a being positive).
+-- This might be insufficient to support any fancier implementation.
+prop_mapMonotonicId :: IntSet -> Property
+prop_mapMonotonicId s = mapMonotonic id s === map id s
+
+prop_mapMonotonicLinear :: Positive Int -> Int -> IntSet -> Property
+prop_mapMonotonicLinear (Positive a) b s = mapMonotonic f s === map f s
+  where
+    f x = a*x + b
+
 prop_maxView :: IntSet -> Bool
 prop_maxView s = case maxView s of
     Nothing -> null s
index d401247..86e3dd5 100644 (file)
@@ -115,6 +115,7 @@ module Data.IntSet (
 
             -- * Map
             , IS.map
+            , mapMonotonic
 
             -- * Folds
             , IS.foldr
index df7c04a..2a824a4 100644 (file)
@@ -141,6 +141,7 @@ module Data.IntSet.Internal (
 
     -- * Map
     , map
+    , mapMonotonic
 
     -- * Folds
     , foldr
@@ -911,6 +912,21 @@ deleteMax = maybe Nil snd . maxView
 map :: (Key -> Key) -> IntSet -> IntSet
 map f = fromList . List.map f . toList
 
+-- | /O(n)/. The
+--
+-- @'mapMonotonic' f s == 'map' f s@, but works only when @f@ is strictly increasing.
+-- /The precondition is not checked./
+-- Semi-formally, we have:
+--
+-- > and [x < y ==> f x < f y | x <- ls, y <- ls]
+-- >                     ==> mapMonotonic f s == map f s
+-- >     where ls = toList s
+
+-- Note that for now the test is insufficient to support any fancier implementation.
+mapMonotonic :: (Key -> Key) -> IntSet -> IntSet
+mapMonotonic f = fromDistinctAscList . List.map f . toAscList
+
+
 {--------------------------------------------------------------------
   Fold
 --------------------------------------------------------------------}