Data.Map.Monoidal

A Map with monoidal accumulation

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

O(1). The number of elements in the map.

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

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

O(log n). The expression (findWithDefault def k map) returns the value at key k or returns default value def when the key is not in the map.

O(n). Return all elements of the map and their keys

O(n). Return all elements of the map in the ascending order of their keys. Subject to list fusion.

O(n). Return all keys of the map in ascending order. Subject to list fusion.

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.

O(n). mapKeysMonotonic f s == mapKeys f s, but works only when f is strictly increasing (both monotonic and injective). That is, for any values x and y, if x < y then f x < f y and f is injective (i.e. it never maps two input keys to the same output key). 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.

mapKeysMonotonic (\ k -> k * 2) (fromList [(5,"a"), (3,"b")]) == fromList [(6, "b"), (10, "a")]
valid (mapKeysMonotonic (\ k -> k * 2) (fromList [(5,"a"), (3,"b")])) == True
valid (mapKeysMonotonic (\ _ -> 1)     (fromList [(5,"a"), (3,"b")])) == False