Constant-fold `__GLASGOW_HASKELL__` CPP conditionals
[ghc.git] / libraries / base / Data / Traversable.hs
1 {-# LANGUAGE Trustworthy #-}
2
3 -----------------------------------------------------------------------------
4 -- |
5 -- Module : Data.Traversable
6 -- Copyright : Conor McBride and Ross Paterson 2005
7 -- License : BSD-style (see the LICENSE file in the distribution)
8 --
9 -- Maintainer : libraries@haskell.org
10 -- Stability : experimental
11 -- Portability : portable
12 --
13 -- Class of data structures that can be traversed from left to right,
14 -- performing an action on each element.
15 --
16 -- See also
17 --
18 -- * \"Applicative Programming with Effects\",
19 -- by Conor McBride and Ross Paterson,
20 -- /Journal of Functional Programming/ 18:1 (2008) 1-13, online at
21 -- <http://www.soi.city.ac.uk/~ross/papers/Applicative.html>.
22 --
23 -- * \"The Essence of the Iterator Pattern\",
24 -- by Jeremy Gibbons and Bruno Oliveira,
25 -- in /Mathematically-Structured Functional Programming/, 2006, online at
26 -- <http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/#iterator>.
27 --
28 -- * \"An Investigation of the Laws of Traversals\",
29 -- by Mauro Jaskelioff and Ondrej Rypacek,
30 -- in /Mathematically-Structured Functional Programming/, 2012, online at
31 -- <http://arxiv.org/pdf/1202.2919>.
32 --
33 -- Note that the functions 'mapM' and 'sequence' generalize "Prelude"
34 -- functions of the same names from lists to any 'Traversable' functor.
35 -- To avoid ambiguity, either import the "Prelude" hiding these names
36 -- or qualify uses of these function names with an alias for this module.
37 --
38 -----------------------------------------------------------------------------
39
40 module Data.Traversable (
41 -- * The 'Traversable' class
42 Traversable(..),
43 -- * Utility functions
44 for,
45 forM,
46 mapAccumL,
47 mapAccumR,
48 -- * General definitions for superclass methods
49 fmapDefault,
50 foldMapDefault,
51 ) where
52
53 import Prelude hiding (mapM, sequence, foldr)
54 import qualified Prelude (mapM, foldr)
55 import Control.Applicative
56 import Data.Foldable (Foldable())
57 import Data.Monoid (Monoid)
58 import Data.Proxy
59
60 import GHC.Arr
61
62 -- | Functors representing data structures that can be traversed from
63 -- left to right.
64 --
65 -- Minimal complete definition: 'traverse' or 'sequenceA'.
66 --
67 -- A definition of 'traverse' must satisfy the following laws:
68 --
69 -- [/naturality/]
70 -- @t . 'traverse' f = 'traverse' (t . f)@
71 -- for every applicative transformation @t@
72 --
73 -- [/identity/]
74 -- @'traverse' Identity = Identity@
75 --
76 -- [/composition/]
77 -- @'traverse' (Compose . 'fmap' g . f) = Compose . 'fmap' ('traverse' g) . 'traverse' f@
78 --
79 -- A definition of 'sequenceA' must satisfy the following laws:
80 --
81 -- [/naturality/]
82 -- @t . 'sequenceA' = 'sequenceA' . 'fmap' t@
83 -- for every applicative transformation @t@
84 --
85 -- [/identity/]
86 -- @'sequenceA' . 'fmap' Identity = Identity@
87 --
88 -- [/composition/]
89 -- @'sequenceA' . 'fmap' Compose = Compose . 'fmap' 'sequenceA' . 'sequenceA'@
90 --
91 -- where an /applicative transformation/ is a function
92 --
93 -- @t :: (Applicative f, Applicative g) => f a -> g a@
94 --
95 -- preserving the 'Applicative' operations, i.e.
96 --
97 -- * @t ('pure' x) = 'pure' x@
98 --
99 -- * @t (x '<*>' y) = t x '<*>' t y@
100 --
101 -- and the identity functor @Identity@ and composition of functors @Compose@
102 -- are defined as
103 --
104 -- > newtype Identity a = Identity a
105 -- >
106 -- > instance Functor Identity where
107 -- > fmap f (Identity x) = Identity (f x)
108 -- >
109 -- > instance Applicative Indentity where
110 -- > pure x = Identity x
111 -- > Identity f <*> Identity x = Identity (f x)
112 -- >
113 -- > newtype Compose f g a = Compose (f (g a))
114 -- >
115 -- > instance (Functor f, Functor g) => Functor (Compose f g) where
116 -- > fmap f (Compose x) = Compose (fmap (fmap f) x)
117 -- >
118 -- > instance (Applicative f, Applicative g) => Applicative (Compose f g) where
119 -- > pure x = Compose (pure (pure x))
120 -- > Compose f <*> Compose x = Compose ((<*>) <$> f <*> x)
121 --
122 -- (The naturality law is implied by parametricity.)
123 --
124 -- Instances are similar to 'Functor', e.g. given a data type
125 --
126 -- > data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)
127 --
128 -- a suitable instance would be
129 --
130 -- > instance Traversable Tree where
131 -- > traverse f Empty = pure Empty
132 -- > traverse f (Leaf x) = Leaf <$> f x
133 -- > traverse f (Node l k r) = Node <$> traverse f l <*> f k <*> traverse f r
134 --
135 -- This is suitable even for abstract types, as the laws for '<*>'
136 -- imply a form of associativity.
137 --
138 -- The superclass instances should satisfy the following:
139 --
140 -- * In the 'Functor' instance, 'fmap' should be equivalent to traversal
141 -- with the identity applicative functor ('fmapDefault').
142 --
143 -- * In the 'Foldable' instance, 'Data.Foldable.foldMap' should be
144 -- equivalent to traversal with a constant applicative functor
145 -- ('foldMapDefault').
146 --
147 class (Functor t, Foldable t) => Traversable t where
148 -- | Map each element of a structure to an action, evaluate
149 -- these actions from left to right, and collect the results.
150 traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
151 traverse f = sequenceA . fmap f
152
153 -- | Evaluate each action in the structure from left to right,
154 -- and collect the results.
155 sequenceA :: Applicative f => t (f a) -> f (t a)
156 sequenceA = traverse id
157
158 -- | Map each element of a structure to a monadic action, evaluate
159 -- these actions from left to right, and collect the results.
160 mapM :: Monad m => (a -> m b) -> t a -> m (t b)
161 mapM f = unwrapMonad . traverse (WrapMonad . f)
162
163 -- | Evaluate each monadic action in the structure from left to right,
164 -- and collect the results.
165 sequence :: Monad m => t (m a) -> m (t a)
166 sequence = mapM id
167
168 -- instances for Prelude types
169
170 instance Traversable Maybe where
171 traverse _ Nothing = pure Nothing
172 traverse f (Just x) = Just <$> f x
173
174 instance Traversable [] where
175 {-# INLINE traverse #-} -- so that traverse can fuse
176 traverse f = Prelude.foldr cons_f (pure [])
177 where cons_f x ys = (:) <$> f x <*> ys
178
179 mapM = Prelude.mapM
180
181 instance Traversable (Either a) where
182 traverse _ (Left x) = pure (Left x)
183 traverse f (Right y) = Right <$> f y
184
185 instance Traversable ((,) a) where
186 traverse f (x, y) = (,) x <$> f y
187
188 instance Ix i => Traversable (Array i) where
189 traverse f arr = listArray (bounds arr) `fmap` traverse f (elems arr)
190
191 instance Traversable Proxy where
192 traverse _ _ = pure Proxy
193 {-# INLINE traverse #-}
194 sequenceA _ = pure Proxy
195 {-# INLINE sequenceA #-}
196 mapM _ _ = return Proxy
197 {-# INLINE mapM #-}
198 sequence _ = return Proxy
199 {-# INLINE sequence #-}
200
201 -- general functions
202
203 -- | 'for' is 'traverse' with its arguments flipped.
204 for :: (Traversable t, Applicative f) => t a -> (a -> f b) -> f (t b)
205 {-# INLINE for #-}
206 for = flip traverse
207
208 -- | 'forM' is 'mapM' with its arguments flipped.
209 forM :: (Traversable t, Monad m) => t a -> (a -> m b) -> m (t b)
210 {-# INLINE forM #-}
211 forM = flip mapM
212
213 -- left-to-right state transformer
214 newtype StateL s a = StateL { runStateL :: s -> (s, a) }
215
216 instance Functor (StateL s) where
217 fmap f (StateL k) = StateL $ \ s -> let (s', v) = k s in (s', f v)
218
219 instance Applicative (StateL s) where
220 pure x = StateL (\ s -> (s, x))
221 StateL kf <*> StateL kv = StateL $ \ s ->
222 let (s', f) = kf s
223 (s'', v) = kv s'
224 in (s'', f v)
225
226 -- |The 'mapAccumL' function behaves like a combination of 'fmap'
227 -- and 'foldl'; it applies a function to each element of a structure,
228 -- passing an accumulating parameter from left to right, and returning
229 -- a final value of this accumulator together with the new structure.
230 mapAccumL :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c)
231 mapAccumL f s t = runStateL (traverse (StateL . flip f) t) s
232
233 -- right-to-left state transformer
234 newtype StateR s a = StateR { runStateR :: s -> (s, a) }
235
236 instance Functor (StateR s) where
237 fmap f (StateR k) = StateR $ \ s -> let (s', v) = k s in (s', f v)
238
239 instance Applicative (StateR s) where
240 pure x = StateR (\ s -> (s, x))
241 StateR kf <*> StateR kv = StateR $ \ s ->
242 let (s', v) = kv s
243 (s'', f) = kf s'
244 in (s'', f v)
245
246 -- |The 'mapAccumR' function behaves like a combination of 'fmap'
247 -- and 'foldr'; it applies a function to each element of a structure,
248 -- passing an accumulating parameter from right to left, and returning
249 -- a final value of this accumulator together with the new structure.
250 mapAccumR :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c)
251 mapAccumR f s t = runStateR (traverse (StateR . flip f) t) s
252
253 -- | This function may be used as a value for `fmap` in a `Functor`
254 -- instance, provided that 'traverse' is defined. (Using
255 -- `fmapDefault` with a `Traversable` instance defined only by
256 -- 'sequenceA' will result in infinite recursion.)
257 fmapDefault :: Traversable t => (a -> b) -> t a -> t b
258 {-# INLINE fmapDefault #-}
259 fmapDefault f = getId . traverse (Id . f)
260
261 -- | This function may be used as a value for `Data.Foldable.foldMap`
262 -- in a `Foldable` instance.
263 foldMapDefault :: (Traversable t, Monoid m) => (a -> m) -> t a -> m
264 foldMapDefault f = getConst . traverse (Const . f)
265
266 -- local instances
267
268 newtype Id a = Id { getId :: a }
269
270 instance Functor Id where
271 fmap f (Id x) = Id (f x)
272
273 instance Applicative Id where
274 pure = Id
275 Id f <*> Id x = Id (f x)
276