Make Data.{Bifoldable,Bitraversable} -XSafe
[ghc.git] / libraries / base / Data / Bitraversable.hs
1 {-# LANGUAGE Safe #-}
2
3 -----------------------------------------------------------------------------
4 -- |
5 -- Module : Data.Bitraversable
6 -- Copyright : (C) 2011-2016 Edward Kmett
7 -- License : BSD-style (see the file LICENSE)
8 --
9 -- Maintainer : libraries@haskell.org
10 -- Stability : provisional
11 -- Portability : portable
12 --
13 -- @since 4.10.0.0
14 ----------------------------------------------------------------------------
15 module Data.Bitraversable
16 ( Bitraversable(..)
17 , bisequenceA
18 , bisequence
19 , bimapM
20 , bifor
21 , biforM
22 , bimapAccumL
23 , bimapAccumR
24 , bimapDefault
25 , bifoldMapDefault
26 ) where
27
28 import Control.Applicative
29 import Data.Bifunctor
30 import Data.Bifoldable
31 import Data.Functor.Identity (Identity(..))
32 import Data.Functor.Utils (StateL(..), StateR(..))
33 import GHC.Generics (K1(..))
34
35 -- | 'Bitraversable' identifies bifunctorial data structures whose elements can
36 -- be traversed in order, performing 'Applicative' or 'Monad' actions at each
37 -- element, and collecting a result structure with the same shape.
38 --
39 -- As opposed to 'Traversable' data structures, which have one variety of
40 -- element on which an action can be performed, 'Bitraversable' data structures
41 -- have two such varieties of elements.
42 --
43 -- A definition of 'traverse' must satisfy the following laws:
44 --
45 -- [/naturality/]
46 -- @'bitraverse' (t . f) (t . g) ≡ t . 'bitraverse' f g@
47 -- for every applicative transformation @t@
48 --
49 -- [/identity/]
50 -- @'bitraverse' 'Identity' 'Identity' ≡ 'Identity'@
51 --
52 -- [/composition/]
53 -- @'Compose' . 'fmap' ('bitraverse' g1 g2) . 'bitraverse' f1 f2
54 -- ≡ 'traverse' ('Compose' . 'fmap' g1 . f1) ('Compose' . 'fmap' g2 . f2)@
55 --
56 -- where an /applicative transformation/ is a function
57 --
58 -- @t :: ('Applicative' f, 'Applicative' g) => f a -> g a@
59 --
60 -- preserving the 'Applicative' operations:
61 --
62 -- @
63 -- t ('pure' x) = 'pure' x
64 -- t (f '<*>' x) = t f '<*>' t x
65 -- @
66 --
67 -- and the identity functor 'Identity' and composition functors 'Compose' are
68 -- defined as
69 --
70 -- > newtype Identity a = Identity { runIdentity :: a }
71 -- >
72 -- > instance Functor Identity where
73 -- > fmap f (Identity x) = Identity (f x)
74 -- >
75 -- > instance Applicative Identity where
76 -- > pure = Identity
77 -- > Identity f <*> Identity x = Identity (f x)
78 -- >
79 -- > newtype Compose f g a = Compose (f (g a))
80 -- >
81 -- > instance (Functor f, Functor g) => Functor (Compose f g) where
82 -- > fmap f (Compose x) = Compose (fmap (fmap f) x)
83 -- >
84 -- > instance (Applicative f, Applicative g) => Applicative (Compose f g) where
85 -- > pure = Compose . pure . pure
86 -- > Compose f <*> Compose x = Compose ((<*>) <$> f <*> x)
87 --
88 -- Some simple examples are 'Either' and '(,)':
89 --
90 -- > instance Bitraversable Either where
91 -- > bitraverse f _ (Left x) = Left <$> f x
92 -- > bitraverse _ g (Right y) = Right <$> g y
93 -- >
94 -- > instance Bitraversable (,) where
95 -- > bitraverse f g (x, y) = (,) <$> f x <*> g y
96 --
97 -- 'Bitraversable' relates to its superclasses in the following ways:
98 --
99 -- @
100 -- 'bimap' f g ≡ 'runIdentity' . 'bitraverse' ('Identity' . f) ('Identity' . g)
101 -- 'bifoldMap' f g = 'getConst' . 'bitraverse' ('Const' . f) ('Const' . g)
102 -- @
103 --
104 -- These are available as 'bimapDefault' and 'bifoldMapDefault' respectively.
105 --
106 -- @since 4.10.0.0
107 class (Bifunctor t, Bifoldable t) => Bitraversable t where
108 -- | Evaluates the relevant functions at each element in the structure,
109 -- running the action, and builds a new structure with the same shape, using
110 -- the results produced from sequencing the actions.
111 --
112 -- @'bitraverse' f g ≡ 'bisequenceA' . 'bimap' f g@
113 --
114 -- For a version that ignores the results, see 'bitraverse_'.
115 --
116 -- @since 4.10.0.0
117 bitraverse :: Applicative f => (a -> f c) -> (b -> f d) -> t a b -> f (t c d)
118 bitraverse f g = bisequenceA . bimap f g
119
120 -- | Alias for 'bisequence'.
121 --
122 -- @since 4.10.0.0
123 bisequenceA :: (Bitraversable t, Applicative f) => t (f a) (f b) -> f (t a b)
124 bisequenceA = bisequence
125
126 -- | Alias for 'bitraverse'.
127 --
128 -- @since 4.10.0.0
129 bimapM :: (Bitraversable t, Applicative f)
130 => (a -> f c) -> (b -> f d) -> t a b -> f (t c d)
131 bimapM = bitraverse
132
133 -- | Sequences all the actions in a structure, building a new structure with
134 -- the same shape using the results of the actions. For a version that ignores
135 -- the results, see 'bisequence_'.
136 --
137 -- @'bisequence' ≡ 'bitraverse' 'id' 'id'@
138 --
139 -- @since 4.10.0.0
140 bisequence :: (Bitraversable t, Applicative f) => t (f a) (f b) -> f (t a b)
141 bisequence = bitraverse id id
142
143 -- | @since 4.10.0.0
144 instance Bitraversable (,) where
145 bitraverse f g ~(a, b) = (,) <$> f a <*> g b
146
147 -- | @since 4.10.0.0
148 instance Bitraversable ((,,) x) where
149 bitraverse f g ~(x, a, b) = (,,) x <$> f a <*> g b
150
151 -- | @since 4.10.0.0
152 instance Bitraversable ((,,,) x y) where
153 bitraverse f g ~(x, y, a, b) = (,,,) x y <$> f a <*> g b
154
155 -- | @since 4.10.0.0
156 instance Bitraversable ((,,,,) x y z) where
157 bitraverse f g ~(x, y, z, a, b) = (,,,,) x y z <$> f a <*> g b
158
159 -- | @since 4.10.0.0
160 instance Bitraversable ((,,,,,) x y z w) where
161 bitraverse f g ~(x, y, z, w, a, b) = (,,,,,) x y z w <$> f a <*> g b
162
163 -- | @since 4.10.0.0
164 instance Bitraversable ((,,,,,,) x y z w v) where
165 bitraverse f g ~(x, y, z, w, v, a, b) = (,,,,,,) x y z w v <$> f a <*> g b
166
167 -- | @since 4.10.0.0
168 instance Bitraversable Either where
169 bitraverse f _ (Left a) = Left <$> f a
170 bitraverse _ g (Right b) = Right <$> g b
171
172 -- | @since 4.10.0.0
173 instance Bitraversable Const where
174 bitraverse f _ (Const a) = Const <$> f a
175
176 -- | @since 4.10.0.0
177 instance Bitraversable (K1 i) where
178 bitraverse f _ (K1 c) = K1 <$> f c
179
180 -- | 'bifor' is 'bitraverse' with the structure as the first argument. For a
181 -- version that ignores the results, see 'bifor_'.
182 --
183 -- @since 4.10.0.0
184 bifor :: (Bitraversable t, Applicative f)
185 => t a b -> (a -> f c) -> (b -> f d) -> f (t c d)
186 bifor t f g = bitraverse f g t
187
188 -- | Alias for 'bifor'.
189 --
190 -- @since 4.10.0.0
191 biforM :: (Bitraversable t, Applicative f)
192 => t a b -> (a -> f c) -> (b -> f d) -> f (t c d)
193 biforM = bifor
194
195 -- | The 'bimapAccumL' function behaves like a combination of 'bimap' and
196 -- 'bifoldl'; it traverses a structure from left to right, threading a state
197 -- of type @a@ and using the given actions to compute new elements for the
198 -- structure.
199 --
200 -- @since 4.10.0.0
201 bimapAccumL :: Bitraversable t => (a -> b -> (a, c)) -> (a -> d -> (a, e))
202 -> a -> t b d -> (a, t c e)
203 bimapAccumL f g s t
204 = runStateL (bitraverse (StateL . flip f) (StateL . flip g) t) s
205
206 -- | The 'bimapAccumR' function behaves like a combination of 'bimap' and
207 -- 'bifoldl'; it traverses a structure from right to left, threading a state
208 -- of type @a@ and using the given actions to compute new elements for the
209 -- structure.
210 --
211 -- @since 4.10.0.0
212 bimapAccumR :: Bitraversable t => (a -> b -> (a, c)) -> (a -> d -> (a, e))
213 -> a -> t b d -> (a, t c e)
214 bimapAccumR f g s t
215 = runStateR (bitraverse (StateR . flip f) (StateR . flip g) t) s
216
217 -- | A default definition of 'bimap' in terms of the 'Bitraversable'
218 -- operations.
219 --
220 -- @since 4.10.0.0
221 bimapDefault :: Bitraversable t => (a -> b) -> (c -> d) -> t a c -> t b d
222 bimapDefault f g = runIdentity . bitraverse (Identity . f) (Identity . g)
223
224 -- | A default definition of 'bifoldMap' in terms of the 'Bitraversable'
225 -- operations.
226 --
227 -- @since 4.10.0.0
228 bifoldMapDefault :: (Bitraversable t, Monoid m)
229 => (a -> m) -> (b -> m) -> t a b -> m
230 bifoldMapDefault f g = getConst . bitraverse (Const . f) (Const . g)