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

:

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

:

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.