d21c4e1caf351da3def845cab5275954ae530d5d
[packages/containers.git] / Data / IntMap / Merge / Strict.hs
1 {-# LANGUAGE CPP #-}
2 {-# LANGUAGE BangPatterns #-}
3 #if __GLASGOW_HASKELL__
4 {-# LANGUAGE DeriveDataTypeable, StandaloneDeriving #-}
5 #endif
6 #if !defined(TESTING) && defined(__GLASGOW_HASKELL__)
7 {-# LANGUAGE Trustworthy #-}
8 #endif
9 #if __GLASGOW_HASKELL__ >= 708
10 {-# LANGUAGE RoleAnnotations #-}
11 {-# LANGUAGE TypeFamilies #-}
12 #define USE_MAGIC_PROXY 1
13 #endif
14
15 #if USE_MAGIC_PROXY
16 {-# LANGUAGE MagicHash #-}
17 #endif
18
19 #include "containers.h"
20
21 -----------------------------------------------------------------------------
22 -- |
23 -- Module : Data.IntMap.Merge.Strict
24 -- Copyright : (c) wren romano 2016
25 -- License : BSD-style
26 -- Maintainer : libraries@haskell.org
27 -- Portability : portable
28 --
29 -- This module defines an API for writing functions that merge two
30 -- maps. The key functions are 'merge' and 'mergeA'.
31 -- Each of these can be used with several different \"merge tactics\".
32 --
33 -- The 'merge' and 'mergeA' functions are shared by
34 -- the lazy and strict modules. Only the choice of merge tactics
35 -- determines strictness. If you use 'Data.Map.Merge.Strict.mapMissing'
36 -- from this module then the results will be forced before they are
37 -- inserted. If you use 'Data.Map.Merge.Lazy.mapMissing' from
38 -- "Data.Map.Merge.Lazy" then they will not.
39 --
40 -- == Efficiency note
41 --
42 -- The 'Control.Category.Category', 'Applicative', and 'Monad' instances for
43 -- 'WhenMissing' tactics are included because they are valid. However, they are
44 -- inefficient in many cases and should usually be avoided. The instances
45 -- for 'WhenMatched' tactics should not pose any major efficiency problems.
46 --
47 -- @since 0.5.9
48
49 module Data.IntMap.Merge.Strict (
50 -- ** Simple merge tactic types
51 SimpleWhenMissing
52 , SimpleWhenMatched
53
54 -- ** General combining function
55 , merge
56
57 -- *** @WhenMatched@ tactics
58 , zipWithMaybeMatched
59 , zipWithMatched
60
61 -- *** @WhenMissing@ tactics
62 , mapMaybeMissing
63 , dropMissing
64 , preserveMissing
65 , mapMissing
66 , filterMissing
67
68 -- ** Applicative merge tactic types
69 , WhenMissing
70 , WhenMatched
71
72 -- ** Applicative general combining function
73 , mergeA
74
75 -- *** @WhenMatched@ tactics
76 -- | The tactics described for 'merge' work for
77 -- 'mergeA' as well. Furthermore, the following
78 -- are available.
79 , zipWithMaybeAMatched
80 , zipWithAMatched
81
82 -- *** @WhenMissing@ tactics
83 -- | The tactics described for 'merge' work for
84 -- 'mergeA' as well. Furthermore, the following
85 -- are available.
86 , traverseMaybeMissing
87 , traverseMissing
88 , filterAMissing
89
90 -- ** Covariant maps for tactics
91 , mapWhenMissing
92 , mapWhenMatched
93
94 -- ** Miscellaneous functions on tactics
95
96 , runWhenMatched
97 , runWhenMissing
98 ) where
99
100 import Data.IntMap.Internal
101 ( SimpleWhenMissing
102 , SimpleWhenMatched
103 , merge
104 , dropMissing
105 , preserveMissing
106 , filterMissing
107 , WhenMissing (..)
108 , WhenMatched (..)
109 , mergeA
110 , filterAMissing
111 , runWhenMatched
112 , runWhenMissing
113 )
114 import Data.IntMap.Strict.Internal
115 #if !MIN_VERSION_base(4,8,0)
116 import Control.Applicative (Applicative (..), (<$>))
117 #endif
118 import Prelude hiding (filter, map, foldl, foldr)
119
120 -- | Map covariantly over a @'WhenMissing' f k x@.
121 mapWhenMissing :: Functor f => (a -> b) -> WhenMissing f x a -> WhenMissing f x b
122 mapWhenMissing f q = WhenMissing
123 { missingSubtree = fmap (map f) . missingSubtree q
124 , missingKey = \k x -> fmap (forceMaybe . fmap f) $ missingKey q k x}
125
126 -- | Map covariantly over a @'WhenMatched' f k x y@.
127 mapWhenMatched :: Functor f => (a -> b) -> WhenMatched f x y a -> WhenMatched f x y b
128 mapWhenMatched f q = WhenMatched
129 { matchedKey = \k x y -> fmap (forceMaybe . fmap f) $ runWhenMatched q k x y }
130
131 -- | When a key is found in both maps, apply a function to the
132 -- key and values and maybe use the result in the merged map.
133 --
134 -- @
135 -- zipWithMaybeMatched :: (k -> x -> y -> Maybe z)
136 -- -> SimpleWhenMatched k x y z
137 -- @
138 zipWithMaybeMatched :: Applicative f
139 => (Key -> x -> y -> Maybe z)
140 -> WhenMatched f x y z
141 zipWithMaybeMatched f = WhenMatched $
142 \k x y -> pure $! forceMaybe $! f k x y
143 {-# INLINE zipWithMaybeMatched #-}
144
145 -- | When a key is found in both maps, apply a function to the
146 -- key and values, perform the resulting action, and maybe use
147 -- the result in the merged map.
148 --
149 -- This is the fundamental 'WhenMatched' tactic.
150 zipWithMaybeAMatched :: Applicative f
151 => (Key -> x -> y -> f (Maybe z))
152 -> WhenMatched f x y z
153 zipWithMaybeAMatched f = WhenMatched $
154 \ k x y -> forceMaybe <$> f k x y
155 {-# INLINE zipWithMaybeAMatched #-}
156
157 -- | When a key is found in both maps, apply a function to the
158 -- key and values to produce an action and use its result in the merged map.
159 zipWithAMatched :: Applicative f
160 => (Key -> x -> y -> f z)
161 -> WhenMatched f x y z
162 zipWithAMatched f = WhenMatched $
163 \ k x y -> (Just $!) <$> f k x y
164 {-# INLINE zipWithAMatched #-}
165
166 -- | When a key is found in both maps, apply a function to the
167 -- key and values and use the result in the merged map.
168 --
169 -- @
170 -- zipWithMatched :: (k -> x -> y -> z)
171 -- -> SimpleWhenMatched k x y z
172 -- @
173 zipWithMatched :: Applicative f
174 => (Key -> x -> y -> z) -> WhenMatched f x y z
175 zipWithMatched f = WhenMatched $
176 \k x y -> pure $! Just $! f k x y
177 {-# INLINE zipWithMatched #-}
178
179 -- | Map over the entries whose keys are missing from the other map,
180 -- optionally removing some. This is the most powerful 'SimpleWhenMissing'
181 -- tactic, but others are usually more efficient.
182 --
183 -- @
184 -- mapMaybeMissing :: (k -> x -> Maybe y) -> SimpleWhenMissing k x y
185 -- @
186 --
187 -- prop> mapMaybeMissing f = traverseMaybeMissing (\k x -> pure (f k x))
188 --
189 -- but @mapMaybeMissing@ uses fewer unnecessary 'Applicative' operations.
190 mapMaybeMissing :: Applicative f => (Key -> x -> Maybe y) -> WhenMissing f x y
191 mapMaybeMissing f = WhenMissing
192 { missingSubtree = \m -> pure $! mapMaybeWithKey f m
193 , missingKey = \k x -> pure $! forceMaybe $! f k x }
194 {-# INLINE mapMaybeMissing #-}
195
196 -- | Map over the entries whose keys are missing from the other map.
197 --
198 -- @
199 -- mapMissing :: (k -> x -> y) -> SimpleWhenMissing k x y
200 -- @
201 --
202 -- prop> mapMissing f = mapMaybeMissing (\k x -> Just $ f k x)
203 --
204 -- but @mapMissing@ is somewhat faster.
205 mapMissing :: Applicative f => (Key -> x -> y) -> WhenMissing f x y
206 mapMissing f = WhenMissing
207 { missingSubtree = \m -> pure $! mapWithKey f m
208 , missingKey = \k x -> pure $! Just $! f k x }
209 {-# INLINE mapMissing #-}
210
211 -- | Traverse over the entries whose keys are missing from the other map,
212 -- optionally producing values to put in the result.
213 -- This is the most powerful 'WhenMissing' tactic, but others are usually
214 -- more efficient.
215 traverseMaybeMissing :: Applicative f
216 => (Key -> x -> f (Maybe y)) -> WhenMissing f x y
217 traverseMaybeMissing f = WhenMissing
218 { missingSubtree = traverseMaybeWithKey f
219 , missingKey = \k x -> forceMaybe <$> f k x }
220 {-# INLINE traverseMaybeMissing #-}
221
222 -- | Traverse over the entries whose keys are missing from the other map.
223 traverseMissing :: Applicative f
224 => (Key -> x -> f y) -> WhenMissing f x y
225 traverseMissing f = WhenMissing
226 { missingSubtree = traverseWithKey f
227 , missingKey = \k x -> (Just $!) <$> f k x }
228 {-# INLINE traverseMissing #-}
229
230 forceMaybe :: Maybe a -> Maybe a
231 forceMaybe Nothing = Nothing
232 forceMaybe m@(Just !_) = m
233 {-# INLINE forceMaybe #-}