Copyright	(c) Daan Leijen 2002 (c) Andriy Palamarchuk 2008
License	BSD-style
Maintainer	[email protected]
Portability	portable
Safe Haskell	Trustworthy
Language	Haskell2010

Data.Map.Strict.Internal

Contents

Strictness properties
Map type
Operators
Query
Construction
- Insertion
- Delete/Update
Combine
Traversal
- Map
Folds
- Strict folds
Conversion
- Lists
- Ordered lists
Filter
Submap
Indexed
Min/Max
Debugging

Description

WARNING

This module is considered internal.

The Package Versioning Policy does not apply.

The contents of this module may change in any way whatsoever and without any warning between minor versions of this package.

Authors importing this module are expected to track development closely.

Description

An efficient implementation of ordered maps from keys to values (dictionaries).

API of this module is strict in both the keys and the values. If you need value-lazy maps, use Data.Map.Lazy instead. The Map type is shared between the lazy and strict modules, meaning that the same Map value can be passed to functions in both modules (although that is rarely needed).

These modules are intended to be imported qualified, to avoid name clashes with Prelude functions, e.g.

 import qualified Data.Map.Strict as Map

The implementation of Map is based on size balanced binary trees (or trees of bounded balance) as described by:

Stephen Adams, "Efficient sets: a balancing act", Journal of Functional Programming 3(4):553-562, October 1993, http://www.swiss.ai.mit.edu/~adams/BB/.
J. Nievergelt and E.M. Reingold, "Binary search trees of bounded balance", SIAM journal of computing 2(1), March 1973.

Bounds for union, intersection, and difference are as given by

Guy Blelloch, Daniel Ferizovic, and Yihan Sun, "Just Join for Parallel Ordered Sets", https://arxiv.org/abs/1602.02120v3.

Note that the implementation is left-biased -- the elements of a first argument are always preferred to the second, for example in union or insert.

Warning: The size of the map must not exceed maxBound::Int. Violation of this condition is not detected and if the size limit is exceeded, its behaviour is undefined.

