Fix module references in the documentation.
[packages/containers.git] / Data / Map.hs
1 {-# LANGUAGE CPP #-}
2 #if !defined(TESTING) && __GLASGOW_HASKELL__ >= 703
3 {-# LANGUAGE Safe #-}
4 #endif
5 -----------------------------------------------------------------------------
6 -- |
7 -- Module : Data.Map
8 -- Copyright : (c) Daan Leijen 2002
9 -- (c) Andriy Palamarchuk 2008
10 -- License : BSD-style
11 -- Maintainer : libraries@haskell.org
12 -- Stability : provisional
13 -- Portability : portable
14 --
15 -- An efficient implementation of ordered maps from keys to values
16 -- (dictionaries).
17 --
18 -- This module re-exports the value lazy "Data.Map.Lazy" API, plus
19 -- several obsolete value strict functions. Please note that these functions
20 -- have different strictness properties than those in "Data.Map.Strict":
21 -- they only evaluate the values inserted into the map. For example, the
22 -- default value to 'insertWith'' is only evaluated if it's used, i.e. because
23 -- there's no value for the key already or because the higher-order argument
24 -- that combines the old and new value uses it.
25 --
26 -- These modules are intended to be imported qualified, to avoid name
27 -- clashes with Prelude functions, e.g.
28 --
29 -- > import qualified Data.Map as Map
30 --
31 -- The implementation of 'Map' is based on /size balanced/ binary trees (or
32 -- trees of /bounded balance/) as described by:
33 --
34 -- * Stephen Adams, \"/Efficient sets: a balancing act/\",
35 -- Journal of Functional Programming 3(4):553-562, October 1993,
36 -- <http://www.swiss.ai.mit.edu/~adams/BB/>.
37 --
38 -- * J. Nievergelt and E.M. Reingold,
39 -- \"/Binary search trees of bounded balance/\",
40 -- SIAM journal of computing 2(1), March 1973.
41 --
42 -- Note that the implementation is /left-biased/ -- the elements of a
43 -- first argument are always preferred to the second, for example in
44 -- 'union' or 'insert'.
45 --
46 -- Operation comments contain the operation time complexity in
47 -- the Big-O notation (<http://en.wikipedia.org/wiki/Big_O_notation>).
48 -----------------------------------------------------------------------------
49
50 module Data.Map
51 ( module Data.Map.Lazy
52 , insertWith'
53 , insertWithKey'
54 , insertLookupWithKey'
55 , fold
56 , foldWithKey
57 ) where
58
59 import Prelude hiding (foldr)
60 import Data.Map.Base (Map(..), balanceL, balanceR)
61 import Data.Map.Lazy
62 import Data.StrictPair
63
64 -- | /Deprecated./ As of version 0.5, replaced by 'Data.Map.Strict.insertWith'.
65 --
66 -- /O(log n)/. Same as 'insertWith', but the value being inserted to the map is
67 -- evaluated to WHNF beforehand. In contrast to 'Data.Map.Strict.insertWith',
68 -- the value argument is not evaluted when not needed.
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 -- We do not reuse Data.Map.Strict.insertWith, because it is stricter -- it
77 -- forces evaluation of the given value. Some people depend on the original
78 -- behaviour, which forces only the key and the result of combining function.
79 -- Particularly, people use insertWith' as a strict version of adjust, which
80 -- requires to use undefined in the place of the value.
81 insertWith' f = insertWithKey' (\_ x' y' -> f x' y')
82 #if __GLASGOW_HASKELL__ >= 700
83 {-# INLINABLE insertWith' #-}
84 #else
85 {-# INLINE insertWith' #-}
86 #endif
87
88 -- | /Deprecated./ As of version 0.5, replaced by
89 -- 'Data.Map.Strict.insertWithKey'.
90 --
91 -- /O(log n)/. Same as 'insertWithKey', but the value being inserted to the map is
92 -- evaluated to WHNF beforehand. In contrast to 'Data.Map.Strict.insertWithKey',
93 -- the value argument is not evaluted when not needed.
94
95 insertWithKey' :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
96 -- We do not reuse Data.Map.Strict.insertWithKey, because it is stricter -- it
97 -- forces evaluation of the given value.
98 insertWithKey' = go
99 where
100 go :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
101 go _ kx _ _ | kx `seq` False = undefined
102 go _ kx x Tip = x `seq` singleton kx x
103 go f kx x (Bin sy ky y l r) =
104 case compare kx ky of
105 LT -> balanceL ky y (go f kx x l) r
106 GT -> balanceR ky y l (go f kx x r)
107 EQ -> let x' = f kx x y
108 in x' `seq` Bin sy kx x' l r
109 #if __GLASGOW_HASKELL__ >= 700
110 {-# INLINABLE insertWithKey' #-}
111 #else
112 {-# INLINE insertWithKey' #-}
113 #endif
114
115 -- | /Deprecated./ As of version 0.5, replaced by
116 -- 'Data.Map.Strict.insertLookupWithKey'.
117 --
118 -- /O(log n)/. Same as 'insertLookupWithKey', but the value being inserted to
119 -- the map is evaluated to WHNF beforehand. In contrast to
120 -- 'Data.Map.Strict.insertLookupWithKey', the value argument is not evaluted
121 -- when not needed.
122
123 insertLookupWithKey' :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a
124 -> (Maybe a, Map k a)
125 -- We do not reuse Data.Map.Strict.insertLookupWithKey, because it is stricter -- it
126 -- forces evaluation of the given value.
127 insertLookupWithKey' f0 kx0 x0 t0 = toPair $ go f0 kx0 x0 t0
128 where
129 go :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> StrictPair (Maybe a) (Map k a)
130 go _ kx _ _ | kx `seq` False = undefined
131 go _ kx x Tip = x `seq` Nothing :*: singleton kx x
132 go f kx x (Bin sy ky y l r) =
133 case compare kx ky of
134 LT -> let (found :*: l') = go f kx x l
135 in found :*: balanceL ky y l' r
136 GT -> let (found :*: r') = go f kx x r
137 in found :*: balanceR ky y l r'
138 EQ -> let x' = f kx x y
139 in x' `seq` (Just y :*: Bin sy kx x' l r)
140 #if __GLASGOW_HASKELL__ >= 700
141 {-# INLINABLE insertLookupWithKey' #-}
142 #else
143 {-# INLINE insertLookupWithKey' #-}
144 #endif
145
146 -- | /Deprecated./ As of version 0.5, replaced by 'foldr'.
147 --
148 -- /O(n)/. Fold the values in the map using the given right-associative
149 -- binary operator. This function is an equivalent of 'foldr' and is present
150 -- for compatibility only.
151 fold :: (a -> b -> b) -> b -> Map k a -> b
152 fold = foldr
153 {-# INLINE fold #-}
154
155 -- | /Deprecated./ As of version 0.4, replaced by 'foldrWithKey'.
156 --
157 -- /O(n)/. Fold the keys and values in the map using the given right-associative
158 -- binary operator. This function is an equivalent of 'foldrWithKey' and is present
159 -- for compatibility only.
160 foldWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b
161 foldWithKey = foldrWithKey
162 {-# INLINE foldWithKey #-}