- data DMap k
- data DSum tag where
- data Key f where
- class GEq f => GCompare f where
- data GOrdering a b where
- (!) :: GCompare k => DMap k -> k v -> v
- (\\) :: GCompare k => DMap k -> DMap k -> DMap k
- null :: DMap k -> Bool
- size :: DMap k -> Int
- member :: GCompare k => k a -> DMap k -> Bool
- notMember :: GCompare k => k v -> DMap k -> Bool
- lookup :: GCompare k => k v -> DMap k -> Maybe v
- findWithDefault :: GCompare k => v -> k v -> DMap k -> v
- empty :: DMap k
- singleton :: k v -> v -> DMap k
- insert :: GCompare k => k v -> v -> DMap k -> DMap k
- insertWith :: GCompare k => (v -> v -> v) -> k v -> v -> DMap k -> DMap k
- insertWith' :: GCompare k => (v -> v -> v) -> k v -> v -> DMap k -> DMap k
- insertWithKey :: GCompare k => (k v -> v -> v -> v) -> k v -> v -> DMap k -> DMap k
- insertWithKey' :: GCompare k => (k v -> v -> v -> v) -> k v -> v -> DMap k -> DMap k
- insertLookupWithKey :: GCompare k => (k v -> v -> v -> v) -> k v -> v -> DMap k -> (Maybe v, DMap k)
- insertLookupWithKey' :: GCompare k => (k v -> v -> v -> v) -> k v -> v -> DMap k -> (Maybe v, DMap k)
- delete :: GCompare k => k v -> DMap k -> DMap k
- adjust :: GCompare k => (v -> v) -> k v -> DMap k -> DMap k
- adjustWithKey :: GCompare k => (k v -> v -> v) -> k v -> DMap k -> DMap k
- update :: GCompare k => (v -> Maybe v) -> k v -> DMap k -> DMap k
- updateWithKey :: GCompare k => (k v -> v -> Maybe v) -> k v -> DMap k -> DMap k
- updateLookupWithKey :: GCompare k => (k v -> v -> Maybe v) -> k v -> DMap k -> (Maybe v, DMap k)
- alter :: GCompare k => (Maybe v -> Maybe v) -> k v -> DMap k -> DMap k
- union :: GCompare k => DMap k -> DMap k -> DMap k
- unionWithKey :: GCompare k => (forall v. k v -> v -> v -> v) -> DMap k -> DMap k -> DMap k
- unions :: GCompare k => [DMap k] -> DMap k
- unionsWithKey :: GCompare k => (forall v. k v -> v -> v -> v) -> [DMap k] -> DMap k
- difference :: GCompare k => DMap k -> DMap k -> DMap k
- differenceWithKey :: GCompare k => (forall v. k v -> v -> v -> Maybe v) -> DMap k -> DMap k -> DMap k
- intersection :: GCompare k => DMap k -> DMap k -> DMap k
- intersectionWithKey :: GCompare k => (forall v. k v -> v -> v -> v) -> DMap k -> DMap k -> DMap k
- mapWithKey :: (forall v. k v -> v -> v) -> DMap k -> DMap k
- mapAccumLWithKey :: (forall v. a -> k v -> v -> (a, v)) -> a -> DMap k -> (a, DMap k)
- mapAccumRWithKey :: (forall v. a -> k v -> v -> (a, v)) -> a -> DMap k -> (a, DMap k)
- mapKeysWith :: GCompare k2 => (forall v. k2 v -> v -> v -> v) -> (forall v. k1 v -> k2 v) -> DMap k1 -> DMap k2
- mapKeysMonotonic :: (forall v. k1 v -> k2 v) -> DMap k1 -> DMap k2
- foldWithKey :: (forall v. k v -> v -> b -> b) -> b -> DMap k -> b
- foldrWithKey :: (forall v. k v -> v -> b -> b) -> b -> DMap k -> b
- foldlWithKey :: (forall v. b -> k v -> v -> b) -> b -> DMap k -> b
- keys :: DMap k -> [Key k]
- assocs :: DMap k -> [DSum k]
- toList :: DMap k -> [DSum k]
- fromList :: GCompare k => [DSum k] -> DMap k
- fromListWithKey :: GCompare k => (forall v. k v -> v -> v -> v) -> [DSum k] -> DMap k
- toAscList :: DMap k -> [DSum k]
- toDescList :: DMap k -> [DSum k]
- fromAscList :: GEq k => [DSum k] -> DMap k
- fromAscListWithKey :: GEq k => (forall v. k v -> v -> v -> v) -> [DSum k] -> DMap k
- fromDistinctAscList :: [DSum k] -> DMap k
- filter :: (a -> Bool) -> [a] -> [a]
- filterWithKey :: GCompare k => (forall v. k v -> v -> Bool) -> DMap k -> DMap k
- partitionWithKey :: GCompare k => (forall v. k v -> v -> Bool) -> DMap k -> (DMap k, DMap k)
- mapMaybeWithKey :: GCompare k => (forall v. k v -> v -> Maybe v) -> DMap k -> DMap k
- mapEitherWithKey :: GCompare k => (forall v. k v -> v -> Either v v) -> DMap k -> (DMap k, DMap k)
- split :: GCompare k => k v -> DMap k -> (DMap k, DMap k)
- splitLookup :: GCompare k => k v -> DMap k -> (DMap k, Maybe v, DMap k)
- isSubmapOf :: (GCompare k, EqTag k) => DMap k -> DMap k -> Bool
- isSubmapOfBy :: GCompare k => (forall v. k v -> k v -> v -> v -> Bool) -> DMap k -> DMap k -> Bool
- isProperSubmapOf :: (GCompare k, EqTag k) => DMap k -> DMap k -> Bool
- isProperSubmapOfBy :: GCompare k => (forall v. k v -> k v -> v -> v -> Bool) -> DMap k -> DMap k -> Bool
- lookupIndex :: GCompare k => k v -> DMap k -> Maybe Int
- findIndex :: GCompare k => k v -> DMap k -> Int
- elemAt :: Int -> DMap k -> DSum k
- updateAt :: (forall v. k v -> v -> Maybe v) -> Int -> DMap k -> DMap k
- deleteAt :: Int -> DMap k -> DMap k
- findMin :: DMap k -> DSum k
- findMax :: DMap k -> DSum k
- deleteMin :: DMap k -> DMap k
- deleteMax :: DMap k -> DMap k
- deleteFindMin :: DMap k -> (DSum k, DMap k)
- deleteFindMax :: DMap k -> (DSum k, DMap k)
- updateMinWithKey :: (forall v. k v -> v -> Maybe v) -> DMap k -> DMap k
- updateMaxWithKey :: (forall v. k v -> v -> Maybe v) -> DMap k -> DMap k
- minViewWithKey :: DMap k -> Maybe (DSum k, DMap k)
- maxViewWithKey :: DMap k -> Maybe (DSum k, DMap k)
- showTree :: ShowTag k => DMap k -> String
- showTreeWith :: (forall v. k v -> v -> String) -> Bool -> Bool -> DMap k -> String
- valid :: GCompare k => DMap k -> Bool

