Typo
[packages/base.git] / Data / Foldable.hs
1 {-# LANGUAGE Trustworthy #-}
2
3 -----------------------------------------------------------------------------
4 -- |
5 -- Module : Data.Foldable
6 -- Copyright : 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 folded to a summary value.
14 --
15 -- Many of these functions generalize "Prelude", "Control.Monad" and
16 -- "Data.List" functions of the same names from lists to any 'Foldable'
17 -- functor. To avoid ambiguity, either import those modules hiding
18 -- these names or qualify uses of these function names with an alias
19 -- for this module.
20 --
21 -----------------------------------------------------------------------------
22
23 module Data.Foldable (
24 -- * Folds
25 Foldable(..),
26 -- ** Special biased folds
27 foldrM,
28 foldlM,
29 -- ** Folding actions
30 -- *** Applicative actions
31 traverse_,
32 for_,
33 sequenceA_,
34 asum,
35 -- *** Monadic actions
36 mapM_,
37 forM_,
38 sequence_,
39 msum,
40 -- ** Specialized folds
41 toList,
42 concat,
43 concatMap,
44 and,
45 or,
46 any,
47 all,
48 sum,
49 product,
50 maximum,
51 maximumBy,
52 minimum,
53 minimumBy,
54 -- ** Searches
55 elem,
56 notElem,
57 find
58 ) where
59
60 import Prelude hiding (foldl, foldr, foldl1, foldr1, mapM_, sequence_,
61 elem, notElem, concat, concatMap, and, or, any, all,
62 sum, product, maximum, minimum)
63 import qualified Prelude (foldl, foldr, foldl1, foldr1)
64 import qualified Data.List as List (foldl')
65 import Control.Applicative
66 import Control.Monad (MonadPlus(..))
67 import Data.Maybe (fromMaybe, listToMaybe)
68 import Data.Monoid
69 import Data.Proxy
70
71 import GHC.Exts (build)
72 import GHC.Arr
73
74 -- | Data structures that can be folded.
75 --
76 -- Minimal complete definition: 'foldMap' or 'foldr'.
77 --
78 -- For example, given a data type
79 --
80 -- > data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)
81 --
82 -- a suitable instance would be
83 --
84 -- > instance Foldable Tree where
85 -- > foldMap f Empty = mempty
86 -- > foldMap f (Leaf x) = f x
87 -- > foldMap f (Node l k r) = foldMap f l `mappend` f k `mappend` foldMap f r
88 --
89 -- This is suitable even for abstract types, as the monoid is assumed
90 -- to satisfy the monoid laws. Alternatively, one could define @foldr@:
91 --
92 -- > instance Foldable Tree where
93 -- > foldr f z Empty = z
94 -- > foldr f z (Leaf x) = f x z
95 -- > foldr f z (Node l k r) = foldr f (f k (foldr f z r)) l
96 --
97 class Foldable t where
98 -- | Combine the elements of a structure using a monoid.
99 fold :: Monoid m => t m -> m
100 fold = foldMap id
101
102 -- | Map each element of the structure to a monoid,
103 -- and combine the results.
104 foldMap :: Monoid m => (a -> m) -> t a -> m
105 foldMap f = foldr (mappend . f) mempty
106
107 -- | Right-associative fold of a structure.
108 --
109 -- @'foldr' f z = 'Prelude.foldr' f z . 'toList'@
110 foldr :: (a -> b -> b) -> b -> t a -> b
111 foldr f z t = appEndo (foldMap (Endo . f) t) z
112
113 -- | Right-associative fold of a structure,
114 -- but with strict application of the operator.
115 foldr' :: (a -> b -> b) -> b -> t a -> b
116 foldr' f z0 xs = foldl f' id xs z0
117 where f' k x z = k $! f x z
118
119 -- | Left-associative fold of a structure.
120 --
121 -- @'foldl' f z = 'Prelude.foldl' f z . 'toList'@
122 foldl :: (b -> a -> b) -> b -> t a -> b
123 foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z
124
125 -- | Left-associative fold of a structure.
126 -- but with strict application of the operator.
127 --
128 -- @'foldl' f z = 'List.foldl'' f z . 'toList'@
129 foldl' :: (b -> a -> b) -> b -> t a -> b
130 foldl' f z0 xs = foldr f' id xs z0
131 where f' x k z = k $! f z x
132
133 -- | A variant of 'foldr' that has no base case,
134 -- and thus may only be applied to non-empty structures.
135 --
136 -- @'foldr1' f = 'Prelude.foldr1' f . 'toList'@
137 foldr1 :: (a -> a -> a) -> t a -> a
138 foldr1 f xs = fromMaybe (error "foldr1: empty structure")
139 (foldr mf Nothing xs)
140 where
141 mf x Nothing = Just x
142 mf x (Just y) = Just (f x y)
143
144 -- | A variant of 'foldl' that has no base case,
145 -- and thus may only be applied to non-empty structures.
146 --
147 -- @'foldl1' f = 'Prelude.foldl1' f . 'toList'@
148 foldl1 :: (a -> a -> a) -> t a -> a
149 foldl1 f xs = fromMaybe (error "foldl1: empty structure")
150 (foldl mf Nothing xs)
151 where
152 mf Nothing y = Just y
153 mf (Just x) y = Just (f x y)
154 {-# MINIMAL foldMap | foldr #-}
155
156 -- instances for Prelude types
157
158 instance Foldable Maybe where
159 foldr _ z Nothing = z
160 foldr f z (Just x) = f x z
161
162 foldl _ z Nothing = z
163 foldl f z (Just x) = f z x
164
165 instance Foldable [] where
166 foldr = Prelude.foldr
167 foldl = Prelude.foldl
168 foldl' = List.foldl'
169 foldr1 = Prelude.foldr1
170 foldl1 = Prelude.foldl1
171
172 instance Foldable (Either a) where
173 foldMap _ (Left _) = mempty
174 foldMap f (Right y) = f y
175
176 foldr _ z (Left _) = z
177 foldr f z (Right y) = f y z
178
179 instance Foldable ((,) a) where
180 foldMap f (_, y) = f y
181
182 foldr f z (_, y) = f y z
183
184 instance Ix i => Foldable (Array i) where
185 foldr f z = Prelude.foldr f z . elems
186 foldl f z = Prelude.foldl f z . elems
187 foldr1 f = Prelude.foldr1 f . elems
188 foldl1 f = Prelude.foldl1 f . elems
189
190 instance Foldable Proxy where
191 foldMap _ _ = mempty
192 {-# INLINE foldMap #-}
193 fold _ = mempty
194 {-# INLINE fold #-}
195 foldr _ z _ = z
196 {-# INLINE foldr #-}
197 foldl _ z _ = z
198 {-# INLINE foldl #-}
199 foldl1 _ _ = error "foldl1: Proxy"
200 {-# INLINE foldl1 #-}
201 foldr1 _ _ = error "foldr1: Proxy"
202 {-# INLINE foldr1 #-}
203
204 instance Foldable (Const m) where
205 foldMap _ _ = mempty
206
207 -- | Monadic fold over the elements of a structure,
208 -- associating to the right, i.e. from right to left.
209 foldrM :: (Foldable t, Monad m) => (a -> b -> m b) -> b -> t a -> m b
210 foldrM f z0 xs = foldl f' return xs z0
211 where f' k x z = f x z >>= k
212
213 -- | Monadic fold over the elements of a structure,
214 -- associating to the left, i.e. from left to right.
215 foldlM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b
216 foldlM f z0 xs = foldr f' return xs z0
217 where f' x k z = f z x >>= k
218
219 -- | Map each element of a structure to an action, evaluate
220 -- these actions from left to right, and ignore the results.
221 traverse_ :: (Foldable t, Applicative f) => (a -> f b) -> t a -> f ()
222 traverse_ f = foldr ((*>) . f) (pure ())
223
224 -- | 'for_' is 'traverse_' with its arguments flipped.
225 for_ :: (Foldable t, Applicative f) => t a -> (a -> f b) -> f ()
226 {-# INLINE for_ #-}
227 for_ = flip traverse_
228
229 -- | Map each element of a structure to a monadic action, evaluate
230 -- these actions from left to right, and ignore the results.
231 mapM_ :: (Foldable t, Monad m) => (a -> m b) -> t a -> m ()
232 mapM_ f = foldr ((>>) . f) (return ())
233
234 -- | 'forM_' is 'mapM_' with its arguments flipped.
235 forM_ :: (Foldable t, Monad m) => t a -> (a -> m b) -> m ()
236 {-# INLINE forM_ #-}
237 forM_ = flip mapM_
238
239 -- | Evaluate each action in the structure from left to right,
240 -- and ignore the results.
241 sequenceA_ :: (Foldable t, Applicative f) => t (f a) -> f ()
242 sequenceA_ = foldr (*>) (pure ())
243
244 -- | Evaluate each monadic action in the structure from left to right,
245 -- and ignore the results.
246 sequence_ :: (Foldable t, Monad m) => t (m a) -> m ()
247 sequence_ = foldr (>>) (return ())
248
249 -- | The sum of a collection of actions, generalizing 'concat'.
250 asum :: (Foldable t, Alternative f) => t (f a) -> f a
251 {-# INLINE asum #-}
252 asum = foldr (<|>) empty
253
254 -- | The sum of a collection of actions, generalizing 'concat'.
255 msum :: (Foldable t, MonadPlus m) => t (m a) -> m a
256 {-# INLINE msum #-}
257 msum = foldr mplus mzero
258
259 -- These use foldr rather than foldMap to avoid repeated concatenation.
260
261 -- | List of elements of a structure.
262 toList :: Foldable t => t a -> [a]
263 {-# INLINE toList #-}
264 toList t = build (\ c n -> foldr c n t)
265
266 -- | The concatenation of all the elements of a container of lists.
267 concat :: Foldable t => t [a] -> [a]
268 concat = fold
269
270 -- | Map a function over all the elements of a container and concatenate
271 -- the resulting lists.
272 concatMap :: Foldable t => (a -> [b]) -> t a -> [b]
273 concatMap = foldMap
274
275 -- | 'and' returns the conjunction of a container of Bools. For the
276 -- result to be 'True', the container must be finite; 'False', however,
277 -- results from a 'False' value finitely far from the left end.
278 and :: Foldable t => t Bool -> Bool
279 and = getAll . foldMap All
280
281 -- | 'or' returns the disjunction of a container of Bools. For the
282 -- result to be 'False', the container must be finite; 'True', however,
283 -- results from a 'True' value finitely far from the left end.
284 or :: Foldable t => t Bool -> Bool
285 or = getAny . foldMap Any
286
287 -- | Determines whether any element of the structure satisfies the predicate.
288 any :: Foldable t => (a -> Bool) -> t a -> Bool
289 any p = getAny . foldMap (Any . p)
290
291 -- | Determines whether all elements of the structure satisfy the predicate.
292 all :: Foldable t => (a -> Bool) -> t a -> Bool
293 all p = getAll . foldMap (All . p)
294
295 -- | The 'sum' function computes the sum of the numbers of a structure.
296 sum :: (Foldable t, Num a) => t a -> a
297 sum = getSum . foldMap Sum
298
299 -- | The 'product' function computes the product of the numbers of a structure.
300 product :: (Foldable t, Num a) => t a -> a
301 product = getProduct . foldMap Product
302
303 -- | The largest element of a non-empty structure.
304 maximum :: (Foldable t, Ord a) => t a -> a
305 maximum = foldr1 max
306
307 -- | The largest element of a non-empty structure with respect to the
308 -- given comparison function.
309 maximumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a
310 maximumBy cmp = foldr1 max'
311 where max' x y = case cmp x y of
312 GT -> x
313 _ -> y
314
315 -- | The least element of a non-empty structure.
316 minimum :: (Foldable t, Ord a) => t a -> a
317 minimum = foldr1 min
318
319 -- | The least element of a non-empty structure with respect to the
320 -- given comparison function.
321 minimumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a
322 minimumBy cmp = foldr1 min'
323 where min' x y = case cmp x y of
324 GT -> y
325 _ -> x
326
327 -- | Does the element occur in the structure?
328 elem :: (Foldable t, Eq a) => a -> t a -> Bool
329 elem = any . (==)
330
331 -- | 'notElem' is the negation of 'elem'.
332 notElem :: (Foldable t, Eq a) => a -> t a -> Bool
333 notElem x = not . elem x
334
335 -- | The 'find' function takes a predicate and a structure and returns
336 -- the leftmost element of the structure matching the predicate, or
337 -- 'Nothing' if there is no such element.
338 find :: Foldable t => (a -> Bool) -> t a -> Maybe a
339 find p = listToMaybe . concatMap (\ x -> if p x then [x] else [])
340