Map package:dependent-map

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

O(n). The function mapAccumLWithKey threads an accumulating argument through the map in ascending order of keys.

O(n). The function mapAccumRWithKey threads an accumulating argument through the map in descending order of keys.

O(n). Map keys/values and separate the Left and Right results.

O(n). mapKeysMonotonic f s == mapKeys f s, but works only when 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.

O(n*log n). mapKeysWith c f s is the map obtained by applying 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.

O(n). Map values and collect the Just results.

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

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

Dependent finite maps (partial dependent products) Provides a type called DMap which generalizes Data.Map.Map, allowing keys to specify the type of value that can be associated with them.

Dependent maps: k 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 k, as are Tags from Data.Unique.Tag in the 'prim-uniq' package. Semantically, DMap k f is equivalent to a set of DSum k f where no two elements have the same tag. More informally, DMap is to dependent products as Map is to (->). Thus it could also be thought of as a partial (in the sense of "partial function") dependent product.

O(n+m). Is this a proper submap? (ie. a submap but not equal). Defined as (isProperSubmapOf = isProperSubmapOfBy eqTagged).

O(n+m). Is this a proper submap? (ie. a submap but not equal). The expression (isProperSubmapOfBy 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 keys and values.

O(n+m). This function is defined as (isSubmapOf = isSubmapOfBy eqTagged)).

O(n+m). The expression (isSubmapOfBy f t1 t2) returns True if all keys in t1 are in tree t2, and when f returns True when applied to their respective keys and values.