- data IntMap a
- type Key = Int
- (!) :: IntMap a -> Key -> a
- (\\) :: IntMap a -> IntMap a -> IntMap a
- isEmpty :: IntMap a -> Bool
- size :: IntMap a -> Int
- member :: Key -> IntMap a -> Bool
- lookup :: Key -> IntMap a -> Maybe a
- find :: Key -> IntMap a -> a
- findWithDefault :: a -> Key -> IntMap a -> a
- empty :: IntMap a
- single :: Key -> a -> IntMap a
- insert :: Key -> a -> IntMap a -> IntMap a
- insertWith :: (a -> a -> a) -> Key -> a -> IntMap a -> IntMap a
- insertWithKey :: (Key -> a -> a -> a) -> Key -> a -> IntMap a -> IntMap a
- insertLookupWithKey :: (Key -> a -> a -> a) -> Key -> a -> IntMap a -> (Maybe a, IntMap a)
- delete :: Key -> IntMap a -> IntMap a
- adjust :: (a -> a) -> Key -> IntMap a -> IntMap a
- adjustWithKey :: (Key -> a -> a) -> Key -> IntMap a -> IntMap a
- update :: (a -> Maybe a) -> Key -> IntMap a -> IntMap a
- updateWithKey :: (Key -> a -> Maybe a) -> Key -> IntMap a -> IntMap a
- updateLookupWithKey :: (Key -> a -> Maybe a) -> Key -> IntMap a -> (Maybe a, IntMap a)
- union :: IntMap a -> IntMap a -> IntMap a
- unionWith :: (a -> a -> a) -> IntMap a -> IntMap a -> IntMap a
- unionWithKey :: (Key -> a -> a -> a) -> IntMap a -> IntMap a -> IntMap a
- unions :: [IntMap a] -> IntMap a
- difference :: IntMap a -> IntMap a -> IntMap a
- differenceWith :: (a -> a -> Maybe a) -> IntMap a -> IntMap a -> IntMap a
- differenceWithKey :: (Key -> a -> a -> Maybe a) -> IntMap a -> IntMap a -> IntMap a
- intersection :: IntMap a -> IntMap a -> IntMap a
- intersectionWith :: (a -> a -> a) -> IntMap a -> IntMap a -> IntMap a
- intersectionWithKey :: (Key -> a -> a -> a) -> IntMap a -> IntMap a -> IntMap a
- map :: (a -> b) -> IntMap a -> IntMap b
- mapWithKey :: (Key -> a -> b) -> IntMap a -> IntMap b
- mapAccum :: (a -> b -> (a, c)) -> a -> IntMap b -> (a, IntMap c)
- mapAccumWithKey :: (a -> Key -> b -> (a, c)) -> a -> IntMap b -> (a, IntMap c)
- fold :: (a -> b -> b) -> b -> IntMap a -> b
- foldWithKey :: (Key -> a -> b -> b) -> b -> IntMap a -> b
- elems :: IntMap a -> [a]
- keys :: IntMap a -> [Key]
- assocs :: IntMap a -> [(Key, a)]
- toList :: IntMap a -> [(Key, a)]
- fromList :: [(Key, a)] -> IntMap a
- fromListWith :: (a -> a -> a) -> [(Key, a)] -> IntMap a
- fromListWithKey :: (Key -> a -> a -> a) -> [(Key, a)] -> IntMap a
- toAscList :: IntMap a -> [(Key, a)]
- fromAscList :: [(Key, a)] -> IntMap a
- fromAscListWith :: (a -> a -> a) -> [(Key, a)] -> IntMap a
- fromAscListWithKey :: (Key -> a -> a -> a) -> [(Key, a)] -> IntMap a
- fromDistinctAscList :: [(Key, a)] -> IntMap a
- filter :: (a -> Bool) -> IntMap a -> IntMap a
- filterWithKey :: (Key -> a -> Bool) -> IntMap a -> IntMap a
- partition :: (a -> Bool) -> IntMap a -> (IntMap a, IntMap a)
- partitionWithKey :: (Key -> a -> Bool) -> IntMap a -> (IntMap a, IntMap a)
- split :: Key -> IntMap a -> (IntMap a, IntMap a)
- splitLookup :: Key -> IntMap a -> (Maybe a, IntMap a, IntMap a)
- subset :: Eq a => IntMap a -> IntMap a -> Bool
- subsetBy :: (a -> a -> Bool) -> IntMap a -> IntMap a -> Bool
- properSubset :: Eq a => IntMap a -> IntMap a -> Bool
- properSubsetBy :: (a -> a -> Bool) -> IntMap a -> IntMap a -> Bool
- showTree :: Show a => IntMap a -> String
- showTreeWith :: Show a => Bool -> Bool -> IntMap a -> String

# Map type

# Operators

# Query

find :: Key -> IntMap a -> aSource

*O(min(n,W))*. Find the value of a key. Calls `error`

when the element can not be found.