Operation comments contain the operation time complexity in the Big-O notation (http://en.wikipedia.org/wiki/Big_O_notation).

Be aware that the Functor, Traversable and Data instances are the same as for the Data.Map.Lazy module, so if they are used on strict maps, the resulting maps will be lazy.

Synopsis

data Map k a
- = Bin !Size !k a !(Map k a) !(Map k a)
- | Tip
type Size = Int
(!) :: Ord k => Map k a -> k -> a
(!?) :: Ord k => Map k a -> k -> Maybe a
(\\) :: Ord k => Map k a -> Map k b -> Map k a
null :: Map k a -> Bool
size :: Map k a -> Int
member :: Ord k => k -> Map k a -> Bool
notMember :: Ord k => k -> Map k a -> Bool
lookup :: Ord k => k -> Map k a -> Maybe a
findWithDefault :: Ord k => a -> k -> Map k a -> a
lookupLT :: Ord k => k -> Map k v -> Maybe (k, v)
lookupGT :: Ord k => k -> Map k v -> Maybe (k, v)
lookupLE :: Ord k => k -> Map k v -> Maybe (k, v)
lookupGE :: Ord k => k -> Map k v -> Maybe (k, v)
empty :: Map k a
singleton :: k -> a -> Map k a
insert :: Ord k => k -> a -> Map k a -> Map k a
insertWith :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
insertWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
insertLookupWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a)
delete :: Ord k => k -> Map k a -> Map k a
adjust :: Ord k => (a -> a) -> k -> Map k a -> Map k a
adjustWithKey :: Ord k => (k -> a -> a) -> k -> Map k a -> Map k a
update :: Ord k => (a -> Maybe a) -> k -> Map k a -> Map k a
updateWithKey :: Ord k => (k -> a -> Maybe a) -> k -> Map k a -> Map k a
updateLookupWithKey :: Ord k => (k -> a -> Maybe a) -> k -> Map k a -> (Maybe a, Map k a)
alter :: Ord k => (Maybe a -> Maybe a) -> k -> Map k a -> Map k a
alterF :: (Functor f, Ord k) => (Maybe a -> f (Maybe a)) -> k -> Map k a -> f (Map k a)
union :: Ord k => Map k a -> Map k a -> Map k a
unionWith :: Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
unionWithKey :: Ord k => (k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
unions :: (Foldable f, Ord k) => f (Map k a) -> Map k a
unionsWith :: (Foldable f, Ord k) => (a -> a -> a) -> f (Map k a) -> Map k a
difference :: Ord k => Map k a -> Map k b -> Map k a
differenceWith :: Ord k => (a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
differenceWithKey :: Ord k => (k -> a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
intersection :: Ord k => Map k a -> Map k b -> Map k a
intersectionWith :: Ord k => (a -> b -> c) -> Map k a -> Map k b -> Map k c
intersectionWithKey :: Ord k => (k -> a -> b -> c) -> Map k a -> Map k b -> Map k c
disjoint :: Ord k => Map k a -> Map k b -> Bool
compose :: Ord b => Map b c -> Map a b -> Map a c
type SimpleWhenMissing = WhenMissing Identity
type SimpleWhenMatched = WhenMatched Identity
merge :: Ord k => SimpleWhenMissing k a c -> SimpleWhenMissing k b c -> SimpleWhenMatched k a b c -> Map k a -> Map k b -> Map k c
runWhenMatched :: WhenMatched f k x y z -> k -> x -> y -> f (Maybe z)
runWhenMissing :: WhenMissing f k x y -> k -> x -> f (Maybe y)
zipWithMaybeMatched :: Applicative f => (k -> x -> y -> Maybe z) -> WhenMatched f k x y z
zipWithMatched :: Applicative f => (k -> x -> y -> z) -> WhenMatched f k x y z
mapMaybeMissing :: Applicative f => (k -> x -> Maybe y) -> WhenMissing f k x y
dropMissing :: Applicative f => WhenMissing f k x y
preserveMissing :: Applicative f => WhenMissing f k x x
preserveMissing' :: Applicative f => WhenMissing f k x x
mapMissing :: Applicative f => (k -> x -> y) -> WhenMissing f k x y
filterMissing :: Applicative f => (k -> x -> Bool) -> WhenMissing f k x x
data WhenMissing f k x y = WhenMissing {
- missingSubtree :: Map k x -> f (Map k y)
- missingKey :: k -> x -> f (Maybe y)
}
newtype WhenMatched f k x y z = WhenMatched {
- matchedKey :: k -> x -> y -> f (Maybe z)
}
mergeA :: (Applicative f, Ord k) => WhenMissing f k a c -> WhenMissing f k b c -> WhenMatched f k a b c -> Map k a -> Map k b -> f (Map k c)
zipWithMaybeAMatched :: Applicative f => (k -> x -> y -> f (Maybe z)) -> WhenMatched f k x y z
zipWithAMatched :: Applicative f => (k -> x -> y -> f z) -> WhenMatched f k x y z
traverseMaybeMissing :: Applicative f => (k -> x -> f (Maybe y)) -> WhenMissing f k x y
traverseMissing :: Applicative f => (k -> x -> f y) -> WhenMissing f k x y
filterAMissing :: Applicative f => (k -> x -> f Bool) -> WhenMissing f k x x
mapWhenMissing :: Functor f => (a -> b) -> WhenMissing f k x a -> WhenMissing f k x b
mapWhenMatched :: Functor f => (a -> b) -> WhenMatched f k x y a -> WhenMatched f k x y b
mergeWithKey :: Ord k => (k -> a -> b -> Maybe c) -> (Map k a -> Map k c) -> (Map k b -> Map k c) -> Map k a -> Map k b -> Map k c
map :: (a -> b) -> Map k a -> Map k b
mapWithKey :: (k -> a -> b) -> Map k a -> Map k b
traverseWithKey :: Applicative t => (k -> a -> t b) -> Map k a -> t (Map k b)
traverseMaybeWithKey :: Applicative f => (k -> a -> f (Maybe b)) -> Map k a -> f (Map k b)
mapAccum :: (a -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
mapAccumWithKey :: (a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
mapAccumRWithKey :: (a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
mapKeys :: Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a
mapKeysWith :: Ord k2 => (a -> a -> a) -> (k1 -> k2) -> Map k1 a -> Map k2 a
mapKeysMonotonic :: (k1 -> k2) -> Map k1 a -> Map k2 a
foldr :: (a -> b -> b) -> b -> Map k a -> b
foldl :: (a -> b -> a) -> a -> Map k b -> a
foldrWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b
foldlWithKey :: (a -> k -> b -> a) -> a -> Map k b -> a
foldMapWithKey :: Monoid m => (k -> a -> m) -> Map k a -> m
foldr' :: (a -> b -> b) -> b -> Map k a -> b
foldl' :: (a -> b -> a) -> a -> Map k b -> a
foldrWithKey' :: (k -> a -> b -> b) -> b -> Map k a -> b
foldlWithKey' :: (a -> k -> b -> a) -> a -> Map k b -> a
elems :: Map k a -> [a]
keys :: Map k a -> [k]
assocs :: Map k a -> [(k, a)]
keysSet :: Map k a -> Set k
argSet :: Map k a -> Set (Arg k a)
fromSet :: (k -> a) -> Set k -> Map k a
fromArgSet :: Set (Arg k a) -> Map k a
toList :: Map k a -> [(k, a)]
fromList :: Ord k => [(k, a)] -> Map k a
fromListWith :: Ord k => (a -> a -> a) -> [(k, a)] -> Map k a
fromListWithKey :: Ord k => (k -> a -> a -> a) -> [(k, a)] -> Map k a
toAscList :: Map k a -> [(k, a)]
toDescList :: Map k a -> [(k, a)]
fromAscList :: Eq k => [(k, a)] -> Map k a
fromAscListWith :: Eq k => (a -> a -> a) -> [(k, a)] -> Map k a
fromAscListWithKey :: Eq k => (k -> a -> a -> a) -> [(k, a)] -> Map k a
fromDistinctAscList :: [(k, a)] -> Map k a
fromDescList :: Eq k => [(k, a)] -> Map k a
fromDescListWith :: Eq k => (a -> a -> a) -> [(k, a)] -> Map k a
fromDescListWithKey :: Eq k => (k -> a -> a -> a) -> [(k, a)] -> Map k a
fromDistinctDescList :: [(k, a)] -> Map k a
filter :: (a -> Bool) -> Map k a -> Map k a
filterWithKey :: (k -> a -> Bool) -> Map k a -> Map k a
restrictKeys :: Ord k => Map k a -> Set k -> Map k a
withoutKeys :: Ord k => Map k a -> Set k -> Map k a
partition :: (a -> Bool) -> Map k a -> (Map k a, Map k a)
partitionWithKey :: (k -> a -> Bool) -> Map k a -> (Map k a, Map k a)
takeWhileAntitone :: (k -> Bool) -> Map k a -> Map k a
dropWhileAntitone :: (k -> Bool) -> Map k a -> Map k a
spanAntitone :: (k -> Bool) -> Map k a -> (Map k a, Map k a)
mapMaybe :: (a -> Maybe b) -> Map k a -> Map k b
mapMaybeWithKey :: (k -> a -> Maybe b) -> Map k a -> Map k b
mapEither :: (a -> Either b c) -> Map k a -> (Map k b, Map k c)
mapEitherWithKey :: (k -> a -> Either b c) -> Map k a -> (Map k b, Map k c)
split :: Ord k => k -> Map k a -> (Map k a, Map k a)
splitLookup :: Ord k => k -> Map k a -> (Map k a, Maybe a, Map k a)
splitRoot :: Map k b -> [Map k b]
isSubmapOf :: (Ord k, Eq a) => Map k a -> Map k a -> Bool
isSubmapOfBy :: Ord k => (a -> b -> Bool) -> Map k a -> Map k b -> Bool
isProperSubmapOf :: (Ord k, Eq a) => Map k a -> Map k a -> Bool
isProperSubmapOfBy :: Ord k => (a -> b -> Bool) -> Map k a -> Map k b -> Bool
lookupIndex :: Ord k => k -> Map k a -> Maybe Int
findIndex :: Ord k => k -> Map k a -> Int
elemAt :: Int -> Map k a -> (k, a)
updateAt :: (k -> a -> Maybe a) -> Int -> Map k a -> Map k a
deleteAt :: Int -> Map k a -> Map k a
take :: Int -> Map k a -> Map k a
drop :: Int -> Map k a -> Map k a
splitAt :: Int -> Map k a -> (Map k a, Map k a)
lookupMin :: Map k a -> Maybe (k, a)
lookupMax :: Map k a -> Maybe (k, a)
findMin :: Map k a -> (k, a)
findMax :: Map k a -> (k, a)
deleteMin :: Map k a -> Map k a
deleteMax :: Map k a -> Map k a
deleteFindMin :: Map k a -> ((k, a), Map k a)
deleteFindMax :: Map k a -> ((k, a), Map k a)
updateMin :: (a -> Maybe a) -> Map k a -> Map k a
updateMax :: (a -> Maybe a) -> Map k a -> Map k a
updateMinWithKey :: (k -> a -> Maybe a) -> Map k a -> Map k a
updateMaxWithKey :: (k -> a -> Maybe a) -> Map k a -> Map k a
minView :: Map k a ->