Remove Hugs98 specific code
[packages/base.git] / 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 #ifdef __GLASGOW_HASKELL__
62 import GHC.Arr
63 #endif
64
65 -- | Functors representing data structures that can be traversed from
66 -- left to right.
67 --
68 -- Minimal complete definition: 'traverse' or 'sequenceA'.
69 --
70 -- A definition of 'traverse' must satisfy the following laws:
71 --
72 -- [/naturality/]
73 -- @t . 'traverse' f = 'traverse' (t . f)@
74 -- for every applicative transformation @t@
75 --
76 -- [/identity/]
77 -- @'traverse' Identity = Identity@
78 --
79 -- [/composition/]
80 -- @'traverse' (Compose . 'fmap' g . f) = Compose . 'fmap' ('traverse' g) . 'traverse' f@
81 --
82 -- A definition of 'sequenceA' must satisfy the following laws:
83 --
84 -- [/naturality/]
85 -- @t . 'sequenceA' = 'sequenceA' . 'fmap' t@
86 -- for every applicative transformation @t@
87 --
88 -- [/identity/]
89 -- @'sequenceA' . 'fmap' Identity = Identity@
90 --
91 -- [/composition/]
92 -- @'sequenceA' . 'fmap' Compose = Compose . 'fmap' 'sequenceA' . 'sequenceA'@
93 --
94 -- where an /applicative transformation/ is a function
95 --
96 -- @t :: (Applicative f, Applicative g) => f a -> g a@
97 --
98 -- preserving the 'Applicative' operations, i.e.
99 --
100 -- * @t ('pure' x) = 'pure' x@
101 --
102 -- * @t (x '<*>' y) = t x '<*>' t y@
103 --
104 -- and the identity functor @Identity@ and composition of functors @Compose@
105 -- are defined as
106 --
107 -- > newtype Identity a = Identity a
108 -- >
109 -- > instance Functor Identity where
110 -- > fmap f (Identity x) = Identity (f x)
111 -- >
112 -- > instance Applicative Indentity where
113 -- > pure x = Identity x
114 -- > Identity f <*> Identity x = Identity (f x)
115 -- >
116 -- > newtype Compose f g a = Compose (f (g a))
117 -- >
118 -- > instance (Functor f, Functor g) => Functor (Compose f g) where
119 -- > fmap f (Compose x) = Compose (fmap (fmap f) x)
120 -- >
121 -- > instance (Applicative f, Applicative g) => Applicative (Compose f g) where
122 -- > pure x = Compose (pure (pure x))
123 -- > Compose f <*> Compose x = Compose ((<*>) <$> f <*> x)
124 --
125 -- (The naturality law is implied by parametricity.)
126 --
127 -- Instances are similar to 'Functor', e.g. given a data type
128 --
129 -- > data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)
130 --
131 -- a suitable instance would be
132 --
133 -- > instance Traversable Tree where
134 -- > traverse f Empty = pure Empty
135 -- > traverse f (Leaf x) = Leaf <$> f x
136 -- > traverse f (Node l k r) = Node <$> traverse f l <*> f k <*> traverse f r
137 --
138 -- This is suitable even for abstract types, as the laws for '<*>'
139 -- imply a form of associativity.
140 --
141 -- The superclass instances should satisfy the following:
142 --
143 -- * In the 'Functor' instance, 'fmap' should be equivalent to traversal
144 -- with the identity applicative functor ('fmapDefault').
145 --
146 -- * In the 'Foldable' instance, 'Data.Foldable.foldMap' should be
147 -- equivalent to traversal with a constant applicative functor
148 -- ('foldMapDefault').
149 --
150 class (Functor t, Foldable t) => Traversable t where
151 -- | Map each element of a structure to an action, evaluate
152 -- these actions from left to right, and collect the results.
153 traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
154 traverse f = sequenceA . fmap f
155
156 -- | Evaluate each action in the structure from left to right,
157 -- and collect the results.
158 sequenceA :: Applicative f => t (f a) -> f (t a)
159 sequenceA = traverse id
160
161 -- | Map each element of a structure to a monadic action, evaluate
162 -- these actions from left to right, and collect the results.
163 mapM :: Monad m => (a -> m b) -> t a -> m (t b)
164 mapM f = unwrapMonad . traverse (WrapMonad . f)
165
166 -- | Evaluate each monadic action in the structure from left to right,
167 -- and collect the results.
168 sequence :: Monad m => t (m a) -> m (t a)
169 sequence = mapM id
170
171 -- instances for Prelude types
172
173 instance Traversable Maybe where
174 traverse _ Nothing = pure Nothing
175 traverse f (Just x) = Just <$> f x
176
177 instance Traversable [] where
178 {-# INLINE traverse #-} -- so that traverse can fuse
179 traverse f = Prelude.foldr cons_f (pure [])
180 where cons_f x ys = (:) <$> f x <*> ys
181
182 mapM = Prelude.mapM
183
184 instance Traversable (Either a) where
185 traverse _ (Left x) = pure (Left x)
186 traverse f (Right y) = Right <$> f y
187
188 instance Traversable ((,) a) where
189 traverse f (x, y) = (,) x <$> f y
190
191 instance Ix i => Traversable (Array i) where
192 traverse f arr = listArray (bounds arr) `fmap` traverse f (elems arr)
193
194 instance Traversable Proxy where
195 traverse _ _ = pure Proxy
196 {-# INLINE traverse #-}
197 sequenceA _ = pure Proxy
198 {-# INLINE sequenceA #-}
199 mapM _ _ = return Proxy
200 {-# INLINE mapM #-}
201 sequence _ = return Proxy
202 {-# INLINE sequence #-}
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