findWithDefault :: a -> Key -> IntMap a -> aSource

*O(min(n,W))*. The expression `(findWithDefault def k map)`

returns the value of key `k`

or returns `def`

when
the key is not an element of the map.

# Construction

## Insertion

insert :: Key -> a -> IntMap a -> IntMap aSource

*O(min(n,W))*. Insert a new key/value pair in the map. When the key
is already an element of the set, it's value is replaced by the new value,
ie. `insert`

is left-biased.

insertWith :: (a -> a -> a) -> Key -> a -> IntMap a -> IntMap aSource

*O(min(n,W))*. Insert with a combining function.

insertWithKey :: (Key -> a -> a -> a) -> Key -> a -> IntMap a -> IntMap aSource

*O(min(n,W))*. Insert with a combining function.

insertLookupWithKey :: (Key -> a -> a -> a) -> Key -> a -> IntMap a -> (Maybe a, IntMap a)Source

*O(min(n,W))*. The expression (`insertLookupWithKey f k x map`

) is a pair where
the first element is equal to (`lookup k map`

) and the second element
equal to (`insertWithKey f k x map`

).

## Delete/Update

delete :: Key -> IntMap a -> IntMap aSource

*O(min(n,W))*. Delete a key and its value from the map. When the key is not
a member of the map, the original map is returned.

adjust :: (a -> a) -> Key -> IntMap a -> IntMap aSource

*O(min(n,W))*. Adjust a value at a specific key. When the key is not
a member of the map, the original map is returned.

adjustWithKey :: (Key -> a -> a) -> Key -> IntMap a -> IntMap aSource

*O(min(n,W))*. Adjust a value at a specific key. When the key is not
a member of the map, the original map is returned.

update :: (a -> Maybe a) -> Key -> IntMap a -> IntMap aSource

*O(min(n,W))*. The expression (`update f k map`

) updates the value `x`

at `k`

(if it is in the map). If (`f x`

) is `Nothing`

, the element is
deleted. If it is (`Just y`

), the key `k`

is bound to the new value `y`

.

updateWithKey :: (Key -> a -> Maybe a) -> Key -> IntMap a -> IntMap aSource

*O(min(n,W))*. The expression (`update f k map`

) updates the value `x`

at `k`

(if it is in the map). If (`f k x`

) is `Nothing`

, the element is
deleted. If it is (`Just y`

), the key `k`

is bound to the new value `y`

.

updateLookupWithKey :: (Key -> a -> Maybe a) -> Key -> IntMap a -> (Maybe a, IntMap a)Source

*O(min(n,W))*. Lookup and update.

# Combine

## Union

unionWith :: (a -> a -> a) -> IntMap a -> IntMap a -> IntMap aSource

*O(n+m)*. The union with a combining function.

unionWithKey :: (Key -> a -> a -> a) -> IntMap a -> IntMap a -> IntMap aSource

*O(n+m)*. The union with a combining function.

## Difference

difference :: IntMap a -> IntMap a -> IntMap aSource

*O(n+m)*. Difference between two maps (based on keys).

differenceWith :: (a -> a -> Maybe a) -> IntMap a -> IntMap a -> IntMap aSource

*O(n+m)*. Difference with a combining function.

differenceWithKey :: (Key -> a -> a -> Maybe a) -> IntMap a -> IntMap a -> IntMap aSource

*O(n+m)*. Difference with a combining function. When two equal keys are
encountered, the combining function is applied to the key and both values.
If it returns `Nothing`

, the element is discarded (proper set difference). If
it returns (`Just y`

), the element is updated with a new value `y`

.

## Intersection

intersection :: IntMap a -> IntMap a -> IntMap aSource

*O(n+m)*. The (left-biased) intersection of two maps (based on keys).

intersectionWith :: (a -> a -> a) -> IntMap a -> IntMap a -> IntMap aSource

*O(n+m)*. The intersection with a combining function.

intersectionWithKey :: (Key -> a -> a -> a) -> IntMap a -> IntMap a -> IntMap aSource

*O(n+m)*. The intersection with a combining function.

# Traversal

## Map

mapWithKey :: (Key -> a -> b) -> IntMap a -> IntMap bSource

*O(n)*. Map a function over all values in the map.

mapAccum :: (a -> b -> (a, c)) -> a -> IntMap b -> (a, IntMap c)Source

*O(n)*. The function `mapAccum`

threads an accumulating
argument through the map in an unspecified order.

mapAccumWithKey :: (a -> Key -> b -> (a, c)) -> a -> IntMap b -> (a, IntMap c)Source

*O(n)*. The function `mapAccumWithKey`

threads an accumulating
argument through the map in an unspecified order.

## Fold

fold :: (a -> b -> b) -> b -> IntMap a -> bSource

*O(n)*. Fold over the elements of a map in an unspecified order.

sum map = fold (+) 0 map elems map = fold (:) [] map

