Data.Bimap

An implementation of bidirectional maps between values of two key types. A Bimap is essentially a bijection between subsets of its two argument types.

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.

Bimap type

data Bimap a b

A bidirectional map between values of types a and b.

Instances

(Eq a, Eq b) => Eq (Bimap a b)

(Show a, Show b) => Show (Bimap a b)

Query

null :: Bimap a b -> Bool

Is the bimap empty?

size :: Bimap a b -> Int

The number of elements in the bimap.

member :: (Ord a, Ord b) => a -> Bimap a b -> Bool

Is the specified value a member of the bimap?

memberR :: (Ord a, Ord b) => b -> Bimap a b -> Bool

A version of member specialized to the right key.

notMember :: (Ord a, Ord b) => a -> Bimap a b -> Bool

Is the specified value not a member of the bimap?

notMemberR :: (Ord a, Ord b) => b -> Bimap a b -> Bool

A version of notMember specialized to the right key.

pairMember :: (Ord a, Ord b) => (a, b) -> Bimap a b -> Bool

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.

pairNotMember :: (Ord a, Ord b) => (a, b) -> Bimap a b -> Bool

Are the two values not in the bimap, or not associated with each other? (Complement of pairMember.)

lookup :: (Ord a, Ord b, Monad m) => a -> Bimap a b -> m b

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.

lookupR :: (Ord a, Ord b, Monad m) => b -> Bimap a b -> m a

A version of lookup that is specialized to the right key, and returns only the left key.

(!) :: (Ord a, Ord b) => Bimap a b -> a -> b

Find the right key corresponding to a given left key. Calls error when the key is not in the bimap.

(!>) :: (Ord a, Ord b) => Bimap a b -> b -> a

A version of (!) that is specialized to the right key, and returns only the left key.

Construction

empty :: Bimap a b

The empty bimap.

singleton :: a -> b -> Bimap a b

A bimap with a single element.

Update

insert :: (Ord a, Ord b) => a -> b -> Bimap a b -> Bimap a b

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.

delete :: (Ord a, Ord b) => a -> Bimap a b -> Bimap a b

Delete a value and its twin from a bimap. When the value is not a member of the bimap, the original bimap is returned.

deleteR :: (Ord a, Ord b) => b -> Bimap a b -> Bimap a b

A version of delete specialized to the right key.

Conversion/traversal

fromList :: (Ord a, Ord b) => [(a, b)] -> Bimap a b

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.

toList :: Bimap a b -> [(a, b)]

Convert to a list of associated pairs.

toAscList :: Bimap a b -> [(a, b)]

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.

toAscListR :: Bimap a b -> [(b, a)]

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.

keys :: Bimap a b -> [a]

Return all left-hand keys in the bimap in ascending order.

keysR :: Bimap a b -> [b]

Return all right-hand keys in the bimap in ascending order.

elems :: Bimap a b -> [b]

An alias for keysR.

assocs :: Bimap a b -> [(a, b)]

Return all associated pairs in the bimap, with the left-hand values in ascending order.

fold :: (a -> b -> c -> c) -> c -> Bimap a b -> c

Fold the association pairs in the map, such that fold f z == foldr f z . assocs.

Miscellaneous

valid :: (Ord a, Ord b) => Bimap a b -> Bool

Test if the internal bimap structure is valid.

twist :: Bimap a b -> Bimap b a

Reverse the positions of the two element types in the bimap.

twisted :: (Bimap a b -> Bimap a b) -> Bimap b a -> Bimap b a

Reverse the positions of the two element types in a bimap transformation.