Deprecate some functions in Data.Map
[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 -- * J. Nievergelt and E.M. Reingold,
40 -- \"/Binary search trees of bounded balance/\",
41 -- SIAM journal of computing 2(1), March 1973.
42 --
43 -- Bounds for 'union', 'intersection', and 'difference' are as given
44 -- by
45 --
46 -- * Guy Blelloch, Daniel Ferizovic, and Yihan Sun,
47 -- \"/Just Join for Parallel Ordered Sets/\",
48 -- <https://arxiv.org/abs/1602.02120v3>.
49 --
50 -- Note that the implementation is /left-biased/ -- the elements of a
51 -- first argument are always preferred to the second, for example in
52 -- 'union' or 'insert'.
53 --
54 -- /Warning/: The size of the map must not exceed @maxBound::Int@. Violation of
55 -- this condition is not detected and if the size limit is exceeded, its
56 -- behaviour is undefined.
57 --
58 -- Operation comments contain the operation time complexity in
59 -- the Big-O notation (<http://en.wikipedia.org/wiki/Big_O_notation>).
60 -----------------------------------------------------------------------------
61
62 module Data.Map
63 ( module Data.Map.Lazy
64 , insertWith'
65 , insertWithKey'
66 , insertLookupWithKey'
67 , fold
68 , foldWithKey
69 ) where
70
71 import Prelude hiding (foldr)
72 import Data.Map.Lazy
73 import qualified Data.Map.Strict as Strict
74
75 -- | /O(log n)/. Same as 'insertWith', but the value being inserted to the map is
76 -- evaluated to WHNF beforehand.
77 --
78 -- For example, to update a counter:
79 --
80 -- > insertWith' (+) k 1 m
81 --
82 {-# DEPRECATED insertWith' "As of version 0.5, replaced by 'Data.Map.Strict.insertWith'." #-}
83 insertWith' :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
84 insertWith' = Strict.insertWith
85 #if __GLASGOW_HASKELL__
86 {-# INLINABLE insertWith' #-}
87 #else
88 {-# INLINE insertWith' #-}
89 #endif
90
91 -- | /O(log n)/. Same as 'insertWithKey', but the value being inserted to the map is
92 -- evaluated to WHNF beforehand.
93 {-# DEPRECATED insertWithKey' "As of version 0.5, replaced by 'Data.Map.Strict.insertWithKey'." #-}
94 insertWithKey' :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
95 -- We do not reuse Data.Map.Strict.insertWithKey, because it is stricter -- it
96 -- forces evaluation of the given value.
97 insertWithKey' = Strict.insertWithKey
98 #if __GLASGOW_HASKELL__
99 {-# INLINABLE insertWithKey' #-}
100 #else
101 {-# INLINE insertWithKey' #-}
102 #endif
103
104 -- | /O(log n)/. Same as 'insertLookupWithKey', but the value being inserted to
105 -- the map is evaluated to WHNF beforehand.
106 {-# DEPRECATED insertLookupWithKey' "As of version 0.5, replaced by 'Data.Map.Strict.insertLookupWithKey'." #-}
107 insertLookupWithKey' :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a
108 -> (Maybe a, Map k a)
109 -- We do not reuse Data.Map.Strict.insertLookupWithKey, because it is stricter -- it
110 -- forces evaluation of the given value.
111 insertLookupWithKey' = Strict.insertLookupWithKey
112 #if __GLASGOW_HASKELL__
113 {-# INLINABLE insertLookupWithKey' #-}
114 #else
115 {-# INLINE insertLookupWithKey' #-}
116 #endif
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 {-# DEPRECATED fold "As of version 0.5, replaced by 'foldr'." #-}
122 fold :: (a -> b -> b) -> b -> Map k a -> b
123 fold = foldr
124 {-# INLINE fold #-}
125
126 -- | /O(n)/. Fold the keys and values in the map using the given right-associative
127 -- binary operator. This function is an equivalent of 'foldrWithKey' and is present
128 -- for compatibility only.
129 {-# DEPRECATED foldWithKey "As of version 0.4, replaced by 'foldrWithKey'." #-}
130 foldWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b
131 foldWithKey = foldrWithKey
132 {-# INLINE foldWithKey #-}