-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Bidirectional mapping between two key types -- -- A data structure representing a bidirectional mapping between two key -- types. Each value in the bimap is associated with exactly one value of -- the opposite type. @package bimap @version 0.3.2 -- | An implementation of bidirectional maps between values of two 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 right-hand type as the -- key and the left-hand type as the value. module Data.Bimap -- | A bidirectional map between values of types a and b. data Bimap a b -- | O(1). Is the bimap empty? Version: 0.2 null :: Bimap a b -> Bool -- | O(1). The number of elements in the bimap. Version: 0.2 size :: Bimap a b -> Int -- | 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 -- | 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 -- | 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 -- | 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 -- | 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 -- | 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 -- | 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, MonadThrow m) => a -> Bimap a b -> m b -- | 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, MonadThrow m) => b -> Bimap a b -> m a -- | 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 -- | 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 -- | O(1). The empty bimap. Version: 0.2 empty :: Bimap a b -- | O(1). A bimap with a single element. Version: 0.2 singleton :: a -> b -> Bimap a b -- | 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 -- | O(log n). Insert a pair of values into the bimap, but only if -- neither is already in the bimap. Version: 0.2.2 tryInsert :: (Ord a, Ord b) => a -> b -> Bimap a b -> Bimap a b -- | O(log n). Update a value at a specific left key with the result -- of the provided function. -- -- When the left key is not a member of the bimap, the original bimap is -- returned. adjust :: (Ord a, Ord b) => (b -> b) -> a -> Bimap a b -> Bimap a b -- | O(log n). Update a value at a specific right key with the -- result of the provided function. -- -- When the right key is not a member of the bimap, the original bimap is -- returned. adjustR :: (Ord a, Ord b) => (a -> a) -> b -> Bimap a b -> Bimap a b -- | O(log n). Adjust a value at a specific left key. -- -- When the left key is not a member of the bimap, the original bimap is -- returned. adjustWithKey :: (Ord a, Ord b) => (a -> b -> b) -> a -> Bimap a b -> Bimap a b -- | O(log n). Adjust a value at a specific right key. -- -- When the right key is not a member of the bimap, the original bimap is -- returned. adjustWithKeyR :: (Ord a, Ord b) => (b -> a -> a) -> b -> Bimap a b -> Bimap a b -- | O(log n). The expression (update f a bimap) -- updates the right value b at a (if it is in the -- bimap). -- -- If (f b) is Nothing, the element is deleted. -- -- If it is (Just y), the left key a is bound to -- the new value y. update :: (Ord a, Ord b) => (b -> Maybe b) -> a -> Bimap a b -> Bimap a b -- | O(log n). The expression (updateR f b bimap) -- updates the left value a at b (if it is in the -- bimap). -- -- If (f a) is Nothing, the element is deleted. -- -- If it is (Just x), the right key b is bound -- to the new value x. updateR :: (Ord a, Ord b) => (a -> Maybe a) -> b -> Bimap a b -> Bimap a b -- | O(log n). The expression (updateWithKey f a -- bimap) updates the right value b at a (if it is -- in the bimap). -- -- If (f a b) is Nothing, the element is deleted. -- -- If it is (Just y), the left key a is bound to -- the new value y. updateWithKey :: (Ord a, Ord b) => (a -> b -> Maybe b) -> a -> Bimap a b -> Bimap a b -- | O(log n). The expression (updateWithKeyR f b -- bimap) updates the left value a at b (if it is -- in the bimap). -- -- If (f b a) is Nothing, the element is deleted. -- -- If it is (Just x), the right key b is bound -- to the new value x. updateWithKeyR :: (Ord a, Ord b) => (b -> a -> Maybe a) -> b -> Bimap a b -> Bimap a b -- | 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 -- | 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 -- | O(log n). Find the element with minimal left key. Calls -- error if the bimap is empty. Version: 0.2.2 findMin :: Bimap a b -> (a, b) -- | O(log n). Find the element with minimal right key. The -- right-hand key is the first entry in the pair. Calls -- error if the bimap is empty. Version: 0.2.2 findMinR :: Bimap a b -> (b, a) -- | O(log n). Find the element with maximal left key. Calls -- error if the bimap is empty. Version: 0.2.2 findMax :: Bimap a b -> (a, b) -- | O(log n). Find the element with maximal right key. The -- right-hand key is the first entry in the pair. Calls -- error if the bimap is empty. Version: 0.2.2 findMaxR :: Bimap a b -> (b, a) -- | O(log n). Delete the element with minimal left key. Calls -- error if the bimap is empty. Version: 0.2.2 deleteMin :: (Ord b) => Bimap a b -> Bimap a b -- | O(log n). Delete the element with minimal right key. Calls -- error if the bimap is empty. Version: 0.2.2 deleteMinR :: (Ord a) => Bimap a b -> Bimap a b -- | O(log n). Delete the element with maximal left key. Calls -- error if the bimap is empty. Version: 0.2.2 deleteMax :: (Ord b) => Bimap a b -> Bimap a b -- | O(log n). Delete the element with maximal right key. Calls -- error if the bimap is empty. Version: 0.2.2 deleteMaxR :: (Ord a) => Bimap a b -> Bimap a b -- | O(log n). Delete and find the element with minimal left key. -- Calls error if the bimap is empty. Version: -- 0.2.2 deleteFindMin :: (Ord b) => Bimap a b -> ((a, b), Bimap a b) -- | O(log n). Delete and find the element with minimal right key. -- Calls error if the bimap is empty. Version: -- 0.2.2 deleteFindMinR :: (Ord a) => Bimap a b -> ((b, a), Bimap a b) -- | O(log n). Delete and find the element with maximal left key. -- Calls error if the bimap is empty. Version: -- 0.2.2 deleteFindMax :: (Ord b) => Bimap a b -> ((a, b), Bimap a b) -- | O(log n). Delete and find the element with maximal right key. -- Calls error if the bimap is empty. Version: -- 0.2.2 deleteFindMaxR :: (Ord a) => Bimap a b -> ((b, a), Bimap a b) -- | O(n). Filter all association pairs that satisfy the predicate. -- -- Note that the predicate will be applied twice for each -- association in the bimap. -- -- Version: 0.2.4 filter :: (Ord a, Ord b) => (a -> b -> Bool) -> Bimap a b -> Bimap a b -- | O(n). Partition the bimap according to a predicate. The first -- bimap contains all associations that satisfy the predicate; the second -- contains all associations that fail the predicate. -- -- Note that the predicate will be applied twice for each -- association in the bimap. -- -- Version: 0.2.4 partition :: (Ord a, Ord b) => (a -> b -> Bool) -> Bimap a b -> (Bimap a b, Bimap a b) -- | 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 -- | O(n*log n). Build a map from a list of pairs. Unlike -- fromList, earlier pairs will take precedence over later ones. -- -- The name fromAList is a reference to Lisp-style association -- lists, where associations can be overridden by prepending new ones. -- -- Note that when duplicates occur in both the keys and in the values, -- fromList xs /= fromAList (reverse xs). However, if either -- contains no duplicates, then the equality holds. -- -- Version: 0.2.2 fromAList :: (Ord a, Ord b) => [(a, b)] -> Bimap a b -- | O(n). Build a bimap from a list of pairs, where both the -- fst and snd halves of the list are in strictly -- ascending order. -- -- This precondition is checked; an invalid list will cause an error. -- -- Version: 0.2.3 fromAscPairList :: (Ord a, Ord b) => [(a, b)] -> Bimap a b -- | O(n). Build a bimap from a list of pairs, where both the -- fst and snd halves of the list are in strictly -- ascending order. -- -- This precondition is not checked; an invalid list will produce -- a malformed bimap. -- -- Version: 0.2.3 fromAscPairListUnchecked :: (Ord a, Ord b) => [(a, b)] -> Bimap a b -- | O(n). Convert to a list of associated pairs. Version: -- 0.2 toList :: Bimap a b -> [(a, b)] -- | 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)] -- | 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)] -- | O(n). Return all left-hand keys in the bimap in ascending -- order. Version: 0.2 keys :: Bimap a b -> [a] -- | O(n). Return all right-hand keys in the bimap in ascending -- order. Version: 0.2 keysR :: Bimap a b -> [b] -- | O(n). An alias for keysR. Version: 0.2 elems :: Bimap a b -> [b] -- | 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)] -- | 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 -- | 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 -- | 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 -- | 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 -- | 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 -- | O(1). Extract only the left-to-right component of a bimap. -- Version: 0.2.1 toMap :: Bimap a b -> Map a b -- | O(1). Extract only the right-to-left component of a bimap. -- Version: 0.2.1 toMapR :: Bimap a b -> Map b a -- | O(n*log n). Test if the internal bimap structure is valid. This -- should be true for any bimap created using the public interface, -- unless fromAscPairListUnchecked has been used inappropriately. -- Version: 0.2 valid :: (Ord a, Ord b) => Bimap a b -> Bool -- | O(1). Reverse the positions of the two element types in the -- bimap. Version: 0.2 twist :: Bimap a b -> Bimap b a -- | 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) instance GHC.Show.Show Data.Bimap.BimapException instance GHC.Classes.Eq Data.Bimap.BimapException instance (GHC.Show.Show a, GHC.Show.Show b) => GHC.Show.Show (Data.Bimap.Bimap a b) instance (GHC.Classes.Eq a, GHC.Classes.Eq b) => GHC.Classes.Eq (Data.Bimap.Bimap a b) instance GHC.Exception.Exception Data.Bimap.BimapException