Eliminate Equality.hs-boot and Proxy.hs-boot by moving instances
[ghc.git] / libraries / base / Data / Traversable.hs
1 {-# LANGUAGE Trustworthy #-}
2 {-# LANGUAGE CPP #-}
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 -- Note that the functions 'mapM' and 'sequence' generalize "Prelude"
35 -- functions of the same names from lists to any 'Traversable' functor.
36 -- To avoid ambiguity, either import the "Prelude" hiding these names
37 -- or qualify uses of these function names with an alias for this module.
38 --
39 -----------------------------------------------------------------------------
40
41 module Data.Traversable (
42 -- * The 'Traversable' class
43 Traversable(..),
44 -- * Utility functions
45 for,
46 forM,
47 mapAccumL,
48 mapAccumR,
49 -- * General definitions for superclass methods
50 fmapDefault,
51 foldMapDefault,
52 ) where
53
54 import Prelude hiding (mapM, sequence, foldr)
55 import qualified Prelude (mapM, foldr)
56 import Control.Applicative
57 import Data.Foldable (Foldable())
58 import Data.Monoid (Monoid)
59 import Data.Proxy
60
61 #if defined(__GLASGOW_HASKELL__)
62 import GHC.Arr
63 #elif defined(__HUGS__)
64 import Hugs.Array
65 #endif
66
67 -- | Functors representing data structures that can be traversed from
68 -- left to right.
69 --
70 -- Minimal complete definition: 'traverse' or 'sequenceA'.
71 --
72 -- A definition of 'traverse' must satisfy the following laws:
73 --
74 -- [/naturality/]
75 -- @t . 'traverse' f = 'traverse' (t . f)@
76 -- for every applicative transformation @t@
77 --
78 -- [/identity/]
79 -- @'traverse' Identity = Identity@
80 --
81 -- [/composition/]
82 -- @'traverse' (Compose . 'fmap' g . f) = Compose . 'fmap' ('traverse' g) . 'traverse' f@
83 --
84 -- A definition of 'sequenceA' must satisfy the following laws:
85 --
86 -- [/naturality/]
87 -- @t . 'sequenceA' = 'sequenceA' . 'fmap' t@
88 -- for every applicative transformation @t@
89 --
90 -- [/identity/]
91 -- @'sequenceA' . 'fmap' Identity = Identity@
92 --
93 -- [/composition/]
94 -- @'sequenceA' . 'fmap' Compose = Compose . 'fmap' 'sequenceA' . 'sequenceA'@
95 --
96 -- where an /applicative transformation/ is a function
97 --
98 -- @t :: (Applicative f, Applicative g) => f a -> g a@
99 --
100 -- preserving the 'Applicative' operations, i.e.
101 --
102 -- * @t ('pure' x) = 'pure' x@
103 --
104 -- * @t (x '<*>' y) = t x '<*>' t y@
105 --
106 -- and the identity functor @Identity@ and composition of functors @Compose@
107 -- are defined as
108 --
109 -- > newtype Identity a = Identity a
110 -- >
111 -- > instance Functor Identity where
112 -- > fmap f (Identity x) = Identity (f x)
113 -- >
114 -- > instance Applicative Indentity where
115 -- > pure x = Identity x
116 -- > Identity f <*> Identity x = Identity (f x)
117 -- >
118 -- > newtype Compose f g a = Compose (f (g a))
119 -- >
120 -- > instance (Functor f, Functor g) => Functor (Compose f g) where
121 -- > fmap f (Compose x) = Compose (fmap (fmap f) x)
122 -- >
123 -- > instance (Applicative f, Applicative g) => Applicative (Compose f g) where
124 -- > pure x = Compose (pure (pure x))
125 -- > Compose f <*> Compose x = Compose ((<*>) <$> f <*> x)
126 --
127 -- (The naturality law is implied by parametricity.)
128 --
129 -- Instances are similar to 'Functor', e.g. given a data type
130 --
131 -- > data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)
132 --
133 -- a suitable instance would be
134 --
135 -- > instance Traversable Tree where
136 -- > traverse f Empty = pure Empty
137 -- > traverse f (Leaf x) = Leaf <$> f x
138 -- > traverse f (Node l k r) = Node <$> traverse f l <*> f k <*> traverse f r
139 --
140 -- This is suitable even for abstract types, as the laws for '<*>'
141 -- imply a form of associativity.
142 --
143 -- The superclass instances should satisfy the following:
144 --
145 -- * In the 'Functor' instance, 'fmap' should be equivalent to traversal
146 -- with the identity applicative functor ('fmapDefault').
147 --
148 -- * In the 'Foldable' instance, 'Data.Foldable.foldMap' should be
149 -- equivalent to traversal with a constant applicative functor
150 -- ('foldMapDefault').
151 --
152 class (Functor t, Foldable t) => Traversable t where
153 -- | Map each element of a structure to an action, evaluate
154 -- these actions from left to right, and collect the results.
155 traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
156 traverse f = sequenceA . fmap f
157
158 -- | Evaluate each action in the structure from left to right,
159 -- and collect the results.
160 sequenceA :: Applicative f => t (f a) -> f (t a)
161 sequenceA = traverse id
162
163 -- | Map each element of a structure to a monadic action, evaluate
164 -- these actions from left to right, and collect the results.
165 mapM :: Monad m => (a -> m b) -> t a -> m (t b)
166 mapM f = unwrapMonad . traverse (WrapMonad . f)
167
168 -- | Evaluate each monadic action in the structure from left to right,
169 -- and collect the results.
170 sequence :: Monad m => t (m a) -> m (t a)
171 sequence = mapM id
172
173 -- instances for Prelude types
174
175 instance Traversable Maybe where
176 traverse _ Nothing = pure Nothing
177 traverse f (Just x) = Just <$> f x
178
179 instance Traversable [] where
180 {-# INLINE traverse #-} -- so that traverse can fuse
181 traverse f = Prelude.foldr cons_f (pure [])
182 where cons_f x ys = (:) <$> f x <*> ys
183
184 mapM = Prelude.mapM
185
186 instance Traversable (Either a) where
187 traverse _ (Left x) = pure (Left x)
188 traverse f (Right y) = Right <$> f y
189
190 instance Traversable ((,) a) where
191 traverse f (x, y) = (,) x <$> f y
192
193 instance Ix i => Traversable (Array i) where
194 traverse f arr = listArray (bounds arr) `fmap` traverse f (elems arr)
195
196 instance Traversable Proxy where
197 traverse _ _ = pure Proxy
198 {-# INLINE traverse #-}
199 sequenceA _ = pure Proxy
200 {-# INLINE sequenceA #-}
201 mapM _ _ = return Proxy
202 {-# INLINE mapM #-}
203 sequence _ = return Proxy
204 {-# INLINE sequence #-}
205
206 -- general functions
207
208 -- | 'for' is 'traverse' with its arguments flipped.
209 for :: (Traversable t, Applicative f) => t a -> (a -> f b) -> f (t b)
210 {-# INLINE for #-}
211 for = flip traverse
212
213 -- | 'forM' is 'mapM' with its arguments flipped.
214 forM :: (Traversable t, Monad m) => t a -> (a -> m b) -> m (t b)
215 {-# INLINE forM #-}
216 forM = flip mapM
217
218 -- left-to-right state transformer
219 newtype StateL s a = StateL { runStateL :: s -> (s, a) }
220
221 instance Functor (StateL s) where
222 fmap f (StateL k) = StateL $ \ s -> let (s', v) = k s in (s', f v)
223
224 instance Applicative (StateL s) where
225 pure x = StateL (\ s -> (s, x))
226 StateL kf <*> StateL kv = StateL $ \ s ->
227 let (s', f) = kf s
228 (s'', v) = kv s'
229 in (s'', f v)
230
231 -- |The 'mapAccumL' function behaves like a combination of 'fmap'
232 -- and 'foldl'; it applies a function to each element of a structure,
233 -- passing an accumulating parameter from left to right, and returning
234 -- a final value of this accumulator together with the new structure.
235 mapAccumL :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c)
236 mapAccumL f s t = runStateL (traverse (StateL . flip f) t) s
237
238 -- right-to-left state transformer
239 newtype StateR s a = StateR { runStateR :: s -> (s, a) }
240
241 instance Functor (StateR s) where
242 fmap f (StateR k) = StateR $ \ s -> let (s', v) = k s in (s', f v)
243
244 instance Applicative (StateR s) where
245 pure x = StateR (\ s -> (s, x))
246 StateR kf <*> StateR kv = StateR $ \ s ->
247 let (s', v) = kv s
248 (s'', f) = kf s'
249 in (s'', f v)
250
251 -- |The 'mapAccumR' function behaves like a combination of 'fmap'
252 -- and 'foldr'; it applies a function to each element of a structure,
253 -- passing an accumulating parameter from right to left, and returning
254 -- a final value of this accumulator together with the new structure.
255 mapAccumR :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c)
256 mapAccumR f s t = runStateR (traverse (StateR . flip f) t) s
257
258 -- | This function may be used as a value for `fmap` in a `Functor`
259 -- instance, provided that 'traverse' is defined. (Using
260 -- `fmapDefault` with a `Traversable` instance defined only by
261 -- 'sequenceA' will result in infinite recursion.)
262 fmapDefault :: Traversable t => (a -> b) -> t a -> t b
263 {-# INLINE fmapDefault #-}
264 fmapDefault f = getId . traverse (Id . f)
265
266 -- | This function may be used as a value for `Data.Foldable.foldMap`
267 -- in a `Foldable` instance.
268 foldMapDefault :: (Traversable t, Monoid m) => (a -> m) -> t a -> m
269 foldMapDefault f = getConst . traverse (Const . f)
270
271 -- local instances
272
273 newtype Id a = Id { getId :: a }
274
275 instance Functor Id where
276 fmap f (Id x) = Id (f x)
277
278 instance Applicative Id where
279 pure = Id
280 Id f <*> Id x = Id (f x)
281