Fold integer-gmp.git into ghc.git (re #8545)
[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 {-# MINIMAL traverse | sequenceA #-}
168
169 -- instances for Prelude types
170
171 instance Traversable Maybe where
172 traverse _ Nothing = pure Nothing
173 traverse f (Just x) = Just <$> f x
174
175 instance Traversable [] where
176 {-# INLINE traverse #-} -- so that traverse can fuse
177 traverse f = Prelude.foldr cons_f (pure [])
178 where cons_f x ys = (:) <$> f x <*> ys
179
180 mapM = Prelude.mapM
181
182 instance Traversable (Either a) where
183 traverse _ (Left x) = pure (Left x)
184 traverse f (Right y) = Right <$> f y
185
186 instance Traversable ((,) a) where
187 traverse f (x, y) = (,) x <$> f y
188
189 instance Ix i => Traversable (Array i) where
190 traverse f arr = listArray (bounds arr) `fmap` traverse f (elems arr)
191
192 instance Traversable Proxy where
193 traverse _ _ = pure Proxy
194 {-# INLINE traverse #-}
195 sequenceA _ = pure Proxy
196 {-# INLINE sequenceA #-}
197 mapM _ _ = return Proxy
198 {-# INLINE mapM #-}
199 sequence _ = return Proxy
200 {-# INLINE sequence #-}
201
202 instance Traversable (Const m) where
203 traverse _ (Const m) = pure $ Const m
204
205 -- general functions
206
207 -- | 'for' is 'traverse' with its arguments flipped.
208 for :: (Traversable t, Applicative f) => t a -> (a -> f b) -> f (t b)
209 {-# INLINE for #-}
210 for = flip traverse
211
212 -- | 'forM' is 'mapM' with its arguments flipped.
213 forM :: (Traversable t, Monad m) => t a -> (a -> m b) -> m (t b)
214 {-# INLINE forM #-}
215 forM = flip mapM
216
217 -- left-to-right state transformer
218 newtype StateL s a = StateL { runStateL :: s -> (s, a) }
219
220 instance Functor (StateL s) where
221 fmap f (StateL k) = StateL $ \ s -> let (s', v) = k s in (s', f v)
222
223 instance Applicative (StateL s) where
224 pure x = StateL (\ s -> (s, x))
225 StateL kf <*> StateL kv = StateL $ \ s ->
226 let (s', f) = kf s
227 (s'', v) = kv s'
228 in (s'', f v)
229
230 -- |The 'mapAccumL' function behaves like a combination of 'fmap'
231 -- and 'foldl'; it applies a function to each element of a structure,
232 -- passing an accumulating parameter from left to right, and returning
233 -- a final value of this accumulator together with the new structure.
234 mapAccumL :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c)
235 mapAccumL f s t = runStateL (traverse (StateL . flip f) t) s
236
237 -- right-to-left state transformer
238 newtype StateR s a = StateR { runStateR :: s -> (s, a) }
239
240 instance Functor (StateR s) where
241 fmap f (StateR k) = StateR $ \ s -> let (s', v) = k s in (s', f v)
242
243 instance Applicative (StateR s) where
244 pure x = StateR (\ s -> (s, x))
245 StateR kf <*> StateR kv = StateR $ \ s ->
246 let (s', v) = kv s
247 (s'', f) = kf s'
248 in (s'', f v)
249
250 -- |The 'mapAccumR' function behaves like a combination of 'fmap'
251 -- and 'foldr'; it applies a function to each element of a structure,
252 -- passing an accumulating parameter from right to left, and returning
253 -- a final value of this accumulator together with the new structure.
254 mapAccumR :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c)
255 mapAccumR f s t = runStateR (traverse (StateR . flip f) t) s
256
257 -- | This function may be used as a value for `fmap` in a `Functor`
258 -- instance, provided that 'traverse' is defined. (Using
259 -- `fmapDefault` with a `Traversable` instance defined only by
260 -- 'sequenceA' will result in infinite recursion.)
261 fmapDefault :: Traversable t => (a -> b) -> t a -> t b
262 {-# INLINE fmapDefault #-}
263 fmapDefault f = getId . traverse (Id . f)
264
265 -- | This function may be used as a value for `Data.Foldable.foldMap`
266 -- in a `Foldable` instance.
267 foldMapDefault :: (Traversable t, Monoid m) => (a -> m) -> t a -> m
268 foldMapDefault f = getConst . traverse (Const . f)
269
270 -- local instances
271
272 newtype Id a = Id { getId :: a }
273
274 instance Functor Id where
275 fmap f (Id x) = Id (f x)
276
277 instance Applicative Id where
278 pure = Id
279 Id f <*> Id x = Id (f x)
280