foldWithKey :: (Key -> a -> b -> b) -> b -> IntMap a -> bSource

*O(n)*. Fold over the elements of a map in an unspecified order.

keys map = foldWithKey (\k x ks -> k:ks) [] map

# Conversion

## Lists

fromListWith :: (a -> a -> a) -> [(Key, a)] -> IntMap aSource

*O(n*min(n,W))*. Create a map from a list of key/value pairs with a combining function. See also `fromAscListWith`

.

fromListWithKey :: (Key -> a -> a -> a) -> [(Key, a)] -> IntMap aSource

*O(n*min(n,W))*. Build a map from a list of key/value pairs with a combining function. See also fromAscListWithKey'.

## Ordered lists

toAscList :: IntMap a -> [(Key, a)]Source

*O(n)*. Convert the map to a list of key/value pairs where the
keys are in ascending order.

fromAscList :: [(Key, a)] -> IntMap aSource

*O(n*min(n,W))*. Build a map from a list of key/value pairs where
the keys are in ascending order.

fromAscListWith :: (a -> a -> a) -> [(Key, a)] -> IntMap aSource

*O(n*min(n,W))*. Build a map from a list of key/value pairs where
the keys are in ascending order, with a combining function on equal keys.

fromAscListWithKey :: (Key -> a -> a -> a) -> [(Key, a)] -> IntMap aSource

*O(n*min(n,W))*. Build a map from a list of key/value pairs where
the keys are in ascending order, with a combining function on equal keys.

fromDistinctAscList :: [(Key, a)] -> IntMap aSource

*O(n*min(n,W))*. Build a map from a list of key/value pairs where
the keys are in ascending order and all distinct.

# Filter

filter :: (a -> Bool) -> IntMap a -> IntMap aSource

*O(n)*. Filter all values that satisfy some predicate.

filterWithKey :: (Key -> a -> Bool) -> IntMap a -> IntMap aSource

*O(n)*. Filter all keys/values that satisfy some predicate.

partition :: (a -> Bool) -> IntMap a -> (IntMap a, IntMap a)Source

*O(n)*. partition the map according to some predicate. The first
map contains all elements that satisfy the predicate, the second all
elements that fail the predicate. See also `split`

.

partitionWithKey :: (Key -> a -> Bool) -> IntMap a -> (IntMap a, IntMap a)Source

*O(n)*. partition the map according to some predicate. The first
map contains all elements that satisfy the predicate, the second all
elements that fail the predicate. See also `split`

.

split :: Key -> IntMap a -> (IntMap a, IntMap a)Source

*O(log n)*. The expression (`split k map`

) is a pair `(map1,map2)`

where all keys in `map1`

are lower than `k`

and all keys in
`map2`

larger than `k`

.

splitLookup :: Key -> IntMap a -> (Maybe a, IntMap a, IntMap a)Source

*O(log n)*. Performs a `split`

but also returns whether the pivot
key was found in the original map.

# Subset

subset :: Eq a => IntMap a -> IntMap a -> BoolSource

*O(n+m)*. Is this a subset? Defined as (`subset = subsetBy (==)`

).

subsetBy :: (a -> a -> Bool) -> IntMap a -> IntMap a -> BoolSource

*O(n+m)*.
The expression (`subsetBy f m1 m2`

) returns `True`

if
all keys in `m1`

are in `m2`

, and when `f`

returns `True`

when
applied to their respective values. For example, the following
expressions are all `True`

.

subsetBy (==) (fromList [(1,1)]) (fromList [(1,1),(2,2)]) subsetBy (<=) (fromList [(1,1)]) (fromList [(1,1),(2,2)]) subsetBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1),(2,2)])

But the following are all `False`

:

subsetBy (==) (fromList [(1,2)]) (fromList [(1,1),(2,2)]) subsetBy (<) (fromList [(1,1)]) (fromList [(1,1),(2,2)]) subsetBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1)])

properSubset :: Eq a => IntMap a -> IntMap a -> BoolSource

*O(n+m)*. Is this a proper subset? (ie. a subset but not equal).
Defined as (`properSubset = properSubsetBy (==)`

).

properSubsetBy :: (a -> a -> Bool) -> IntMap a -> IntMap a -> BoolSource

*O(n+m)*. Is this a proper subset? (ie. a subset but not equal).
The expression (`properSubsetBy f m1 m2`

) returns `True`

when
`m1`

and `m2`

are not equal,
all keys in `m1`

are in `m2`

, and when `f`

returns `True`

when
applied to their respective values. For example, the following
expressions are all `True`

.

properSubsetBy (==) (fromList [(1,1)]) (fromList [(1,1),(2,2)]) properSubsetBy (<=) (fromList [(1,1)]) (fromList [(1,1),(2,2)])

But the following are all `False`

:

properSubsetBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1),(2,2)]) properSubsetBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1)]) properSubsetBy (<) (fromList [(1,1)]) (fromList [(1,1),(2,2)])