# Documentation

Dependent maps: f is a GADT-like thing with a facility for
rediscovering its type parameter, elements of which function as identifiers
tagged with the type of the thing they identify. Real GADTs are one
useful instantiation of `f`

, as are `Tag`

s from Data.Dependent.Tag.

Semantically,

is equivalent to a set of `DMap`

f

where no two
elements have the same tag.
`DSum`

f

More informally, `DMap`

is to dependent products as `M.Map`

is to `(->)`

.
Thus it could also be thought of as a partial (in the sense of "partial
function") dependent product.

data DSum tag where

A basic dependent sum type; the first component is a tag that specifies the type of the second; for example, think of a GADT such as:

data Tag a where AString :: Tag String AnInt :: Tag Int

Then, we have the following valid expressions of type `DSum Tag`

:

AString :=> "hello!" AnInt :=> 42

And we can write functions that consume `DSum Tag`

values by matching,
such as:

toString :: DSum Tag -> String toString (AString :=> str) = str toString (AnInt :=> int) = show int

By analogy to the (key => value) construction for dictionary entries in
many dynamic languages, we use (key :=> value) as the constructor for
dependent sums. The :=> operator has very low precedence and binds to
the right, so if the `Tag`

GADT is extended with an additional constructor
`Rec :: Tag (DSum Tag)`

, then `Rec :=> AnInt :=> 3 + 4`

is parsed as
would be expected (`Rec :=> (AnInt :=> (3 + 4))`

) and has type `DSum Tag`

.
Its precedence is just above that of `$`

, so `foo bar $ AString :=> eep`

is equivalent to `foo bar (AString :=> eep)`

.

class GEq f => GCompare f where

Type class for orderable GADT-like structures. When 2 things are equal,
must return a witness that their parameter types are equal as well (GEQ).
|Type class for comparable GADT-like structures. When 2 things are equal,
must return a witness that their parameter types are equal as well (`GEQ`

).

data GOrdering a b where

A type for the result of comparing GADT constructors; the type parameters of the GADT values being compared are included so that in the case where they are equal their parameter types can be unified.

# Operators

(!) :: GCompare k => DMap k -> k v -> vSource

*O(log n)*. Find the value at a key.
Calls `error`

when the element can not be found.

fromList [(5,'a'), (3,'b')] ! 1 Error: element not in the map fromList [(5,'a'), (3,'b')] ! 5 == 'a'

# Query

member :: GCompare k => k a -> DMap k -> BoolSource

*O(log n)*. Is the key a member of the map? See also `notMember`

.

notMember :: GCompare k => k v -> DMap k -> BoolSource

*O(log n)*. Is the key not a member of the map? See also `member`

.

findWithDefault :: GCompare k => v -> k v -> DMap k -> vSource

*O(log n)*. The expression `(`

returns
the value at key `findWithDefault`

def k map)`k`

