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