Change INLINE to INLINABLE on methods using Ord.
[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 value strict functions from 'Data.Map.Strict'.
20 --
21 -- These modules are intended to be imported qualified, to avoid name
22 -- clashes with Prelude functions, e.g.
23 --
24 -- > import qualified Data.Map as Map
25 --
26 -- The implementation of 'Map' is based on /size balanced/ binary trees (or
27 -- trees of /bounded balance/) as described by:
28 --
29 -- * Stephen Adams, \"/Efficient sets: a balancing act/\",
30 -- Journal of Functional Programming 3(4):553-562, October 1993,
31 -- <http://www.swiss.ai.mit.edu/~adams/BB/>.
32 --
33 -- * J. Nievergelt and E.M. Reingold,
34 -- \"/Binary search trees of bounded balance/\",
35 -- SIAM journal of computing 2(1), March 1973.
36 --
37 -- Note that the implementation is /left-biased/ -- the elements of a
38 -- first argument are always preferred to the second, for example in
39 -- 'union' or 'insert'.
40 --
41 -- Operation comments contain the operation time complexity in
42 -- the Big-O notation (<http://en.wikipedia.org/wiki/Big_O_notation>).
43 -----------------------------------------------------------------------------
44
45 module Data.Map
46 ( module Data.Map.Lazy
47 , insertWith'
48 , insertWithKey'
49 , insertLookupWithKey'
50 , fold
51 , foldWithKey
52 ) where
53
54 import Data.Map.Lazy
55 import qualified Data.Map.Lazy as L
56 import qualified Data.Map.Strict as S
57
58 -- | /Deprecated./ As of version 0.5, replaced by 'S.insertWith'.
59 --
60 -- /O(log n)/. Same as 'insertWith', but the combining function is
61 -- applied strictly. This is often the most desirable behavior.
62 --
63 -- For example, to update a counter:
64 --
65 -- > insertWith' (+) k 1 m
66 --
67 insertWith' :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
68 insertWith' = S.insertWith
69 {-# INLINABLE insertWith' #-}
70
71 -- | /Deprecated./ As of version 0.5, replaced by 'S.insertWithKey'.
72 --
73 -- /O(log n)/. Same as 'insertWithKey', but the combining function is
74 -- applied strictly.
75 insertWithKey' :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
76 insertWithKey' = S.insertWithKey
77 {-# INLINABLE insertWithKey' #-}
78
79 -- | /Deprecated./ As of version 0.5, replaced by
80 -- 'S.insertLookupWithKey'.
81 --
82 -- /O(log n)/. A strict version of 'insertLookupWithKey'.
83 insertLookupWithKey' :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a
84 -> (Maybe a, Map k a)
85 insertLookupWithKey' = S.insertLookupWithKey
86 {-# INLINABLE insertLookupWithKey' #-}
87
88 -- | /Deprecated./ As of version 0.5, replaced by 'L.foldr'.
89 --
90 -- /O(n)/. Fold the values in the map using the given right-associative
91 -- binary operator. This function is an equivalent of 'foldr' and is present
92 -- for compatibility only.
93 fold :: (a -> b -> b) -> b -> Map k a -> b
94 fold = L.foldr
95 {-# INLINE fold #-}
96
97 -- | /Deprecated./ As of version 0.4, replaced by 'L.foldrWithKey'.
98 --
99 -- /O(n)/. Fold the keys and values in the map using the given right-associative
100 -- binary operator. This function is an equivalent of 'foldrWithKey' and is present
101 -- for compatibility only.
102 foldWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b
103 foldWithKey = foldrWithKey
104 {-# INLINE foldWithKey #-}