Safe Haskell  None 

Language  Haskell98 
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 lefthand type is associated with an element of the righthand type, and viceversa, 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 lefthand type to be the
key, and the righthand type to be the value.
Functions with an
R
suffix reverse this convention, treating the
righthand type as the key and the lefthand type as the value.
Synopsis
 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, MonadThrow m) => a > Bimap a b > m b
 lookupR :: ( Ord a, Ord b, MonadThrow 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
 tryInsert :: ( Ord a, Ord b) => a > b > Bimap a b > Bimap a b
 adjust :: ( Ord a, Ord b) => (b > b) > a > Bimap a b > Bimap a b
 adjustR :: ( Ord a, Ord b) => (a > a) > b > Bimap a b > Bimap a b
 adjustWithKey :: ( Ord a, Ord b) => (a > b > b) > a > Bimap a b > Bimap a b
 adjustWithKeyR :: ( Ord a, Ord b) => (b > a > a) > b > Bimap a b > Bimap a b
 update :: ( Ord a, Ord b) => (b > Maybe b) > a > Bimap a b > Bimap a b
 updateR :: ( Ord a, Ord b) => (a > Maybe a) > b > Bimap a b > Bimap a b
 updateWithKey :: ( Ord a, Ord b) => (a > b > Maybe b) > a > Bimap a b > Bimap a b
 updateWithKeyR :: ( Ord a, Ord b) => (b > a > Maybe 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
 findMin :: Bimap a b > (a, b)
 findMinR :: Bimap a b > (b, a)
 findMax :: Bimap a b > (a, b)
 findMaxR :: Bimap a b > (b, a)
 deleteMin :: Ord b => Bimap a b > Bimap a b
 deleteMinR :: Ord a => Bimap a b > Bimap a b
 deleteMax :: Ord b => Bimap a b > Bimap a b
 deleteMaxR :: Ord a => Bimap a b > Bimap a b
 deleteFindMin :: Ord b => Bimap a b > ((a, b), Bimap a b)
 deleteFindMinR :: Ord a => Bimap a b > ((b, a), Bimap a b)
 deleteFindMax :: Ord b => Bimap a b > ((a, b), Bimap a b)
 deleteFindMaxR :: Ord a => Bimap a b > ((b, a), Bimap a b)
 filter :: ( Ord a, Ord b) => (a > b > Bool ) > Bimap a b > Bimap a b
 partition :: ( Ord a, Ord b) => (a > b > Bool ) > Bimap a b > ( Bimap a b, Bimap a b)
 fromList :: ( Ord a, Ord b) => [(a, b)] > Bimap a b
 fromAList :: ( Ord a, Ord b) => [(a, b)] > Bimap a b
 fromAscPairList :: ( Ord a, Ord b) => [(a, b)] > Bimap a b
 fromAscPairListUnchecked :: ( 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
 map :: Ord c => (a > c) > Bimap a b > Bimap c b
 mapR :: Ord c => (b > c) > Bimap a b > Bimap a c
 mapMonotonic :: (a > c) > Bimap a b > Bimap c b
 mapMonotonicR :: (b > c) > Bimap a b > Bimap a 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
.
Instances
( Ord a, Ord b) => IsList ( Bimap a b) Source #  
( Eq a, Eq b) => Eq ( Bimap a b) Source #  
( Ord a, Ord b) => Ord ( Bimap a b) Source #  
Defined in Data.Bimap 

( Show a, Show b) => Show ( Bimap a b) Source #  
Generic ( Bimap a b) Source #  
( NFData a, NFData b) => NFData ( Bimap a b) Source #  
Defined in Data.Bimap 

type Rep ( Bimap a b) Source #  
Defined in Data.Bimap
type
Rep
(
Bimap
a b) =
D1
('
MetaData
"Bimap" "Data.Bimap" "bimap0.4.0HC2xNK0GTetOiqZIhbekA" '
False
) (
C1
('
MetaCons
"MkBimap" '
PrefixI
'
False
) (
S1
('
MetaSel
('
Nothing
::
Maybe
Symbol
) '
NoSourceUnpackedness
'
SourceStrict
'
DecidedStrict
) (
Rec0
(
Map
a b))
:*:
S1
('
MetaSel
('
Nothing
::
Maybe
Symbol
) '
NoSourceUnpackedness
'
SourceStrict
'
DecidedStrict
) (
Rec0
(
Map
b a))))


type Item ( Bimap a b) Source #  
Defined in Data.Bimap 
Query
member :: ( Ord a, Ord b) => a > Bimap a b > Bool Source #
O(log n) . Is the specified value a member of the bimap? Version: 0.2
memberR :: ( Ord a, Ord b) => b > Bimap a b > Bool Source #
O(log n)
. A version of
member
specialized to the right key.
Version: 0.2
notMember :: ( Ord a, Ord b) => a > Bimap a b > Bool Source #
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 > Bool Source #
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 > Bool Source #
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 > Bool Source #
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, MonadThrow m) => a > Bimap a b > m b Source #
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, MonadThrow m) => b > Bimap a b > m a Source #
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 > b Source #
O(log n)
.
Find the right key corresponding to a given left key.
Calls
when the key is not in the bimap.
Version: 0.2
error
(!>) :: ( Ord a, Ord b) => Bimap a b > b > a Source #
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 b Source #
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
tryInsert :: ( Ord a, Ord b) => a > b > Bimap a b > Bimap a b Source #
O(log n) . Insert a pair of values into the bimap, but only if neither is already in the bimap. Version: 0.2.2
adjust :: ( Ord a, Ord b) => (b > b) > a > Bimap a b > Bimap a b Source #
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.
adjustR :: ( Ord a, Ord b) => (a > a) > b > Bimap a b > Bimap a b Source #
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.
adjustWithKey :: ( Ord a, Ord b) => (a > b > b) > a > Bimap a b > Bimap a b Source #
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.
adjustWithKeyR :: ( Ord a, Ord b) => (b > a > a) > b > Bimap a b > Bimap a b Source #
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.
updateWithKey :: ( Ord a, Ord b) => (a > b > Maybe b) > a > Bimap a b > Bimap a b Source #
O(log n)
.
The expression (
) updates the right value
updateWithKey
f a bimap
b
at
a
(if it is in the bimap).
If (
f a b
) is
Nothing
, the element is deleted.
If it is (
), the left key
Just
y
a
is bound to the new value
y
.
updateWithKeyR :: ( Ord a, Ord b) => (b > a > Maybe a) > b > Bimap a b > Bimap a b Source #
O(log n)
.
The expression (
) updates the left value
updateWithKeyR
f b bimap
a
at
b
(if it is in the bimap).
If (
f b a
) is
Nothing
, the element is deleted.
If it is (
), the right key
Just
x
b
is bound to the new value
x
.
delete :: ( Ord a, Ord b) => a > Bimap a b > Bimap a b Source #
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 b Source #
O(log n)
A version of
delete
specialized to the right key.
Version: 0.2
Min/Max
findMin :: Bimap a b > (a, b) Source #
O(log n)
.
Find the element with minimal left key.
Calls
if the bimap is empty.
Version: 0.2.2
error
findMinR :: Bimap a b > (b, a) Source #
O(log n)
.
Find the element with minimal right key. The
righthand key is the first entry in the pair.
Calls
if the bimap is empty.
Version: 0.2.2
error
findMax :: Bimap a b > (a, b) Source #
O(log n)
.
Find the element with maximal left key.
Calls
if the bimap is empty.
Version: 0.2.2
error
findMaxR :: Bimap a b > (b, a) Source #
O(log n)
.
Find the element with maximal right key. The
righthand key is the first entry in the pair.
Calls
if the bimap is empty.
Version: 0.2.2
error
deleteMin :: Ord b => Bimap a b > Bimap a b Source #
O(log n)
.
Delete the element with minimal left key.
Calls
if the bimap is empty.
Version: 0.2.2
error
deleteMinR :: Ord a => Bimap a b > Bimap a b Source #
O(log n)
.
Delete the element with minimal right key.
Calls
if the bimap is empty.
Version: 0.2.2
error
deleteMax :: Ord b => Bimap a b > Bimap a b Source #
O(log n)
.
Delete the element with maximal left key.
Calls
if the bimap is empty.
Version: 0.2.2
error
deleteMaxR :: Ord a => Bimap a b > Bimap a b Source #
O(log n)
.
Delete the element with maximal right key.
Calls
if the bimap is empty.
Version: 0.2.2
error
deleteFindMin :: Ord b => Bimap a b > ((a, b), Bimap a b) Source #
O(log n)
.
Delete and find the element with minimal left key.
Calls
if the bimap is empty.
Version: 0.2.2
error
deleteFindMinR :: Ord a => Bimap a b > ((b, a), Bimap a b) Source #
O(log n)
.
Delete and find the element with minimal right key.
Calls
if the bimap is empty.
Version: 0.2.2
error
deleteFindMax :: Ord b => Bimap a b > ((a, b), Bimap a b) Source #
O(log n)
.
Delete and find the element with maximal left key.
Calls
if the bimap is empty.
Version: 0.2.2
error
deleteFindMaxR :: Ord a => Bimap a b > ((b, a), Bimap a b) Source #
O(log n)
.
Delete and find the element with maximal right key.
Calls
if the bimap is empty.
Version: 0.2.2
error
Filter
filter :: ( Ord a, Ord b) => (a > b > Bool ) > Bimap a b > Bimap a b Source #
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
partition :: ( Ord a, Ord b) => (a > b > Bool ) > Bimap a b > ( Bimap a b, Bimap a b) Source #
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
Conversion/traversal
fromList :: ( Ord a, Ord b) => [(a, b)] > Bimap a b Source #
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
fromAList :: ( Ord a, Ord b) => [(a, b)] > Bimap a b Source #
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 Lispstyle 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
fromAscPairList :: ( Ord a, Ord b) => [(a, b)] > Bimap a b Source #
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
fromAscPairListUnchecked :: ( Ord a, Ord b) => [(a, b)] > Bimap a b Source #
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
toAscList :: Bimap a b > [(a, b)] Source #
O(n) . Convert to a list of associated pairs, with the lefthand 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 righthand 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 lefthand keys in the bimap in ascending order. Version: 0.2
keysR :: Bimap a b > [b] Source #
O(n) . Return all righthand 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 lefthand values in ascending order. Version: 0.2
map :: Ord c => (a > c) > Bimap a b > Bimap c b Source #
O(n*log n) Map a function over all the left keys in the map. Version 0.3
mapR :: Ord c => (b > c) > Bimap a b > Bimap a c Source #
O(n*log n) Map a function over all the right keys in the map. Version 0.3
mapMonotonic :: (a > c) > Bimap a b > Bimap c b Source #
O(n) . Map a strictly increasing function over all left keys in the map. The precondition is not checked. Version 0.3
mapMonotonicR :: (b > c) > Bimap a b > Bimap a c Source #
O(n) . Map a strictly increasing function over all right keys in the map. The precondition is not checked. Version 0.3
toMap :: Bimap a b > Map a b Source #
O(1) . Extract only the lefttoright component of a bimap. Version: 0.2.1
toMapR :: Bimap a b > Map b a Source #
O(1) . Extract only the righttoleft component of a bimap. Version: 0.2.1
Miscellaneous
valid :: ( Ord a, Ord b) => Bimap a b > Bool Source #
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