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*