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