Add warning about Seq size.
[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 -- /Warning/: The size of the map must not exceed @maxBound::Int@. Violation of
49 -- this condition is not detected and if the size limit is exceeded, its
50 -- behaviour is undefined.
51 --
52 -- Operation comments contain the operation time complexity in
53 -- the Big-O notation (<http://en.wikipedia.org/wiki/Big_O_notation>).
54 -----------------------------------------------------------------------------
55
56 module Data.Map
57 ( module Data.Map.Lazy
58 , insertWith'
59 , insertWithKey'
60 , insertLookupWithKey'
61 , fold
62 , foldWithKey
63 ) where
64
65 import Prelude hiding (foldr)
66 import Data.Map.Lazy
67 import qualified Data.Map.Strict as Strict
68
69 -- | /Deprecated./ As of version 0.5, replaced by 'Data.Map.Strict.insertWith'.
70 --
71 -- /O(log n)/. Same as 'insertWith', but the value being inserted to the map is
72 -- evaluated to WHNF beforehand.
73 --
74 -- For example, to update a counter:
75 --
76 -- > insertWith' (+) k 1 m
77 --
78
79 insertWith' :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
80 insertWith' = Strict.insertWith
81 #if __GLASGOW_HASKELL__ >= 700
82 {-# INLINABLE insertWith' #-}
83 #else
84 {-# INLINE insertWith' #-}
85 #endif
86
87 -- | /Deprecated./ As of version 0.5, replaced by
88 -- 'Data.Map.Strict.insertWithKey'.
89 --
90 -- /O(log n)/. Same as 'insertWithKey', but the value being inserted to the map is
91 -- evaluated to WHNF beforehand.
92
93 insertWithKey' :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
94 -- We do not reuse Data.Map.Strict.insertWithKey, because it is stricter -- it
95 -- forces evaluation of the given value.
96 insertWithKey' = Strict.insertWithKey
97 #if __GLASGOW_HASKELL__ >= 700
98 {-# INLINABLE insertWithKey' #-}
99 #else
100 {-# INLINE insertWithKey' #-}
101 #endif
102
103 -- | /Deprecated./ As of version 0.5, replaced by
104 -- 'Data.Map.Strict.insertLookupWithKey'.
105 --
106 -- /O(log n)/. Same as 'insertLookupWithKey', but the value being inserted to
107 -- the map is evaluated to WHNF beforehand.
108
109 insertLookupWithKey' :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a
110 -> (Maybe a, Map k a)
111 -- We do not reuse Data.Map.Strict.insertLookupWithKey, because it is stricter -- it
112 -- forces evaluation of the given value.
113 insertLookupWithKey' = Strict.insertLookupWithKey
114 #if __GLASGOW_HASKELL__ >= 700
115 {-# INLINABLE insertLookupWithKey' #-}
116 #else
117 {-# INLINE insertLookupWithKey' #-}
118 #endif
119
120 -- | /Deprecated./ As of version 0.5, replaced by 'foldr'.
121 --
122 -- /O(n)/. Fold the values in the map using the given right-associative
123 -- binary operator. This function is an equivalent of 'foldr' and is present
124 -- for compatibility only.
125 fold :: (a -> b -> b) -> b -> Map k a -> b
126 fold = foldr
127 {-# INLINE fold #-}
128
129 -- | /Deprecated./ As of version 0.4, replaced by 'foldrWithKey'.
130 --
131 -- /O(n)/. Fold the keys and values in the map using the given right-associative
132 -- binary operator. This function is an equivalent of 'foldrWithKey' and is present
133 -- for compatibility only.
134 foldWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b
135 foldWithKey = foldrWithKey
136 {-# INLINE foldWithKey #-}