or returns default value `def`

when the key is not in the map.

# Construction

singleton :: k v -> v -> DMap kSource

*O(1)*. A map with a single element.

singleton 1 'a' == fromList [(1, 'a')] size (singleton 1 'a') == 1

## Insertion

insert :: GCompare k => k v -> v -> DMap k -> DMap kSource

*O(log n)*. Insert a new key and value in the map.
If the key is already present in the map, the associated value is
replaced with the supplied value. `insert`

is equivalent to

.
`insertWith`

`const`

insertWith :: GCompare k => (v -> v -> v) -> k v -> v -> DMap k -> DMap kSource

*O(log n)*. Insert with a function, combining new value and old value.

will insert the entry `insertWith`

f key value mp`key :=> value`

into `mp`

if key does
not exist in the map. If the key does exist, the function will
insert the entry `key :=> f new_value old_value`

.

insertWith' :: GCompare k => (v -> v -> v) -> k v -> v -> DMap k -> DMap kSource

Same as `insertWith`

, but the combining function is applied strictly.
This is often the most desirable behavior.

insertWithKey :: GCompare k => (k v -> v -> v -> v) -> k v -> v -> DMap k -> DMap kSource

*O(log n)*. Insert with a function, combining key, new value and old value.

will insert the entry `insertWithKey`

f key value mp`key :=> value`

into `mp`

if key does
not exist in the map. If the key does exist, the function will
insert the entry `key :=> f key new_value old_value`

.
Note that the key passed to f is the same key passed to `insertWithKey`

.

insertWithKey' :: GCompare k => (k v -> v -> v -> v) -> k v -> v -> DMap k -> DMap kSource

Same as `insertWithKey`

, but the combining function is applied strictly.

insertLookupWithKey :: GCompare k => (k v -> v -> v -> v) -> k v -> v -> DMap k -> (Maybe v, DMap k)Source

*O(log n)*. Combines insert operation with old value retrieval.
The expression (

)
is a pair where the first element is equal to (`insertLookupWithKey`

f k x map

)
and the second element equal to (`lookup`

k map

).
`insertWithKey`

f k x map

insertLookupWithKey' :: GCompare k => (k v -> v -> v -> v) -> k v -> v -> DMap k -> (Maybe v, DMap k)Source

