RIO.Map.Unchecked

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. 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.

Warning: This function should be used only if f is monotonically strictly increasing. This precondition is not checked. Use mapKeys if the precondition may not hold.

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

O(n). Convert the map to a list of key/value pairs where the keys are in ascending order. Subject to list fusion.

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

O(n). Build a map from an ascending list in linear time.

Warning: This function should be used only if the keys are in non-decreasing order. This precondition is not checked. Use fromList if the precondition may not hold.

fromAscList [(3,"b"), (5,"a")]          == fromList [(3, "b"), (5, "a")]
fromAscList [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "b")]
valid (fromAscList [(3,"b"), (5,"a"), (5,"b")]) == True
valid (fromAscList [(5,"a"), (3,"b"), (5,"b")]) == False

O(n). Build a map from an ascending list in linear time with a combining function for equal keys.

Warning: This function should be used only if the keys are in non-decreasing order. This precondition is not checked. Use fromListWith if the precondition may not hold.

fromAscListWith (++) [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "ba")]
valid (fromAscListWith (++) [(3,"b"), (5,"a"), (5,"b")]) == True
valid (fromAscListWith (++) [(5,"a"), (3,"b"), (5,"b")]) == False

Also see the performance note on fromListWith.

O(n). Build a map from an ascending list in linear time with a combining function for equal keys.

Warning: This function should be used only if the keys are in non-decreasing order. This precondition is not checked. Use fromListWithKey if the precondition may not hold.

let f k a1 a2 = (show k) ++ ":" ++ a1 ++ a2
fromAscListWithKey f [(3,"b"), (5,"a"), (5,"b"), (5,"b")] == fromList [(3, "b"), (5, "5:b5:ba")]
valid (fromAscListWithKey f [(3,"b"), (5,"a"), (5,"b"), (5,"b")]) == True
valid (fromAscListWithKey f [(5,"a"), (3,"b"), (5,"b"), (5,"b")]) == False

Also see the performance note on fromListWith.

O(n). Build a map from an ascending list of distinct elements in linear time.

Warning: This function should be used only if the keys are in strictly increasing order. This precondition is not checked. Use fromList if the precondition may not hold.

fromDistinctAscList [(3,"b"), (5,"a")] == fromList [(3, "b"), (5, "a")]
valid (fromDistinctAscList [(3,"b"), (5,"a")])          == True
valid (fromDistinctAscList [(3,"b"), (5,"a"), (5,"b")]) == False

O(n). Convert the map to a list of key/value pairs where the keys are in descending order. Subject to list fusion.

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

O(n). Build a map from a descending list in linear time.

Warning: This function should be used only if the keys are in non-increasing order. This precondition is not checked. Use fromList if the precondition may not hold.

fromDescList [(5,"a"), (3,"b")]          == fromList [(3, "b"), (5, "a")]
fromDescList [(5,"a"), (5,"b"), (3,"a")] == fromList [(3, "b"), (5, "b")]
valid (fromDescList [(5,"a"), (5,"b"), (3,"b")]) == True
valid (fromDescList [(5,"a"), (3,"b"), (5,"b")]) == False

O(n). Build a map from a descending list in linear time with a combining function for equal keys.

Warning: This function should be used only if the keys are in non-increasing order. This precondition is not checked. Use fromListWith if the precondition may not hold.

fromDescListWith (++) [(5,"a"), (5,"b"), (3,"b")] == fromList [(3, "b"), (5, "ba")]
valid (fromDescListWith (++) [(5,"a"), (5,"b"), (3,"b")]) == True
valid (fromDescListWith (++) [(5,"a"), (3,"b"), (5,"b")]) == False

Also see the performance note on fromListWith.

O(n). Build a map from a descending list in linear time with a combining function for equal keys.

Warning: This function should be used only if the keys are in non-increasing order. This precondition is not checked. Use fromListWithKey if the precondition may not hold.

let f k a1 a2 = (show k) ++ ":" ++ a1 ++ a2
fromDescListWithKey f [(5,"a"), (5,"b"), (5,"b"), (3,"b")] == fromList [(3, "b"), (5, "5:b5:ba")]
valid (fromDescListWithKey f [(5,"a"), (5,"b"), (5,"b"), (3,"b")]) == True
valid (fromDescListWithKey f [(5,"a"), (3,"b"), (5,"b"), (5,"b")]) == False

Also see the performance note on fromListWith.

O(n). Build a map from a descending list of distinct elements in linear time.

Warning: This function should be used only if the keys are in strictly decreasing order. This precondition is not checked. Use fromList if the precondition may not hold.

fromDistinctDescList [(5,"a"), (3,"b")] == fromList [(3, "b"), (5, "a")]
valid (fromDistinctDescList [(5,"a"), (3,"b")])          == True
valid (fromDistinctDescList [(5,"a"), (3,"b"), (3,"a")]) == False