bimap-0.5.0: Bidirectional mapping between two key types

Safe Haskell | Safe-Inferred
Language | Haskell98

Data.Bimap

Contents

- Bimap type
- Query
- Construction
- Update
- Min/Max
- Filter
- Conversion/traversal
- Miscellaneous

Description

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.

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
- (!?) :: (Ord a, Ord b, MonadThrow m) => Bimap a b -> a -> m b
- (!?>) :: (Ord a, Ord b, MonadThrow m) => Bimap a b -> b -> m 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

data Bimap a b Source #

A bidirectional map between values of types `a` and `b`.

#### Instances

Instances details

(NFData a, NFData b) => NFData (Bimap a b) Source # |
Instance details Defined in Data.Bimap Methods rnf :: Bimap a b -> () Source #
Generic (Bimap a b) Source # |

Instance details

Defined in Data.Bimap

Associated Types

type Rep (Bimap a b) |

Instance details

Defined in Data.Bimap

type Rep (Bimap a b) = D1 ('MetaData "Bimap" "Data.Bimap" "bimap-0.5.0-EwvZuywpnarHUSxDZq46bs" '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))))

Methods

from :: Bimap a b -> Rep (Bimap a b) x Source #

to :: Rep (Bimap a b) x -> Bimap a b Source #

(Ord a, Ord b) => IsList (Bimap a b) Source # |

Instance details

Defined in Data.Bimap

Associated Types

type Item (Bimap a b) |
Instance details Defined in Data.Bimap type Item (Bimap a b) = (a, b)

Methods

fromList :: [Item (Bimap a b)] -> Bimap a b Source #

fromListN :: Int -> [Item (Bimap a b)] -> Bimap a b Source #

toList :: Bimap a b -> [Item (Bimap a b)] Source #

(Show a, Show b) => Show (Bimap a b) Source # |
Instance details Defined in Data.Bimap Methods showsPrec :: Int -> Bimap a b -> ShowS Source # show :: Bimap a b -> String Source # showList :: [Bimap a b] -> ShowS Source #
(Eq a, Eq b) => Eq (Bimap a b) Source # |
Instance details Defined in Data.Bimap Methods (==) :: Bimap a b -> Bimap a b -> Bool Source # (/=) :: Bimap a b -> Bimap a b -> Bool Source #
(Ord a, Ord b) => Ord (Bimap a b) Source # |
Instance details Defined in Data.Bimap Methods compare :: Bimap a b -> Bimap a b -> Ordering Source # (<) :: Bimap a b -> Bimap a b -> Bool Source # (<=) :: Bimap a b -> Bimap a b -> Bool Source # (>) :: Bimap a b -> Bimap a b -> Bool Source # (>=) :: Bimap a b -> Bimap a b -> Bool Source # max :: Bimap a b -> Bimap a b -> Bimap a b Source # min :: Bimap a b -> Bimap a b -> Bimap a b Source #
type Rep (Bimap a b) Source # |

Instance details

Defined in Data.Bimap

type Rep (Bimap a b) = D1 ('MetaData "Bimap" "Data.Bimap" "bimap-0.5.0-EwvZuywpnarHUSxDZq46bs" '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 # |
Instance details Defined in Data.Bimap type Item (Bimap a b) = (a, b)

# Query

null :: Bimap a b -> Bool Source #

O(1). Is the bimap empty? Version: 0.2

size :: Bimap a b -> Int Source #

O(1). The number of elements in the bimap. Version: 0.2

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.

Note that the signature differs slightly from Data.Map's `lookup`. This one is more general - it functions the same way as the "original" if `m` is cast (or inferred) to Maybe.

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 ``error`` when the key is not in the bimap. Version: 0.2

(!>) :: (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

(!?) :: (Ord a, Ord b, MonadThrow m) => Bimap a b -> a -> m b Source #

O(log n). See `lookup`.

(!?>) :: (Ord a, Ord b, MonadThrow m) => Bimap a b -> b -> m a Source #

O(log n). See `lookupR`.

# Construction

empty :: Bimap a b Source #

O(1). The empty bimap. Version: 0.2

singleton :: a -> b -> Bimap a b Source #

O(1). A bimap with a single element. Version: 0.2

# 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.

update :: (Ord a, Ord b) => (b -> Maybe b) -> a -> Bimap a b -> Bimap a b Source #

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`.

updateR :: (Ord a, Ord b) => (a -> Maybe a) -> b -> Bimap a b -> Bimap a b Source #

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`.

updateWithKey :: (Ord a, Ord b) => (a -> b -> Maybe b) -> a -> Bimap a b -> Bimap a b Source #

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`.

updateWithKeyR :: (Ord a, Ord b) => (b -> a -> Maybe a) -> b -> Bimap a b -> Bimap a b Source #

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`.

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 ``error`` if the bimap is empty. Version: 0.2.2

findMinR :: Bimap a b -> (b, a) Source #

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

findMax :: Bimap a b -> (a, b) Source #

O(log n). Find the element with maximal left key. Calls ``error`` if the bimap is empty. Version: 0.2.2

findMaxR :: Bimap a b -> (b, a) Source #

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

deleteMin :: Ord b => Bimap a b -> Bimap a b Source #

O(log n). Delete the element with minimal left key. Calls ``error`` if the bimap is empty. Version: 0.2.2

deleteMinR :: Ord a => Bimap a b -> Bimap a b Source #

O(log n). Delete the element with minimal right key. Calls ``error`` if the bimap is empty. Version: 0.2.2

deleteMax :: Ord b => Bimap a b -> Bimap a b Source #

O(log n). Delete the element with maximal left key. Calls ``error`` if the bimap is empty. Version: 0.2.2

deleteMaxR :: Ord a => Bimap a b -> Bimap a b Source #

O(log n). Delete the element with maximal right key. Calls ``error`` if the bimap is empty. Version: 0.2.2

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 ``error`` if the bimap is empty. Version: 0.2.2

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 ``error`` if the bimap is empty. Version: 0.2.2

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 ``error`` if the bimap is empty. Version: 0.2.2

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 ``error`` if the bimap is empty. Version: 0.2.2

# 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 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

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

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

O(n). Convert to a list of associated pairs. 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

elems :: Bimap a b -> [b] Source #

O(n). An alias for `keysR`. 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

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

O(n). Fold the association pairs in the map, such that ``fold` f z == `foldr` f z . `assocs``. 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 left-to-right component of a bimap. Version: 0.2.1

toMapR :: Bimap a b -> Map b a Source #

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 -> 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

twist :: Bimap a b -> Bimap b a Source #

O(1). Reverse the positions of the two element types in the bimap. Version: 0.2

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

O(1). Reverse the positions of the two element types in a bimap transformation. Version: 0.2