bimap 0.2.4 → 0.3.0

raw patch · 3 files changed

+118/−41 lines, 3 filesdep ~basenew-uploaderPVP ok

version bump matches the API change (PVP)

Dependency ranges changed: base

API changes (from Hackage documentation)

Files

• Data/Bimap.hs +48/−17
• Test/Tests.hs +59/−11
• bimap.cabal +11/−13

@@ -67,6 +67,10 @@     elems,     assocs,     fold,+    Data.Bimap.map,+    mapR,+    mapMonotonic,+    mapMonotonicR,     toMap,     toMapR,     -- * Miscellaneous@@ -79,6 +83,7 @@ import qualified Data.Map as M import Prelude hiding (lookup, null, filter, pred) import qualified Prelude as P+import Data.Maybe(fromMaybe)   infixr 9 .:@@ -174,7 +179,7 @@ tryInsert :: (Ord a, Ord b)           => a -> b -> Bimap a b -> Bimap a b tryInsert x y bi-    | (x `notMember` bi && y `notMemberR` bi) = unsafeInsert x y bi+    | x `notMember` bi && y `notMemberR` bi = unsafeInsert x y bi     | otherwise                               = bi  {-| /O(log n)/.@@ -194,12 +199,12 @@        => Either a b -> Bimap a b -> Bimap a b deleteE e (MkBimap left right) =     MkBimap-        (perhaps M.delete x $ left)-        (perhaps M.delete y $ right)+        (perhaps M.delete x  left)+        (perhaps M.delete y  right)     where     perhaps = maybe id-    x = either Just (flip M.lookup right) e-    y = either (flip M.lookup left) Just  e+    x = either Just (`M.lookup` right) e+    y = either (`M.lookup` left) Just  e  {-| /O(log n)/. Delete a value and its twin from a bimap.@@ -227,7 +232,7 @@         => a -> Bimap a b -> m b lookup x (MkBimap left _) =     maybe (fail "Data.Bimap.lookup: Left key not found")-          (return)+          return           (M.lookup x left)  {-| /O(log n)/.@@ -238,7 +243,7 @@         => b -> Bimap a b -> m a lookupR y (MkBimap _ right) =     maybe (fail "Data.Bimap.lookupR: Right key not found")-          (return)+          return           (M.lookup y right)  {-| /O(log n)/.@@ -246,18 +251,14 @@ Calls @'error'@ when the key is not in the bimap. /Version: 0.2/-} (!) :: (Ord a, Ord b) => Bimap a b -> a -> b-(!) bi x = case lookup x bi of-    Just y  -> y-    Nothing -> error "Data.Bimap.(!): Left key not found"+(!) bi x = fromMaybe (error "Data.Bimap.(!): Left key not found") $ lookup x bi  {-| /O(log n)/. A version of @(!)@ that is specialized to the right key, and returns the corresponding left key. /Version: 0.2/-} (!>) :: (Ord a, Ord b) => Bimap a b -> b -> a-(!>) bi y = case lookupR y bi of-    Just x  -> x-    Nothing -> error "Data.Bimap.(!>): Right key not found"+(!>) bi y = fromMaybe (error "Data.Bimap.(!>): Right key not found") $ lookupR y bi  {-| /O(n*log n)/. Build a map from a list of pairs. If there are any overlapping@@ -265,7 +266,7 @@ /Version: 0.2/-} fromList :: (Ord a, Ord b)          => [(a, b)] -> Bimap a b-fromList xs = foldl' (flip . uncurry $ insert) empty xs+fromList = foldl' (flip . uncurry $ insert) empty  {-| /O(n*log n)/. Build a map from a list of pairs. Unlike 'fromList', earlier pairs@@ -281,7 +282,7 @@ /Version: 0.2.2/-} fromAList :: (Ord a, Ord b)           => [(a, b)] -> Bimap a b-fromAList xs = foldl' (flip . uncurry $ tryInsert) empty xs+fromAList = foldl' (flip . uncurry $ tryInsert) empty  {-| /O(n)/. Convert to a list of associated pairs. /Version: 0.2/-}@@ -324,7 +325,7 @@                          => [(a, b)] -> Bimap a b fromAscPairListUnchecked xs = MkBimap     (M.fromAscList xs)-    (M.fromAscList $ map swap  xs)+    (M.fromAscList $ P.map swap  xs)     where     swap (x, y) = (y, x) @@ -427,7 +428,7 @@     [ M.valid left, M.valid right     , (==)         (sort .                M.toList $ left )-        (sort . map flipPair . M.toList $ right)+        (sort . P.map flipPair . M.toList $ right)     ]     where     flipPair (x, y) = (y, x)@@ -451,6 +452,36 @@ /Version: 0.2/-} fold :: (a -> b -> c -> c) -> c -> Bimap a b -> c fold f z = foldr (uncurry f) z . assocs++{-| /O(n*log n)/+Map a function over all the left keys in the map.+/Version 0.3/-}+map :: Ord c => (a -> c) -> Bimap a b -> Bimap c b+map f (MkBimap left right) =+    MkBimap (M.mapKeys f left) (M.map f right)++{-| /O(n*log n)/+Map a function over all the right keys in the map.+/Version 0.3/-}+mapR :: Ord c => (b -> c) -> Bimap a b -> Bimap a c+mapR f (MkBimap left right) =+    MkBimap (M.map f left) (M.mapKeys f right)++{-| /O(n)/.+Map a strictly increasing function over all left keys in the map.+/The precondition is not checked./+/Version 0.3/-}+mapMonotonic :: (a -> c) -> Bimap a b -> Bimap c b+mapMonotonic f (MkBimap left right) =+    MkBimap (M.mapKeysMonotonic f left) (M.map f right)++{-| /O(n)/.+Map a strictly increasing function over all right keys in the map.+/The precondition is not checked./+/Version 0.3/-}+mapMonotonicR :: (b -> c) -> Bimap a b -> Bimap a c+mapMonotonicR f (MkBimap left right) =+    MkBimap (M.map f left) (M.mapKeysMonotonic f right)  {-| /O(log n)/. Delete and find the element with maximal left key.

@@ -2,10 +2,10 @@  import Data.List (sort) import qualified Data.Set as S-import Prelude hiding (null, lookup, filter)+import Prelude hiding (null, lookup, filter,map) import qualified Prelude as P import Test.QuickCheck-import Test.QuickCheck.Batch+import Control.Applicative((<$>))  import Data.Bimap @@ -15,6 +15,9 @@ instance (Ord a, Arbitrary a, Ord b, Arbitrary b)     => Arbitrary (Bimap a b) where     arbitrary = fromList `fmap` arbitrary++instance (Ord a, CoArbitrary a, Ord b, CoArbitrary b)+    => CoArbitrary (Bimap a b) where     coarbitrary = coarbitrary . toList  -- generator for filter/partition classification functions@@ -28,6 +31,8 @@         return $ FilterFunc             ("(\\x y -> x - y < " ++ show pivot ++ ")")             (\x y -> fromIntegral x - fromIntegral y < pivot)+instance (Integral a, CoArbitrary a, Integral b, CoArbitrary b)+    => CoArbitrary (FilterFunc a b) where     coarbitrary _ gen = do         x <- arbitrary         coarbitrary (x :: Int) gen@@ -56,8 +61,8 @@     bi = fromList xs     isMember x = x `pairMember` bi     notUnique (x, y) = -        ((>1) . length . P.filter (== x) . map fst $ xs) ||-        ((>1) . length . P.filter (== y) . map snd $ xs)+        ((>1) . length . P.filter (== x) . P.map fst $ xs) ||+        ((>1) . length . P.filter (== y) . P.map snd $ xs)  -- a bimap created from a list is no larger than the list prop_fromList_size xs = (size $ fromList xs) <= length xs@@ -66,21 +71,17 @@  -- a monotone bimap can be reconstituted via fromAscPairList prop_fromAscPairList_reconstitute xs = and-    [ (not . isBottom) bi'-    , valid bi'+    [ valid bi'     , (bi == bi')     ]     where-    xs' = zip (sort $ map fst xs) (sort $ map snd xs)+    xs' = zip (sort $ P.map fst xs) (sort $ P.map snd xs)     bi :: Bimap Int Integer     bi = fromList xs'     bi' = fromAscPairList . toAscList $ bi  -- fromAscPairList will never produce an invalid bimap-prop_fromAscPairList_check xs = or-    [ isBottom bi-    , valid bi-    ]+prop_fromAscPairList_check xs = valid bi     where     bi :: Bimap Int Integer     bi = fromAscPairList xs@@ -442,3 +443,50 @@     where     _ = bi :: Bimap Int Integer +prop_map_preserve_keys bi =+    (Data.List.sort $ P.map f $ keys bi) == (keys $ map f bi)+    where+    f = (4/) -- This is an arbitrary function+    _ = bi :: Bimap Double Integer++prop_map_preserve_lookup bi v =+    (lookup (f v) $ map f bi) == (lookup v bi :: Maybe Integer)+    where+    f = (1-)+    _ = bi :: Bimap Int Integer++prop_map_preserve_right_keys bi =+    (Data.List.sort $ P.map f $ keysR bi) == (keysR $ mapR f bi)+    where+    f = (4/) -- This is an arbitrary function+    _ = bi :: Bimap Int Double++prop_map_preserve_lookupR bi v =+    (lookup v $ mapR f bi) == (f <$> lookup v bi :: Maybe Integer)+    where+    f = (1-)+    _ = bi :: Bimap Int Integer++prop_mapMonotonic_preserve_keys bi =+    (P.map f $ keys bi) == (keys $ mapMonotonic f bi)+    where+    f = (3+) -- This is an arbitrary monotonic function+    _ = bi :: Bimap Double Integer++prop_mapMonotonic_preserve_lookup bi v =+    (lookup (f v) $ mapMonotonic f bi) == (lookup v bi :: Maybe Integer)+    where+    f = (2*)+    _ = bi :: Bimap Int Integer++prop_mapMontonic_preserve_right_keys bi =+    (P.map f $ keysR bi) == (keysR $ mapMonotonicR f bi)+    where+    f = (^2) -- This is an arbitrary monotonic function+    _ = bi :: Bimap Int Double++prop_mapMonotonic_preserve_lookupR bi v =+    (lookup v $ mapMonotonicR f bi) == (f <$> lookup v bi :: Maybe Integer)+    where+    f = (1-)+    _ = bi :: Bimap Int Integer

@@ -1,6 +1,6 @@-cabal-version:       >= 1.2.3.0+cabal-version:       >= 1.6 name:                bimap-version:             0.2.4+version:             0.3.0 synopsis:            Bidirectional mapping between two key types description:   A data structure representing a bidirectional mapping between two@@ -9,14 +9,14 @@ category:            Data license:             BSD3 license-file:        LICENSE-copyright:           Stuart Cook and contributors 2008-author:              Stuart Cook and contributors 2008-maintainer:          scook0@gmail.com-homepage:            http://code.haskell.org/bimap+copyright:           Stuart Cook and contributors 2008, Joel Williamson 2015+author:              Stuart Cook and contributors 2008, Joel Williamson 2015+maintainer:          Joel Williamson <joel@joelwilliamson.ca>+homepage:            https://github.com/joelwilliamson/bimap -- This build-type is a lie, but we're only using hooks to specify -- a test command, so there shouldn't be any problems. build-type:          Simple-tested-with:         GHC ==6.6, GHC ==6.8.1+tested-with:         GHC ==7.8.4 extra-source-files:     HISTORY     tests.sh@@ -24,14 +24,12 @@     Test/Util.hs     Test/RunTests.hs -flag small-base- Library-  if flag(small-base)-    build-depends:       base >= 3, containers-  else-    build-depends:       base < 3+  build-depends:       base >= 4 && <5, containers   ghc-options:         -Wall   exposed-modules:       Data.Bimap +source-repository head+    type:         git+    location:     https://github.com/joelwilliamson/bimap.git