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.
- data Bimap a b
- null :: Bimap a b -> Bool
- size :: Bimap a b -> Int
- member :: (Ord a, Ord b) => a -> Bimap a b -> Bool
- memberR :: (Ord a, Ord b) => b -> Bimap a b -> Bool
- notMember :: (Ord a, Ord b) => a -> Bimap a b -> Bool
- notMemberR :: (Ord a, Ord b) => b -> Bimap a b -> Bool
- pairMember :: (Ord a, Ord b) => (a, b) -> Bimap a b -> Bool
- pairNotMember :: (Ord a, Ord b) => (a, b) -> Bimap a b -> Bool
- lookup :: (Ord a, Ord b, Monad m) => a -> Bimap a b -> m b
- lookupR :: (Ord a, Ord b, Monad m) => b -> Bimap a b -> m a
- (!) :: (Ord a, Ord b) => Bimap a b -> a -> b
- (!>) :: (Ord a, Ord b) => Bimap a b -> b -> a
- empty :: Bimap a b
- singleton :: a -> b -> Bimap a b
- insert :: (Ord a, Ord b) => a -> b -> Bimap a b -> Bimap a b
- delete :: (Ord a, Ord b) => a -> Bimap a b -> Bimap a b
- deleteR :: (Ord a, Ord b) => b -> Bimap a b -> Bimap a b
- fromList :: (Ord a, Ord b) => [(a, b)] -> Bimap a b
- toList :: Bimap a b -> [(a, b)]
- toAscList :: Bimap a b -> [(a, b)]
- toAscListR :: Bimap a b -> [(b, a)]
- keys :: Bimap a b -> [a]
- keysR :: Bimap a b -> [b]
- elems :: Bimap a b -> [b]
- assocs :: Bimap a b -> [(a, b)]
- fold :: (a -> b -> c -> c) -> c -> Bimap a b -> c
- toMap :: Bimap a b -> Map a b
- toMapR :: Bimap a b -> Map b a
- valid :: (Ord a, Ord b) => Bimap a b -> Bool
- twist :: Bimap a b -> Bimap b a
- twisted :: (Bimap a b -> Bimap a b) -> Bimap b a -> Bimap b a
Bimap type
A bidirectional map between values of types a
and b
.
Query
member :: (Ord a, Ord b) => a -> Bimap a b -> BoolSource
O(log n). Is the specified value a member of the bimap?
Version: 0.2
memberR :: (Ord a, Ord b) => b -> Bimap a b -> BoolSource
O(log n). A version of member
specialized to the right key.
Version: 0.2
notMember :: (Ord a, Ord b) => a -> Bimap a b -> BoolSource
O(log n). Is the specified value not a member of the bimap?
Version: 0.2
notMemberR :: (Ord a, Ord b) => b -> Bimap a b -> BoolSource
O(log n). A version of notMember
specialized to the right key.
Version: 0.2
pairMember :: (Ord a, Ord b) => (a, b) -> Bimap a b -> BoolSource
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
pairNotMember :: (Ord a, Ord b) => (a, b) -> Bimap a b -> BoolSource
O(log n).
Are the two values not in the bimap, or not associated
with each other? (Complement of pairMember
.)
Version: 0.2
lookup :: (Ord a, Ord b, Monad m) => a -> Bimap a b -> m bSource
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
lookupR :: (Ord a, Ord b, Monad m) => b -> Bimap a b -> m aSource
O(log n).
A version of lookup
that is specialized to the right key,
and returns the corresponding left key.
Version: 0.2
(!) :: (Ord a, Ord b) => Bimap a b -> a -> bSource
O(log n).
Find the right key corresponding to a given left key.
Calls
when the key is not in the bimap.
error
Version: 0.2
(!>) :: (Ord a, Ord b) => Bimap a b -> b -> aSource
O(log n).
A version of (!)
that is specialized to the right key,
and returns the corresponding left key.
Version: 0.2
Construction
Update
insert :: (Ord a, Ord b) => a -> b -> Bimap a b -> Bimap a bSource
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
delete :: (Ord a, Ord b) => a -> Bimap a b -> Bimap a bSource
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
deleteR :: (Ord a, Ord b) => b -> Bimap a b -> Bimap a bSource
O(log n) A version of delete
specialized to the right key.
Version: 0.2
Conversion/traversal
fromList :: (Ord a, Ord b) => [(a, b)] -> Bimap a bSource
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
toAscList :: Bimap a b -> [(a, b)]Source
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
toAscListR :: Bimap a b -> [(b, a)]Source
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
keys :: Bimap a b -> [a]Source
O(n). Return all left-hand keys in the bimap in ascending order.
Version: 0.2
keysR :: Bimap a b -> [b]Source
O(n). Return all right-hand keys in the bimap in ascending order.
Version: 0.2
assocs :: Bimap a b -> [(a, b)]Source
O(n). Return all associated pairs in the bimap, with the left-hand values in ascending order.
Version: 0.2
toMap :: Bimap a b -> Map a bSource
O(1). Extract only the left-to-right component of a bimap.
Version: 0.2.1
toMapR :: Bimap a b -> Map b aSource
O(1). Extract only the right-to-left component of a bimap.
Version: 0.2.1
Miscellaneous
valid :: (Ord a, Ord b) => Bimap a b -> BoolSource
O(n*log n). Test if the internal bimap structure is valid.
Version: 0.2