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