*O(log n)*. A strict version of `insertLookupWithKey`

.

## Delete/Update

delete :: GCompare k => k v -> DMap k -> DMap kSource

*O(log n)*. 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 :: GCompare k => (v -> v) -> k v -> DMap k -> DMap kSource

*O(log n)*. Update a value at a specific key with the result of the provided function.
When the key is not
a member of the map, the original map is returned.

adjustWithKey :: GCompare k => (k v -> v -> v) -> k v -> DMap k -> DMap kSource

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

updateWithKey :: GCompare k => (k v -> v -> Maybe v) -> k v -> DMap k -> DMap kSource

*O(log n)*. The expression (

) updates the
value `updateWithKey`

f k map`x`

at `k`

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

) is `Nothing`

,
the element is deleted. If it is (

), the key `Just`

y`k`

is bound
to the new value `y`

.

updateLookupWithKey :: GCompare k => (k v -> v -> Maybe v) -> k v -> DMap k -> (Maybe v, DMap k)Source

*O(log n)*. Lookup and update. See also `updateWithKey`

.
The function returns changed value, if it is updated.
Returns the original key value if the map entry is deleted.

# Combine

## Union

unionWithKey :: GCompare k => (forall v. k v -> v -> v -> v) -> DMap k -> DMap k -> DMap kSource

*O(n+m)*.
Union with a combining function. The implementation uses the efficient *hedge-union* algorithm.
Hedge-union is more efficient on (bigset ``union`

` smallset).

unionsWithKey :: GCompare k => (forall v. k v -> v -> v -> v) -> [DMap k] -> DMap kSource

The union of a list of maps, with a combining operation:
(

).
`unionsWithKey`

f == `foldl`

(`unionWithKey`

f) `empty`

## Difference

difference :: GCompare k => DMap k -> DMap k -> DMap kSource

*O(n+m)*. Difference of two maps.
Return elements of the first map not existing in the second map.
The implementation uses an efficient *hedge* algorithm comparable with *hedge-union*.

differenceWithKey :: GCompare k => (forall v. k v -> v -> v -> Maybe v) -> DMap k -> DMap k -> DMap kSource

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

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

y`y`

.
The implementation uses an efficient *hedge* algorithm comparable with *hedge-union*.

## Intersection

intersection :: GCompare k => DMap k -> DMap k -> DMap kSource

*O(n+m)*. Intersection of two maps.
Return data in the first map for the keys existing in both maps.
(

).
`intersection`

m1 m2 == `intersectionWith`

`const`

m1 m2

intersectionWithKey :: GCompare k => (forall v. k v -> v -> v -> v) -> DMap k -> DMap k -> DMap kSource

*O(n+m)*. Intersection with a combining function.
Intersection is more efficient on (bigset ``intersection`

` smallset).

# Traversal

## Map

mapWithKey :: (forall v. k v -> v -> v) -> DMap k -> DMap kSource

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

mapAccumLWithKey :: (forall v. a -> k v -> v -> (a, v)) -> a -> DMap k -> (a, DMap k)Source

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

threads an accumulating
argument throught the map in ascending order of keys.

mapAccumRWithKey :: (forall v. a -> k v -> v -> (a, v)) -> a -> DMap k -> (a, DMap k)Source

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

threads an accumulating
argument through the map in descending order of keys.

mapKeysWith :: GCompare k2 => (forall v. k2 v -> v -> v -> v) -> (forall v. k1 v -> k2 v) -> DMap k1 -> DMap k2Source

*O(n*log n)*.

is the map obtained by applying `mapKeysWith`

c f s`f`

to each key of `s`

.

The size of the result may be smaller if `f`

maps two or more distinct
keys to the same new key. In this case the associated values will be
combined using `c`

.

mapKeysMonotonic :: (forall v. k1 v -> k2 v) -> DMap k1 -> DMap k2Source

*O(n)*.

, but works only when `mapKeysMonotonic`

f s == `mapKeys`

f s`f`

is strictly monotonic.
That is, for any values `x`

and `y`

, if `x`

< `y`

then `f x`

< `f y`

.
*The precondition is not checked.*
Semi-formally, we have:

