Safe Haskell | None |
---|
- data IntBag
- type Key = Int
- (!) :: IntBag -> Key -> Int
- null :: IntBag -> Bool
- size :: IntBag -> Int
- empty :: IntBag
- singleton :: Key -> IntBag
- msingleton :: Key -> Int -> IntBag
- insert :: Key -> Int -> IntBag -> IntBag
- delete :: Key -> Int -> IntBag -> IntBag
- union :: IntBag -> IntBag -> IntBag
- fold :: (Int -> b -> b) -> b -> IntBag -> b
- foldWithKey :: (Key -> Int -> b -> b) -> b -> IntBag -> b
- assocs :: IntBag -> [(Key, Int)]
- toList :: IntBag -> [(Key, Int)]
- fromList :: [(Key, Int)] -> IntBag
- toAscList :: IntBag -> [(Key, Int)]
Map type
O(n+m). See difference
.
(\) :: IntBag -> IntBag -> IntBag
m1 \ m2 = difference m1 m2
A map of integers to values a
.
Operators
(!) :: IntBag -> Key -> IntSource
O(min(n,W)). Find the value at a key.
Calls error
when the element can not be found.
Query
Construction
O(min(n,W)). The expression (
returns the value at key findWithDefault
def k map)k
or returns def
when the key is not an
element of the map.
findWithDefault :: Int -> Key -> IntBag -> Int
findWithDefault def k m
= case lookup k m of
Nothing -> def
Just x -> x
O(1). The empty map.
msingleton :: Key -> Int -> IntBagSource
Insertion
Delete/Update
delete :: Key -> Int -> IntBag -> IntBagSource
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.
Combine
Union
union :: IntBag -> IntBag -> IntBagSource
The union of a list of maps, with a combining operation unionsWith :: (Int->Int->Int) -> [IntBag] -> IntBag unionsWith f ts = foldlStrict (unionWith f) empty ts
O(n+m). The (left-biased) union of two maps.
It prefers the first map when duplicate keys are encountered,
i.e. (
).
union
== unionWith
const
Difference
Traversal
Map
Fold
fold :: (Int -> b -> b) -> b -> IntBag -> bSource
O(n+m). The union with a combining function. unionWith :: (a -> a -> a) -> IntMap a -> IntMap a -> IntMap a unionWith f m1 m2 = unionWithKey (k x y -> f x y) m1 m2
O(n+m). Is this a proper submap? (ie. a submap but not equal).
Defined as (
).
isProperSubmapOf :: Eq a => IntMap a -> IntMap a -> Bool
isProperSubmapOf m1 m2
= isProperSubmapOfBy (==) m1 m2
isProperSubmapOf
= isProperSubmapOfBy
(==)
O(n+m). Is this a proper submap? (ie. a submap but not equal).
The expression (
) returns isProperSubmapOfBy
f m1 m2True
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
:
isProperSubmapOfBy (==) (fromList [(1,1)]) (fromList [(1,1),(2,2)]) isProperSubmapOfBy (<=) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
But the following are all False
:
isProperSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1),(2,2)]) isProperSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1)]) isProperSubmapOfBy (<) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
O(n+m).
The expression (
) returns isSubmapOfBy
f m1 m2True
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
:
isSubmapOfBy (==) (fromList [(1,1)]) (fromList [(1,1),(2,2)]) isSubmapOfBy (<=) (fromList [(1,1)]) (fromList [(1,1),(2,2)]) isSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1),(2,2)])
But the following are all False
:
isSubmapOfBy (==) (fromList [(1,2)]) (fromList [(1,1),(2,2)]) isSubmapOfBy (<) (fromList [(1,1)]) (fromList [(1,1),(2,2)]) isSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1)])
O(n). Fold the values in the map, such that
.
For example,
fold
f z == foldr
f z . elems
elems map = fold (:) [] map
foldWithKey :: (Key -> Int -> b -> b) -> b -> IntBag -> bSource
O(n). Fold the keys and values in the map, such that
.
For example,
foldWithKey
f z == foldr
(uncurry
f) z . toAscList
keys map = foldWithKey (\k x ks -> k:ks) [] map
Conversion
assocs :: IntBag -> [(Key, Int)]Source
O(n). Return all elements of the map in the ascending order of their keys. elems :: IntMap a -> [a] elems m = foldWithKey (k x xs -> x:xs) [] m
O(n). Return all key/value pairs in the map in ascending key order.
Lists
Ordered lists
toAscList :: IntBag -> [(Key, Int)]Source
O(n). Convert the map to a list of key/value pairs where the keys are in ascending order.