bimap 0.2 → 0.2.1
raw patch · 3 files changed
+173/−60 lines, 3 filesdep −mtlPVP ok
version bump matches the API change (PVP)
Dependencies removed: mtl
API changes (from Hackage documentation)
+ Data.Bimap: toMap :: Bimap a b -> Map a b
+ Data.Bimap: toMapR :: Bimap a b -> Map b a
Files
- Data/Bimap.hs +150/−57
- HISTORY +19/−0
- bimap.cabal +4/−3
Data/Bimap.hs view
@@ -3,10 +3,16 @@ key types. A 'Bimap' is essentially a bijection between subsets of its two argument types. +Each element of the left-hand type is associated with an element+of the right-hand type, and vice-versa, such that the two mappings+are inverses. Deleting an element will cause its twin to be deleted,+and inserting a pair of elements will cause any overlapping bindings+to be deleted.+ Most functions implicitly consider the left-hand type to be the key, and the right-hand type to be the value. Functions with an @R@ suffix reverse this convention, treating the-left-hand type as the key.+right-hand type as the key and the left-hand type as the value. -} module Data.Bimap ( -- * Bimap type@@ -41,14 +47,14 @@ elems, assocs, fold,+ toMap,+ toMapR, -- * Miscellaneous valid, twist, twisted, ) where -import Control.Arrow ((>>>))-import Control.Monad.Error () -- Monad instance for Either e import Data.List (foldl', sort) import qualified Data.Map as M import Prelude hiding (lookup, null)@@ -69,64 +75,91 @@ instance (Eq a, Eq b) => Eq (Bimap a b) where (==) bx by = toAscList bx == toAscList by -{-| The empty bimap. -}+{-| /O(1)/. The empty bimap.++/Version: 0.2/-} empty :: Bimap a b empty = MkBimap M.empty M.empty -{-| A bimap with a single element. -}+{-| /O(1)/. A bimap with a single element.++/Version: 0.2/-} singleton :: a -> b -> Bimap a b singleton x y = MkBimap (M.singleton x y) (M.singleton y x) -{-| Is the bimap empty? -}+{-| /O(1)/. Is the bimap empty?++/Version: 0.2/-} null :: Bimap a b -> Bool null (MkBimap left _) = M.null left -{-| The number of elements in the bimap. -}+{-| /O(1)/. The number of elements in the bimap.++/Version: 0.2/-} size :: Bimap a b -> Int size (MkBimap left _) = M.size left -{-| Is the specified value a member of the bimap? -}+{-| /O(log n)/. Is the specified value a member of the bimap?++/Version: 0.2/-} member :: (Ord a, Ord b) => a -> Bimap a b -> Bool member x (MkBimap left _) = M.member x left-{-| A version of 'member' specialized to the right key. -}+{-| /O(log n)/. A version of 'member' specialized to the right key.++/Version: 0.2/-} memberR :: (Ord a, Ord b) => b -> Bimap a b -> Bool memberR y (MkBimap _ right) = M.member y right -{-| Is the specified value not a member of the bimap? -}+{-| /O(log n)/. Is the specified value not a member of the bimap?++/Version: 0.2/-} notMember :: (Ord a, Ord b) => a -> Bimap a b -> Bool notMember = not .: member-{-| A version of 'notMember' specialized to the right key. -}+{-| /O(log n)/. A version of 'notMember' specialized to the right key.++/Version: 0.2/-} notMemberR :: (Ord a, Ord b) => b -> Bimap a b -> Bool notMemberR = not .: memberR -{-| Are the two values associated /with each other/ in the bimap?+{-| /O(log n)/.+Are the two values associated /with each other/ in the bimap? This function is uncurried in its first two arguments, so that it can be used infix.--}++/Version: 0.2/-} pairMember :: (Ord a, Ord b) => (a, b) -> Bimap a b -> Bool pairMember (x, y) (MkBimap left _) = maybe False (== y) (M.lookup x left) -{-| Are the two values not in the bimap, or not associated with-each other? (Complement of 'pairMember'.) -}+{-| /O(log n)/.+Are the two values not in the bimap, or not associated+with each other? (Complement of 'pairMember'.)++/Version: 0.2/-} pairNotMember :: (Ord a, Ord b) => (a, b) -> Bimap a b -> Bool pairNotMember = not .: pairMember -{-| Insert a pair of values into the bimap, associating them.+{-| /O(log n)/.+Insert a pair of values into the bimap, associating them.+ If either of the values is already in the bimap, any overlapping bindings are deleted.--}++/Version: 0.2/-} insert :: (Ord a, Ord b) => a -> b -> Bimap a b -> Bimap a b-insert x y = delete x- >>> deleteR y- >>> unsafeInsert x y+insert x y = delete x >>> deleteR y >>> unsafeInsert x y+ where+ (>>>) = flip (.) -{-| Insert a pair of values into the bimap, without checking for-overlapping bindings. If either value is already in the bimap, and+{-| /O(log n)/.+Insert a pair of values into the bimap, without checking for+overlapping bindings.++If either value is already in the bimap, and is not bound to the other value, the bimap will become inconsistent. -} unsafeInsert :: (Ord a, Ord b)@@ -134,7 +167,7 @@ unsafeInsert x y (MkBimap left right) = MkBimap (M.insert x y left) (M.insert y x right) -{-| Common implementation for 'delete' and 'deleteR'. -}+{-| /O(log n)/. Common implementation for 'delete' and 'deleteR'. -} deleteE :: (Ord a, Ord b) => Either a b -> Bimap a b -> Bimap a b deleteE e (MkBimap left right) =@@ -146,23 +179,29 @@ x = either Just (flip M.lookup right) e y = either (flip M.lookup left) Just e -{-| Delete a value and its twin from a bimap.+{-| /O(log n)/.+Delete a value and its twin from a bimap.+ When the value is not a member of the bimap, the original bimap is returned.--}++/Version: 0.2/-} delete :: (Ord a, Ord b) => a -> Bimap a b -> Bimap a b delete = deleteE . Left -{-| A version of 'delete' specialized to the right key. -}+{-| /O(log n)/ A version of 'delete' specialized to the right key.++/Version: 0.2/-} deleteR :: (Ord a, Ord b) => b -> Bimap a b -> Bimap a b deleteR = deleteE . Right -{-| Lookup a left key in the bimap, returning the associated right-key.+{-| /O(log n)/.+Lookup a left key in the bimap, returning the associated right key. This function will @return@ the result in the monad, or @fail@ if the value isn't in the bimap.--}++/Version: 0.2/-} lookup :: (Ord a, Ord b, Monad m) => a -> Bimap a b -> m b lookup x (MkBimap left _) =@@ -170,8 +209,11 @@ (return) (M.lookup x left) -{-| A version of 'lookup' that is specialized to the right key,-and returns only the left key. -}+{-| /O(log n)/.+A version of 'lookup' that is specialized to the right key,+and returns the corresponding left key.++/Version: 0.2/-} lookupR :: (Ord a, Ord b, Monad m) => b -> Bimap a b -> m a lookupR y (MkBimap _ right) =@@ -179,62 +221,107 @@ (return) (M.lookup y right) -{-| Find the right key corresponding to a given left key.+{-| /O(log n)/.+Find the right key corresponding to a given left key. Calls @'error'@ when the key is not in the bimap.--}++/Version: 0.2/-} (!) :: (Ord a, Ord b) => Bimap a b -> a -> b-(!) bi x = either error id (lookup x bi)+(!) bi x = case lookup x bi of+ Just y -> y+ Nothing -> error "Data.Bimap.(!): Left key not found" -{-| A version of @(!)@ that is specialized to the right key,-and returns only the left key. -}+{-| /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 = either error id (lookupR y bi)+(!>) bi y = case lookupR y bi of+ Just x -> x+ Nothing -> error "Data.Bimap.(!>): Right key not found" -{-| Build a map from a list of pairs. If there are any overlapping+{-| /O(n*log n)/.+Build a map from a list of pairs. If there are any overlapping pairs in the list, the later ones will override the earlier ones.--}++/Version: 0.2/-} fromList :: (Ord a, Ord b) => [(a, b)] -> Bimap a b fromList xs = foldl' (flip . uncurry $ insert) empty xs -{-| Convert to a list of associated pairs. -}+{-| /O(n)/. Convert to a list of associated pairs.++/Version: 0.2/-} toList :: Bimap a b -> [(a, b)] toList = toAscList -{-| Convert to a list of associated pairs, with the left-hand+{-| /O(n)/.+Convert to a list of associated pairs, with the left-hand values in ascending order.+ Since pair ordering is lexical, the pairs will also be in ascending order.--}++/Version: 0.2/-} toAscList :: Bimap a b -> [(a, b)] toAscList (MkBimap left _) = M.toList left -{-| Convert to a list of associated pairs, with the right-hand+{-| /O(n)/.+Convert to a list of associated pairs, with the right-hand values first in the pair and in ascending order.+ Since pair ordering is lexical, the pairs will also be in ascending order.--}++/Version: 0.2/-} toAscListR :: Bimap a b -> [(b, a)] toAscListR = toAscList . twist -{-| Return all associated pairs in the bimap, with the left-hand-values in ascending order. -}+{-| /O(n)/.+Return all associated pairs in the bimap, with the left-hand+values in ascending order.++/Version: 0.2/-} assocs :: Bimap a b -> [(a, b)] assocs = toList -{-| Return all left-hand keys in the bimap in ascending order. -}+{-| /O(n)/.+Return all left-hand keys in the bimap in ascending order.++/Version: 0.2/-} keys :: Bimap a b -> [a] keys (MkBimap left _) = M.keys left -{-| Return all right-hand keys in the bimap in ascending order. -}+{-| /O(n)/.+Return all right-hand keys in the bimap in ascending order.++/Version: 0.2/-} keysR :: Bimap a b -> [b] keysR (MkBimap _ right) = M.keys right -{-| An alias for 'keysR'. -}+{-| /O(n)/. An alias for 'keysR'.++/Version: 0.2/-} elems :: Bimap a b -> [b] elems = keysR -{-| Test if the internal bimap structure is valid. -}+{-| /O(1)/. Extract only the left-to-right component of a bimap.++/Version: 0.2.1/-}+toMap :: Bimap a b -> M.Map a b+toMap (MkBimap left _) = left++{-| /O(1)/. Extract only the right-to-left component of a bimap.++/Version: 0.2.1/-}+toMapR :: Bimap a b -> M.Map b a+toMapR (MkBimap _ right) = right++{-| /O(n*log n)/.+Test if the internal bimap structure is valid.++/Version: 0.2/-} valid :: (Ord a, Ord b) => Bimap a b -> Bool valid (MkBimap left right) = and@@ -246,20 +333,26 @@ where flipPair (x, y) = (y, x) -{-| Reverse the positions of the two element types in the bimap. -}+{-| /O(1)/.+Reverse the positions of the two element types in the bimap.++/Version: 0.2/-} twist :: Bimap a b -> Bimap b a twist (MkBimap left right) = MkBimap right left -{-| Reverse the positions of the two element types in a bimap-transformation. -}+{-| /O(1)/.+Reverse the positions of the two element types in a bimap+transformation.++/Version: 0.2/-} twisted :: (Bimap a b -> Bimap a b) -> (Bimap b a -> Bimap b a) twisted f = twist . f . twist -{-| Fold the association pairs in the map, such that+{-| /O(n)/.+Fold the association pairs in the map, such that @'fold' f z == 'foldr' f z . 'assocs'@.--}++/Version: 0.2/-} fold :: (a -> b -> c -> c) -> c -> Bimap a b -> c fold f z = foldr (uncurry f) z . assocs--
+ HISTORY view
@@ -0,0 +1,19 @@+Version 0.2.1 (6 Feb 2008)++ * removed MTL dependency+ * removed Control.Arrow dependency+ * now Haskell 98, modulo "foldl'" and hierarchical modules+ * added toMap and toMapR+ * added big-O comments+ * added "version" info in function comments++Version 0.2 (5 Feb 2008)++ * large, incompatible interface overhaul+ * GHC 6.8 support+ * Eq instance++Version 0.1 (4 Feb 2008)++ * initial release+ * Data.Bimap and test suite
bimap.cabal view
@@ -1,6 +1,6 @@ cabal-version: >= 1.2.3.0 name: bimap-version: 0.2+version: 0.2.1 synopsis: Bidirectional mapping between two key types description: A data structure representing a bidirectional mapping between two@@ -18,6 +18,7 @@ build-type: Simple tested-with: GHC ==6.6, GHC ==6.8.1 extra-source-files:+ HISTORY tests.sh Test/Tests.hs Test/Util.hs@@ -27,9 +28,9 @@ Library if flag(small-base)- build-depends: base >= 3, mtl, containers+ build-depends: base >= 3, containers else- build-depends: base < 3, mtl+ build-depends: base < 3 ghc-options: -Wall -O2 exposed-modules: Data.Bimap