and [x < y ==> f x < f y | x <- ls, y <- ls] ==> mapKeysMonotonic f s == mapKeys f s where ls = keys s

This means that `f`

maps distinct original keys to distinct resulting keys.
This function has better performance than `mapKeys`

.

## Fold

foldWithKey :: (forall v. k v -> v -> b -> b) -> b -> DMap k -> bSource

*O(n)*. Fold the keys and values in the map, such that

.
`foldWithKey`

f z == `foldr`

(`uncurry`

f) z . `toAscList`

This is identical to `foldrWithKey`

, and you should use that one instead of
this one. This name is kept for backward compatibility.

foldrWithKey :: (forall v. k v -> v -> b -> b) -> b -> DMap k -> bSource

*O(n)*. Post-order fold. The function will be applied from the lowest
value to the highest.

foldlWithKey :: (forall v. b -> k v -> v -> b) -> b -> DMap k -> bSource

*O(n)*. Pre-order fold. The function will be applied from the highest
value to the lowest.

# Conversion

keys :: DMap k -> [Key k]Source

*O(n)*. Return all keys of the map in ascending order.

keys (fromList [(5,"a"), (3,"b")]) == [3,5] keys empty == []

assocs :: DMap k -> [DSum k]Source

*O(n)*. Return all key/value pairs in the map in ascending key order.

## Lists

fromList :: GCompare k => [DSum k] -> DMap kSource

*O(n*log n)*. Build a map from a list of key/value pairs. See also `fromAscList`

.
If the list contains more than one value for the same key, the last value
for the key is retained.

fromListWithKey :: GCompare k => (forall v. k v -> v -> v -> v) -> [DSum k] -> DMap kSource

*O(n*log n)*. Build a map from a list of key/value pairs with a combining function. See also `fromAscListWithKey`

.

## Ordered lists

toDescList :: DMap k -> [DSum k]Source

*O(n)*. Convert to a descending list.

fromAscList :: GEq k => [DSum k] -> DMap kSource

*O(n)*. Build a map from an ascending list in linear time.
*The precondition (input list is ascending) is not checked.*

fromAscListWithKey :: GEq k => (forall v. k v -> v -> v -> v) -> [DSum k] -> DMap kSource

*O(n)*. Build a map from an ascending list in linear time with a
combining function for equal keys.
*The precondition (input list is ascending) is not checked.*

fromDistinctAscList :: [DSum k] -> DMap kSource

*O(n)*. Build a map from an ascending list of distinct elements in linear time.
*The precondition is not checked.*

# Filter

filter :: (a -> Bool) -> [a] -> [a]

`filter`

, applied to a predicate and a list, returns the list of
those elements that satisfy the predicate; i.e.,

filter p xs = [ x | x <- xs, p x]

filterWithKey :: GCompare k => (forall v. k v -> v -> Bool) -> DMap k -> DMap kSource

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

partitionWithKey :: GCompare k => (forall v. k v -> v -> Bool) -> DMap k -> (DMap k, DMap k)Source

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

.

mapMaybeWithKey :: GCompare k => (forall v. k v -> v -> Maybe v) -> DMap k -> DMap kSource

*O(n)*. Map keys/values and collect the `Just`

results.

mapEitherWithKey :: GCompare k => (forall v. k v -> v -> Either v v) -> DMap k -> (DMap k, DMap k)Source

split :: GCompare k => k v -> DMap k -> (DMap k, DMap k)Source

*O(log n)*. The expression (

) is a pair `split`

k map`(map1,map2)`

where
the keys in `map1`

are smaller than `k`

and the keys in `map2`

larger than `k`

.
Any key equal to `k`

is found in neither `map1`

nor `map2`

.

splitLookup :: GCompare k => k v -> DMap k -> (DMap k, Maybe v, DMap k)Source

*O(log n)*. The expression (

) splits a map just
like `splitLookup`

k map`split`

but also returns

.
`lookup`

k map

# Submap

isSubmapOf :: (GCompare k, EqTag k) => DMap k -> DMap k -> BoolSource

*O(n+m)*.
This function is defined as (

).
`isSubmapOf`

