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