1281f2fced5350ce25e27e11c2b70186c79d9d1d
[packages/containers.git] / Data / Map.hs
1 {-# LANGUAGE CPP #-}
2 #if !defined(TESTING) && __GLASGOW_HASKELL__ >= 703
3 {-# LANGUAGE Safe #-}
4 #endif
5
6 #include "containers.h"
7
8 -----------------------------------------------------------------------------
9 -- |
10 -- Module : Data.Map
11 -- Copyright : (c) Daan Leijen 2002
12 -- (c) Andriy Palamarchuk 2008
13 -- License : BSD-style
14 -- Maintainer : libraries@haskell.org
15 -- Stability : provisional
16 -- Portability : portable
17 --
18 -- /Note:/ You should use "Data.Map.Strict" instead of this module if:
19 --
20 -- * You will eventually need all the values stored.
21 --
22 -- * The stored values don't represent large virtual data structures
23 -- to be lazily computed.
24 --
25 -- An efficient implementation of ordered maps from keys to values
26 -- (dictionaries).
27 --
28 -- These modules are intended to be imported qualified, to avoid name
29 -- clashes with Prelude functions, e.g.
30 --
31 -- > import qualified Data.Map as Map
32 --
33 -- The implementation of 'Map' is based on /size balanced/ binary trees (or
34 -- trees of /bounded balance/) as described by:
35 --
36 -- * Stephen Adams, \"/Efficient sets: a balancing act/\",
37 -- Journal of Functional Programming 3(4):553-562, October 1993,
38 -- <http://www.swiss.ai.mit.edu/~adams/BB/>.
39 --
40 -- * J. Nievergelt and E.M. Reingold,
41 -- \"/Binary search trees of bounded balance/\",
42 -- SIAM journal of computing 2(1), March 1973.
43 --
44 -- Note that the implementation is /left-biased/ -- the elements of a
45 -- first argument are always preferred to the second, for example in
46 -- 'union' or 'insert'.
47 --
48 -- Operation comments contain the operation time complexity in
49 -- the Big-O notation (<http://en.wikipedia.org/wiki/Big_O_notation>).
50 -----------------------------------------------------------------------------
51
52 module Data.Map
53 ( module Data.Map.Lazy
54 , insertWith'
55 , insertWithKey'
56 , insertLookupWithKey'
57 , fold
58 , foldWithKey
59 ) where
60
61 import Prelude hiding (foldr)
62 import Data.Map.Lazy
63 import qualified Data.Map.Strict as Strict
64
65 -- | /Deprecated./ As of version 0.5, replaced by 'Data.Map.Strict.insertWith'.
66 --
67 -- /O(log n)/. Same as 'insertWith', but the value being inserted to the map is
68 -- evaluated to WHNF beforehand.
69 --
70 -- For example, to update a counter:
71 --
72 -- > insertWith' (+) k 1 m
73 --
74
75 insertWith' :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
76 insertWith' = Strict.insertWith
77 #if __GLASGOW_HASKELL__ >= 700
78 {-# INLINABLE insertWith' #-}
79 #else
80 {-# INLINE insertWith' #-}
81 #endif
82
83 -- | /Deprecated./ As of version 0.5, replaced by
84 -- 'Data.Map.Strict.insertWithKey'.
85 --
86 -- /O(log n)/. Same as 'insertWithKey', but the value being inserted to the map is
87 -- evaluated to WHNF beforehand.
88
89 insertWithKey' :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
90 -- We do not reuse Data.Map.Strict.insertWithKey, because it is stricter -- it
91 -- forces evaluation of the given value.
92 insertWithKey' = Strict.insertWithKey
93 #if __GLASGOW_HASKELL__ >= 700
94 {-# INLINABLE insertWithKey' #-}
95 #else
96 {-# INLINE insertWithKey' #-}
97 #endif
98
99 -- | /Deprecated./ As of version 0.5, replaced by
100 -- 'Data.Map.Strict.insertLookupWithKey'.
101 --
102 -- /O(log n)/. Same as 'insertLookupWithKey', but the value being inserted to
103 -- the map is evaluated to WHNF beforehand.
104
105 insertLookupWithKey' :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a
106 -> (Maybe a, Map k a)
107 -- We do not reuse Data.Map.Strict.insertLookupWithKey, because it is stricter -- it
108 -- forces evaluation of the given value.
109 insertLookupWithKey' = Strict.insertLookupWithKey
110 #if __GLASGOW_HASKELL__ >= 700
111 {-# INLINABLE insertLookupWithKey' #-}
112 #else
113 {-# INLINE insertLookupWithKey' #-}
114 #endif
115
116 -- | /Deprecated./ As of version 0.5, replaced by 'foldr'.
117 --
118 -- /O(n)/. Fold the values in the map using the given right-associative
119 -- binary operator. This function is an equivalent of 'foldr' and is present
120 -- for compatibility only.
121 fold :: (a -> b -> b) -> b -> Map k a -> b
122 fold = foldr
123 {-# INLINE fold #-}
124
125 -- | /Deprecated./ As of version 0.4, replaced by 'foldrWithKey'.
126 --
127 -- /O(n)/. Fold the keys and values in the map using the given right-associative
128 -- binary operator. This function is an equivalent of 'foldrWithKey' and is present
129 -- for compatibility only.
130 foldWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b
131 foldWithKey = foldrWithKey
132 {-# INLINE foldWithKey #-}