= `isSubmapOfBy`

`eqTagged`

)

isSubmapOfBy :: GCompare k => (forall v. k v -> k v -> v -> v -> Bool) -> DMap k -> DMap k -> BoolSource

*O(n+m)*.
The expression (

) returns `isSubmapOfBy`

f t1 t2`True`

if
all keys in `t1`

are in tree `t2`

, and when `f`

returns `True`

when
applied to their respective keys and values.

isProperSubmapOf :: (GCompare k, EqTag k) => DMap k -> DMap k -> BoolSource

*O(n+m)*. Is this a proper submap? (ie. a submap but not equal).
Defined as (

).
`isProperSubmapOf`

= `isProperSubmapOfBy`

`eqTagged`

isProperSubmapOfBy :: GCompare k => (forall v. k v -> k v -> v -> v -> Bool) -> DMap k -> DMap k -> BoolSource

*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 keys and values.

# Indexed

lookupIndex :: GCompare k => k v -> DMap k -> Maybe IntSource

*O(log n)*. Lookup the *index* of a key. The index is a number from
*0* up to, but not including, the `size`

of the map.

elemAt :: Int -> DMap k -> DSum kSource

*O(log n)*. Retrieve an element by *index*. Calls `error`

when an
invalid index is used.

updateAt :: (forall v. k v -> v -> Maybe v) -> Int -> DMap k -> DMap kSource

*O(log n)*. Update the element at *index*. Calls `error`

when an
invalid index is used.

# Min/Max

findMin :: DMap k -> DSum kSource

*O(log n)*. The minimal key of the map. Calls `error`

is the map is empty.

findMax :: DMap k -> DSum kSource

*O(log n)*. The maximal key of the map. Calls `error`

is the map is empty.

deleteMin :: DMap k -> DMap kSource

*O(log n)*. Delete the minimal key. Returns an empty map if the map is empty.

deleteMax :: DMap k -> DMap kSource

*O(log n)*. Delete the maximal key. Returns an empty map if the map is empty.

deleteFindMin :: DMap k -> (DSum k, DMap k)Source

*O(log n)*. Delete and find the minimal element.

deleteFindMin (fromList [(5,"a"), (3,"b"), (10,"c")]) == ((3,"b"), fromList[(5,"a"), (10,"c")]) deleteFindMin Error: can not return the minimal element of an empty map

deleteFindMax :: DMap k -> (DSum k, DMap k)Source

*O(log n)*. Delete and find the maximal element.

deleteFindMax (fromList [(5,"a"), (3,"b"), (10,"c")]) == ((10,"c"), fromList [(3,"b"), (5,"a")]) deleteFindMax empty Error: can not return the maximal element of an empty map

updateMinWithKey :: (forall v. k v -> v -> Maybe v) -> DMap k -> DMap kSource

*O(log n)*. Update the value at the minimal key.

updateMaxWithKey :: (forall v. k v -> v -> Maybe v) -> DMap k -> DMap kSource

*O(log n)*. Update the value at the maximal key.

minViewWithKey :: DMap k -> Maybe (DSum k, DMap k)Source

*O(log n)*. Retrieves the minimal (key :=> value) entry of the map, and
the map stripped of that element, or `Nothing`

if passed an empty map.

maxViewWithKey :: DMap k -> Maybe (DSum k, DMap k)Source

*O(log n)*. Retrieves the maximal (key :=> value) entry of the map, and
the map stripped of that element, or `Nothing`

if passed an empty map.

# Debugging

showTree :: ShowTag k => DMap k -> StringSource

*O(n)*. Show the tree that implements the map. The tree is shown
in a compressed, hanging format. See `showTreeWith`

.

showTreeWith :: (forall v. k v -> v -> String) -> Bool -> Bool -> DMap k -> StringSource

*O(n)*. The expression (

) shows
the tree that implements the map. Elements are shown using the `showTreeWith`

showelem hang wide map`showElem`

function. If `hang`

is
`True`

, a *hanging* tree is shown otherwise a rotated tree is shown. If
`wide`

is `True`

, an extra wide version is shown.