Document the Semigroup for Map
[packages/containers.git] / Data / IntMap.hs
1 {-# LANGUAGE CPP #-}
2 #if !defined(TESTING) && defined(__GLASGOW_HASKELL__)
3 {-# LANGUAGE Safe #-}
4 #endif
5 #ifdef __GLASGOW_HASKELL__
6 {-# LANGUAGE DataKinds, FlexibleContexts #-}
7 #endif
8 #if __GLASGOW_HASKELL__ >= 800
9 {-# LANGUAGE MonoLocalBinds #-}
10 #endif
11
12 #include "containers.h"
13
14 -----------------------------------------------------------------------------
15 -- |
16 -- Module : Data.IntMap
17 -- Copyright : (c) Daan Leijen 2002
18 -- (c) Andriy Palamarchuk 2008
19 -- License : BSD-style
20 -- Maintainer : libraries@haskell.org
21 -- Portability : portable
22 --
23 -- An efficient implementation of maps from integer keys to values
24 -- (dictionaries).
25 --
26 -- This module re-exports the value lazy "Data.IntMap.Lazy" API, plus
27 -- several deprecated value strict functions. Please note that these functions
28 -- have different strictness properties than those in "Data.IntMap.Strict":
29 -- they only evaluate the result of the combining function. For example, the
30 -- default value to 'insertWith'' is only evaluated if the combining function
31 -- is called and uses it.
32 --
33 -- These modules are intended to be imported qualified, to avoid name
34 -- clashes with Prelude functions, e.g.
35 --
36 -- > import Data.IntMap (IntMap)
37 -- > import qualified Data.IntMap as IntMap
38 --
39 -- The implementation is based on /big-endian patricia trees/. This data
40 -- structure performs especially well on binary operations like 'union'
41 -- and 'intersection'. However, my benchmarks show that it is also
42 -- (much) faster on insertions and deletions when compared to a generic
43 -- size-balanced map implementation (see "Data.Map").
44 --
45 -- * Chris Okasaki and Andy Gill, \"/Fast Mergeable Integer Maps/\",
46 -- Workshop on ML, September 1998, pages 77-86,
47 -- <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.5452>
48 --
49 -- * D.R. Morrison, \"/PATRICIA -- Practical Algorithm To Retrieve
50 -- Information Coded In Alphanumeric/\", Journal of the ACM, 15(4),
51 -- October 1968, pages 514-534.
52 --
53 -- Operation comments contain the operation time complexity in
54 -- the Big-O notation <http://en.wikipedia.org/wiki/Big_O_notation>.
55 -- Many operations have a worst-case complexity of /O(min(n,W))/.
56 -- This means that the operation can become linear in the number of
57 -- elements with a maximum of /W/ -- the number of bits in an 'Int'
58 -- (32 or 64).
59 -----------------------------------------------------------------------------
60
61 module Data.IntMap
62 ( module Data.IntMap.Lazy
63 #ifdef __GLASGOW_HASKELL__
64 -- For GHC, we disable these, pending removal. For anything else,
65 -- we just don't define them at all.
66 , insertWith'
67 , insertWithKey'
68 , fold
69 , foldWithKey
70 #endif
71 ) where
72
73 import Data.IntMap.Lazy
74
75 #ifdef __GLASGOW_HASKELL__
76 import Utils.Containers.Internal.TypeError
77
78 -- | This function is being removed and is no longer usable.
79 -- Use 'Data.IntMap.Strict.insertWith'
80 insertWith' :: Whoops "Data.IntMap.insertWith' is gone. Use Data.IntMap.Strict.insertWith."
81 => (a -> a -> a) -> Key -> a -> IntMap a -> IntMap a
82 insertWith' _ _ _ _ = undefined
83
84 -- | This function is being removed and is no longer usable.
85 -- Use 'Data.IntMap.Strict.insertWithKey'.
86 insertWithKey' :: Whoops "Data.IntMap.insertWithKey' is gone. Use Data.IntMap.Strict.insertWithKey."
87 => (Key -> a -> a -> a) -> Key -> a -> IntMap a -> IntMap a
88 insertWithKey' _ _ _ _ = undefined
89
90 -- | This function is being removed and is no longer usable.
91 -- Use 'Data.IntMap.Lazy.foldr'.
92 fold :: Whoops "Data.IntMap.fold' is gone. Use Data.IntMap.foldr or Prelude.foldr."
93 => (a -> b -> b) -> b -> IntMap a -> b
94 fold _ _ _ = undefined
95
96 -- | This function is being removed and is no longer usable.
97 -- Use 'foldrWithKey'.
98 foldWithKey :: Whoops "Data.IntMap.foldWithKey is gone. Use foldrWithKey."
99 => (Key -> a -> b -> b) -> b -> IntMap a -> b
100 foldWithKey _ _ _ = undefined
101 #endif