map -opengl +containers
An efficient implementation of ordered maps from keys to values (dictionaries).
This module re-exports the value lazy Lazy API, plus several value strict functions from Strict.
These modules are intended to be imported qualified, to avoid name clashes with Prelude functions, e.g.
> import qualified Data.Map as Map
The implementation of Map is based on size balanced binary trees (or trees of bounded balance) as described by:
* Stephen Adams, "Efficient sets: a balancing act", Journal of Functional Programming 3(4):553-562, October 1993, http://www.swiss.ai.mit.edu/~adams/BB/.
* J. Nievergelt and E.M. Reingold, "Binary search trees of bounded balance", SIAM journal of computing 2(1), March 1973.
Note that the implementation is left-biased -- the elements of a first argument are always preferred to the second, for example in union or insert.
Operation comments contain the operation time complexity in the Big-O notation (http://en.wikipedia.org/wiki/Big_O_notation).
A Map from keys k to values a.
O(n*min(n,W)). map f s is the set obtained by applying f to each element of s.
It's worth noting that the size of the result may be smaller if, for some (x,y), x /= y && f x == f y
O(n). Map a function over all values in the map.
> map (++ "x") (fromList [(5,"a"), (3,"b")]) == fromList [(3, "bx"), (5, "ax")]
O(n). Map a function over all values in the map.
> map (++ "x") (fromList [(5,"a"), (3,"b")]) == fromList [(3, "bx"), (5, "ax")]
O(n*log n). map f s is the set obtained by applying f to each element of s.
It's worth noting that the size of the result may be smaller if, for some (x,y), x /= y && f x == f y
O(n). The function mapAccum threads an accumulating argument through the map in ascending order of keys.
> let f a b = (a ++ b, b ++ "X")
> mapAccum f "Everything: " (fromList [(5,"a"), (3,"b")]) == ("Everything: ba", fromList [(3, "bX"), (5, "aX")])
O(n). The function mapAccum threads an accumulating argument through the map in ascending order of keys.
> let f a b = (a ++ b, b ++ "X")
> mapAccum f "Everything: " (fromList [(5,"a"), (3,"b")]) == ("Everything: ba", fromList [(3, "bX"), (5, "aX")])
O(n). The function mapAccumR threads an accumulating argument through the map in descending order of keys.
O(n). The function mapAccumR threads an accumulating argument through the map in descending order of keys.
O(n). The function mapAccumWithKey threads an accumulating argument through the map in ascending order of keys.
> let f a k b = (a ++ " " ++ (show k) ++ "-" ++ b, b ++ "X")
> mapAccumWithKey f "Everything:" (fromList [(5,"a"), (3,"b")]) == ("Everything: 3-b 5-a", fromList [(3, "bX"), (5, "aX")])
O(n). The function mapAccumWithKey threads an accumulating argument through the map in ascending order of keys.
> let f a k b = (a ++ " " ++ (show k) ++ "-" ++ b, b ++ "X")
> mapAccumWithKey f "Everything:" (fromList [(5,"a"), (3,"b")]) == ("Everything: 3-b 5-a", fromList [(3, "bX"), (5, "aX")])
O(n). Map values and separate the Left and Right results.
> let f a = if a < "c" then Left a else Right a
> mapEither f (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
> == (fromList [(3,"b"), (5,"a")], fromList [(1,"x"), (7,"z")])
>
> mapEither (\ a -> Right a) (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
> == (empty, fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
O(n). Map values and separate the Left and Right results.
> let f a = if a < "c" then Left a else Right a
> mapEither f (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
> == (fromList [(3,"b"), (5,"a")], fromList [(1,"x"), (7,"z")])
>
> mapEither (\ a -> Right a) (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
> == (empty, fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
O(n). Map keys/values and separate the Left and Right results.
> let f k a = if k < 5 then Left (k * 2) else Right (a ++ a)
> mapEitherWithKey f (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
> == (fromList [(1,2), (3,6)], fromList [(5,"aa"), (7,"zz")])
>
> mapEitherWithKey (\_ a -> Right a) (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
> == (empty, fromList [(1,"x"), (3,"b"), (5,"a"), (7,"z")])
O(n). Map keys/values and separate the Left and Right results.
> let f k a = if k < 5 then Left (k * 2) else Right (a ++ a)
> mapEitherWithKey f (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
> == (fromList [(1,2), (3,6)], fromList [(5,"aa"), (7,"zz")])
>
> mapEitherWithKey (\_ a -> Right a) (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
> == (empty, fromList [(1,"x"), (3,"b"), (5,"a"), (7,"z")])
O(n*min(n,W)). mapKeys 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 value at the greatest of the original keys is retained.
> mapKeys (+ 1) (fromList [(5,"a"), (3,"b")]) == fromList [(4, "b"), (6, "a")]
> mapKeys (\ _ -> 1) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 1 "c"
> mapKeys (\ _ -> 3) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 3 "c"
O(n*log n). mapKeys 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 value at the greatest of the original keys is retained.
> mapKeys (+ 1) (fromList [(5,"a"), (3,"b")]) == fromList [(4, "b"), (6, "a")]
> mapKeys (\ _ -> 1) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 1 "c"
> mapKeys (\ _ -> 3) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 3 "c"
O(n*min(n,W)). 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
>
This means that f maps distinct original keys to distinct resulting keys. This function has slightly better performance than mapKeys.
> mapKeysMonotonic (\ k -> k * 2) (fromList [(5,"a"), (3,"b")]) == fromList [(6, "b"), (10, "a")]
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
>
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
Show more results