Update Trac ticket URLs to point to GitLab
[ghc.git] / libraries / base / Data / Foldable.hs
1 {-# LANGUAGE DeriveFoldable #-}
2 {-# LANGUAGE FlexibleInstances #-}
3 {-# LANGUAGE NoImplicitPrelude #-}
4 {-# LANGUAGE ScopedTypeVariables #-}
5 {-# LANGUAGE StandaloneDeriving #-}
6 {-# LANGUAGE Trustworthy #-}
7 {-# LANGUAGE TypeOperators #-}
8
9 -----------------------------------------------------------------------------
10 -- |
11 -- Module : Data.Foldable
12 -- Copyright : Ross Paterson 2005
13 -- License : BSD-style (see the LICENSE file in the distribution)
14 --
15 -- Maintainer : libraries@haskell.org
16 -- Stability : experimental
17 -- Portability : portable
18 --
19 -- Class of data structures that can be folded to a summary value.
20 --
21 -----------------------------------------------------------------------------
22
23 module Data.Foldable (
24 Foldable(..),
25 -- * Special biased folds
26 foldrM,
27 foldlM,
28 -- * Folding actions
29 -- ** Applicative actions
30 traverse_,
31 for_,
32 sequenceA_,
33 asum,
34 -- ** Monadic actions
35 mapM_,
36 forM_,
37 sequence_,
38 msum,
39 -- * Specialized folds
40 concat,
41 concatMap,
42 and,
43 or,
44 any,
45 all,
46 maximumBy,
47 minimumBy,
48 -- * Searches
49 notElem,
50 find
51 ) where
52
53 import Data.Bool
54 import Data.Either
55 import Data.Eq
56 import Data.Functor.Utils (Max(..), Min(..), (#.))
57 import qualified GHC.List as List
58 import Data.Maybe
59 import Data.Monoid
60 import Data.Ord
61 import Data.Proxy
62
63 import GHC.Arr ( Array(..), elems, numElements,
64 foldlElems, foldrElems,
65 foldlElems', foldrElems',
66 foldl1Elems, foldr1Elems)
67 import GHC.Base hiding ( foldr )
68 import GHC.Generics
69 import GHC.Num ( Num(..) )
70
71 infix 4 `elem`, `notElem`
72
73 -- | Data structures that can be folded.
74 --
75 -- For example, given a data type
76 --
77 -- > data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)
78 --
79 -- a suitable instance would be
80 --
81 -- > instance Foldable Tree where
82 -- > foldMap f Empty = mempty
83 -- > foldMap f (Leaf x) = f x
84 -- > foldMap f (Node l k r) = foldMap f l `mappend` f k `mappend` foldMap f r
85 --
86 -- This is suitable even for abstract types, as the monoid is assumed
87 -- to satisfy the monoid laws. Alternatively, one could define @foldr@:
88 --
89 -- > instance Foldable Tree where
90 -- > foldr f z Empty = z
91 -- > foldr f z (Leaf x) = f x z
92 -- > foldr f z (Node l k r) = foldr f (f k (foldr f z r)) l
93 --
94 -- @Foldable@ instances are expected to satisfy the following laws:
95 --
96 -- > foldr f z t = appEndo (foldMap (Endo . f) t ) z
97 --
98 -- > foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z
99 --
100 -- > fold = foldMap id
101 --
102 -- > length = getSum . foldMap (Sum . const 1)
103 --
104 -- @sum@, @product@, @maximum@, and @minimum@ should all be essentially
105 -- equivalent to @foldMap@ forms, such as
106 --
107 -- > sum = getSum . foldMap Sum
108 --
109 -- but may be less defined.
110 --
111 -- If the type is also a 'Functor' instance, it should satisfy
112 --
113 -- > foldMap f = fold . fmap f
114 --
115 -- which implies that
116 --
117 -- > foldMap f . fmap g = foldMap (f . g)
118
119 class Foldable t where
120 {-# MINIMAL foldMap | foldr #-}
121
122 -- | Combine the elements of a structure using a monoid.
123 fold :: Monoid m => t m -> m
124 fold = foldMap id
125
126 -- | Map each element of the structure to a monoid,
127 -- and combine the results.
128 foldMap :: Monoid m => (a -> m) -> t a -> m
129 {-# INLINE foldMap #-}
130 -- This INLINE allows more list functions to fuse. See #9848.
131 foldMap f = foldr (mappend . f) mempty
132
133 -- | A variant of 'foldMap' that is strict in the accumulator.
134 --
135 -- @since 4.13.0.0
136 foldMap' :: Monoid m => (a -> m) -> t a -> m
137 foldMap' f = foldl' (\ acc a -> acc <> f a) mempty
138
139 -- | Right-associative fold of a structure.
140 --
141 -- In the case of lists, 'foldr', when applied to a binary operator, a
142 -- starting value (typically the right-identity of the operator), and a
143 -- list, reduces the list using the binary operator, from right to left:
144 --
145 -- > foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)
146 --
147 -- Note that, since the head of the resulting expression is produced by
148 -- an application of the operator to the first element of the list,
149 -- 'foldr' can produce a terminating expression from an infinite list.
150 --
151 -- For a general 'Foldable' structure this should be semantically identical
152 -- to,
153 --
154 -- @foldr f z = 'List.foldr' f z . 'toList'@
155 --
156 foldr :: (a -> b -> b) -> b -> t a -> b
157 foldr f z t = appEndo (foldMap (Endo #. f) t) z
158
159 -- | Right-associative fold of a structure, but with strict application of
160 -- the operator.
161 --
162 -- @since 4.6.0.0
163 foldr' :: (a -> b -> b) -> b -> t a -> b
164 foldr' f z0 xs = foldl f' id xs z0
165 where f' k x z = k $! f x z
166
167 -- | Left-associative fold of a structure.
168 --
169 -- In the case of lists, 'foldl', when applied to a binary
170 -- operator, a starting value (typically the left-identity of the operator),
171 -- and a list, reduces the list using the binary operator, from left to
172 -- right:
173 --
174 -- > foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn
175 --
176 -- Note that to produce the outermost application of the operator the
177 -- entire input list must be traversed. This means that 'foldl'' will
178 -- diverge if given an infinite list.
179 --
180 -- Also note that if you want an efficient left-fold, you probably want to
181 -- use 'foldl'' instead of 'foldl'. The reason for this is that latter does
182 -- not force the "inner" results (e.g. @z \`f\` x1@ in the above example)
183 -- before applying them to the operator (e.g. to @(\`f\` x2)@). This results
184 -- in a thunk chain @O(n)@ elements long, which then must be evaluated from
185 -- the outside-in.
186 --
187 -- For a general 'Foldable' structure this should be semantically identical
188 -- to,
189 --
190 -- @foldl f z = 'List.foldl' f z . 'toList'@
191 --
192 foldl :: (b -> a -> b) -> b -> t a -> b
193 foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z
194 -- There's no point mucking around with coercions here,
195 -- because flip forces us to build a new function anyway.
196
197 -- | Left-associative fold of a structure but with strict application of
198 -- the operator.
199 --
200 -- This ensures that each step of the fold is forced to weak head normal
201 -- form before being applied, avoiding the collection of thunks that would
202 -- otherwise occur. This is often what you want to strictly reduce a finite
203 -- list to a single, monolithic result (e.g. 'length').
204 --
205 -- For a general 'Foldable' structure this should be semantically identical
206 -- to,
207 --
208 -- @foldl' f z = 'List.foldl'' f z . 'toList'@
209 --
210 -- @since 4.6.0.0
211 foldl' :: (b -> a -> b) -> b -> t a -> b
212 foldl' f z0 xs = foldr f' id xs z0
213 where f' x k z = k $! f z x
214
215 -- | A variant of 'foldr' that has no base case,
216 -- and thus may only be applied to non-empty structures.
217 --
218 -- @'foldr1' f = 'List.foldr1' f . 'toList'@
219 foldr1 :: (a -> a -> a) -> t a -> a
220 foldr1 f xs = fromMaybe (errorWithoutStackTrace "foldr1: empty structure")
221 (foldr mf Nothing xs)
222 where
223 mf x m = Just (case m of
224 Nothing -> x
225 Just y -> f x y)
226
227 -- | A variant of 'foldl' that has no base case,
228 -- and thus may only be applied to non-empty structures.
229 --
230 -- @'foldl1' f = 'List.foldl1' f . 'toList'@
231 foldl1 :: (a -> a -> a) -> t a -> a
232 foldl1 f xs = fromMaybe (errorWithoutStackTrace "foldl1: empty structure")
233 (foldl mf Nothing xs)
234 where
235 mf m y = Just (case m of
236 Nothing -> y
237 Just x -> f x y)
238
239 -- | List of elements of a structure, from left to right.
240 --
241 -- @since 4.8.0.0
242 toList :: t a -> [a]
243 {-# INLINE toList #-}
244 toList t = build (\ c n -> foldr c n t)
245
246 -- | Test whether the structure is empty. The default implementation is
247 -- optimized for structures that are similar to cons-lists, because there
248 -- is no general way to do better.
249 --
250 -- @since 4.8.0.0
251 null :: t a -> Bool
252 null = foldr (\_ _ -> False) True
253
254 -- | Returns the size/length of a finite structure as an 'Int'. The
255 -- default implementation is optimized for structures that are similar to
256 -- cons-lists, because there is no general way to do better.
257 --
258 -- @since 4.8.0.0
259 length :: t a -> Int
260 length = foldl' (\c _ -> c+1) 0
261
262 -- | Does the element occur in the structure?
263 --
264 -- @since 4.8.0.0
265 elem :: Eq a => a -> t a -> Bool
266 elem = any . (==)
267
268 -- | The largest element of a non-empty structure.
269 --
270 -- @since 4.8.0.0
271 maximum :: forall a . Ord a => t a -> a
272 maximum = fromMaybe (errorWithoutStackTrace "maximum: empty structure") .
273 getMax . foldMap (Max #. (Just :: a -> Maybe a))
274
275 -- | The least element of a non-empty structure.
276 --
277 -- @since 4.8.0.0
278 minimum :: forall a . Ord a => t a -> a
279 minimum = fromMaybe (errorWithoutStackTrace "minimum: empty structure") .
280 getMin . foldMap (Min #. (Just :: a -> Maybe a))
281
282 -- | The 'sum' function computes the sum of the numbers of a structure.
283 --
284 -- @since 4.8.0.0
285 sum :: Num a => t a -> a
286 sum = getSum #. foldMap Sum
287
288 -- | The 'product' function computes the product of the numbers of a
289 -- structure.
290 --
291 -- @since 4.8.0.0
292 product :: Num a => t a -> a
293 product = getProduct #. foldMap Product
294
295 -- instances for Prelude types
296
297 -- | @since 2.01
298 instance Foldable Maybe where
299 foldMap = maybe mempty
300
301 foldr _ z Nothing = z
302 foldr f z (Just x) = f x z
303
304 foldl _ z Nothing = z
305 foldl f z (Just x) = f z x
306
307 -- | @since 2.01
308 instance Foldable [] where
309 elem = List.elem
310 foldl = List.foldl
311 foldl' = List.foldl'
312 foldl1 = List.foldl1
313 foldr = List.foldr
314 foldr1 = List.foldr1
315 length = List.length
316 maximum = List.maximum
317 minimum = List.minimum
318 null = List.null
319 product = List.product
320 sum = List.sum
321 toList = id
322
323 -- | @since 4.9.0.0
324 instance Foldable NonEmpty where
325 foldr f z ~(a :| as) = f a (List.foldr f z as)
326 foldl f z (a :| as) = List.foldl f (f z a) as
327 foldl1 f (a :| as) = List.foldl f a as
328
329 -- GHC isn't clever enough to transform the default definition
330 -- into anything like this, so we'd end up shuffling a bunch of
331 -- Maybes around.
332 foldr1 f (p :| ps) = foldr go id ps p
333 where
334 go x r prev = f prev (r x)
335
336 -- We used to say
337 --
338 -- length (_ :| as) = 1 + length as
339 --
340 -- but the default definition is better, counting from 1.
341 --
342 -- The default definition also works great for null and foldl'.
343 -- As usual for cons lists, foldr' is basically hopeless.
344
345 foldMap f ~(a :| as) = f a `mappend` foldMap f as
346 fold ~(m :| ms) = m `mappend` fold ms
347 toList ~(a :| as) = a : as
348
349 -- | @since 4.7.0.0
350 instance Foldable (Either a) where
351 foldMap _ (Left _) = mempty
352 foldMap f (Right y) = f y
353
354 foldr _ z (Left _) = z
355 foldr f z (Right y) = f y z
356
357 length (Left _) = 0
358 length (Right _) = 1
359
360 null = isLeft
361
362 -- | @since 4.7.0.0
363 instance Foldable ((,) a) where
364 foldMap f (_, y) = f y
365
366 foldr f z (_, y) = f y z
367
368 -- | @since 4.8.0.0
369 instance Foldable (Array i) where
370 foldr = foldrElems
371 foldl = foldlElems
372 foldl' = foldlElems'
373 foldr' = foldrElems'
374 foldl1 = foldl1Elems
375 foldr1 = foldr1Elems
376 toList = elems
377 length = numElements
378 null a = numElements a == 0
379
380 -- | @since 4.7.0.0
381 instance Foldable Proxy where
382 foldMap _ _ = mempty
383 {-# INLINE foldMap #-}
384 fold _ = mempty
385 {-# INLINE fold #-}
386 foldr _ z _ = z
387 {-# INLINE foldr #-}
388 foldl _ z _ = z
389 {-# INLINE foldl #-}
390 foldl1 _ _ = errorWithoutStackTrace "foldl1: Proxy"
391 foldr1 _ _ = errorWithoutStackTrace "foldr1: Proxy"
392 length _ = 0
393 null _ = True
394 elem _ _ = False
395 sum _ = 0
396 product _ = 1
397
398 -- | @since 4.8.0.0
399 instance Foldable Dual where
400 foldMap = coerce
401
402 elem = (. getDual) #. (==)
403 foldl = coerce
404 foldl' = coerce
405 foldl1 _ = getDual
406 foldr f z (Dual x) = f x z
407 foldr' = foldr
408 foldr1 _ = getDual
409 length _ = 1
410 maximum = getDual
411 minimum = getDual
412 null _ = False
413 product = getDual
414 sum = getDual
415 toList (Dual x) = [x]
416
417 -- | @since 4.8.0.0
418 instance Foldable Sum where
419 foldMap = coerce
420
421 elem = (. getSum) #. (==)
422 foldl = coerce
423 foldl' = coerce
424 foldl1 _ = getSum
425 foldr f z (Sum x) = f x z
426 foldr' = foldr
427 foldr1 _ = getSum
428 length _ = 1
429 maximum = getSum
430 minimum = getSum
431 null _ = False
432 product = getSum
433 sum = getSum
434 toList (Sum x) = [x]
435
436 -- | @since 4.8.0.0
437 instance Foldable Product where
438 foldMap = coerce
439
440 elem = (. getProduct) #. (==)
441 foldl = coerce
442 foldl' = coerce
443 foldl1 _ = getProduct
444 foldr f z (Product x) = f x z
445 foldr' = foldr
446 foldr1 _ = getProduct
447 length _ = 1
448 maximum = getProduct
449 minimum = getProduct
450 null _ = False
451 product = getProduct
452 sum = getProduct
453 toList (Product x) = [x]
454
455 -- | @since 4.8.0.0
456 instance Foldable First where
457 foldMap f = foldMap f . getFirst
458
459 -- | @since 4.8.0.0
460 instance Foldable Last where
461 foldMap f = foldMap f . getLast
462
463 -- | @since 4.12.0.0
464 instance (Foldable f) => Foldable (Alt f) where
465 foldMap f = foldMap f . getAlt
466
467 -- | @since 4.12.0.0
468 instance (Foldable f) => Foldable (Ap f) where
469 foldMap f = foldMap f . getAp
470
471 -- Instances for GHC.Generics
472 -- | @since 4.9.0.0
473 instance Foldable U1 where
474 foldMap _ _ = mempty
475 {-# INLINE foldMap #-}
476 fold _ = mempty
477 {-# INLINE fold #-}
478 foldr _ z _ = z
479 {-# INLINE foldr #-}
480 foldl _ z _ = z
481 {-# INLINE foldl #-}
482 foldl1 _ _ = errorWithoutStackTrace "foldl1: U1"
483 foldr1 _ _ = errorWithoutStackTrace "foldr1: U1"
484 length _ = 0
485 null _ = True
486 elem _ _ = False
487 sum _ = 0
488 product _ = 1
489
490 -- | @since 4.9.0.0
491 deriving instance Foldable V1
492
493 -- | @since 4.9.0.0
494 deriving instance Foldable Par1
495
496 -- | @since 4.9.0.0
497 deriving instance Foldable f => Foldable (Rec1 f)
498
499 -- | @since 4.9.0.0
500 deriving instance Foldable (K1 i c)
501
502 -- | @since 4.9.0.0
503 deriving instance Foldable f => Foldable (M1 i c f)
504
505 -- | @since 4.9.0.0
506 deriving instance (Foldable f, Foldable g) => Foldable (f :+: g)
507
508 -- | @since 4.9.0.0
509 deriving instance (Foldable f, Foldable g) => Foldable (f :*: g)
510
511 -- | @since 4.9.0.0
512 deriving instance (Foldable f, Foldable g) => Foldable (f :.: g)
513
514 -- | @since 4.9.0.0
515 deriving instance Foldable UAddr
516
517 -- | @since 4.9.0.0
518 deriving instance Foldable UChar
519
520 -- | @since 4.9.0.0
521 deriving instance Foldable UDouble
522
523 -- | @since 4.9.0.0
524 deriving instance Foldable UFloat
525
526 -- | @since 4.9.0.0
527 deriving instance Foldable UInt
528
529 -- | @since 4.9.0.0
530 deriving instance Foldable UWord
531
532 -- Instances for Data.Ord
533 -- | @since 4.12.0.0
534 deriving instance Foldable Down
535
536 -- | Monadic fold over the elements of a structure,
537 -- associating to the right, i.e. from right to left.
538 foldrM :: (Foldable t, Monad m) => (a -> b -> m b) -> b -> t a -> m b
539 foldrM f z0 xs = foldl c return xs z0
540 -- See Note [List fusion and continuations in 'c']
541 where c k x z = f x z >>= k
542 {-# INLINE c #-}
543
544 -- | Monadic fold over the elements of a structure,
545 -- associating to the left, i.e. from left to right.
546 foldlM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b
547 foldlM f z0 xs = foldr c return xs z0
548 -- See Note [List fusion and continuations in 'c']
549 where c x k z = f z x >>= k
550 {-# INLINE c #-}
551
552 -- | Map each element of a structure to an action, evaluate these
553 -- actions from left to right, and ignore the results. For a version
554 -- that doesn't ignore the results see 'Data.Traversable.traverse'.
555 traverse_ :: (Foldable t, Applicative f) => (a -> f b) -> t a -> f ()
556 traverse_ f = foldr c (pure ())
557 -- See Note [List fusion and continuations in 'c']
558 where c x k = f x *> k
559 {-# INLINE c #-}
560
561 -- | 'for_' is 'traverse_' with its arguments flipped. For a version
562 -- that doesn't ignore the results see 'Data.Traversable.for'.
563 --
564 -- >>> for_ [1..4] print
565 -- 1
566 -- 2
567 -- 3
568 -- 4
569 for_ :: (Foldable t, Applicative f) => t a -> (a -> f b) -> f ()
570 {-# INLINE for_ #-}
571 for_ = flip traverse_
572
573 -- | Map each element of a structure to a monadic action, evaluate
574 -- these actions from left to right, and ignore the results. For a
575 -- version that doesn't ignore the results see
576 -- 'Data.Traversable.mapM'.
577 --
578 -- As of base 4.8.0.0, 'mapM_' is just 'traverse_', specialized to
579 -- 'Monad'.
580 mapM_ :: (Foldable t, Monad m) => (a -> m b) -> t a -> m ()
581 mapM_ f = foldr c (return ())
582 -- See Note [List fusion and continuations in 'c']
583 where c x k = f x >> k
584 {-# INLINE c #-}
585
586 -- | 'forM_' is 'mapM_' with its arguments flipped. For a version that
587 -- doesn't ignore the results see 'Data.Traversable.forM'.
588 --
589 -- As of base 4.8.0.0, 'forM_' is just 'for_', specialized to 'Monad'.
590 forM_ :: (Foldable t, Monad m) => t a -> (a -> m b) -> m ()
591 {-# INLINE forM_ #-}
592 forM_ = flip mapM_
593
594 -- | Evaluate each action in the structure from left to right, and
595 -- ignore the results. For a version that doesn't ignore the results
596 -- see 'Data.Traversable.sequenceA'.
597 sequenceA_ :: (Foldable t, Applicative f) => t (f a) -> f ()
598 sequenceA_ = foldr c (pure ())
599 -- See Note [List fusion and continuations in 'c']
600 where c m k = m *> k
601 {-# INLINE c #-}
602
603 -- | Evaluate each monadic action in the structure from left to right,
604 -- and ignore the results. For a version that doesn't ignore the
605 -- results see 'Data.Traversable.sequence'.
606 --
607 -- As of base 4.8.0.0, 'sequence_' is just 'sequenceA_', specialized
608 -- to 'Monad'.
609 sequence_ :: (Foldable t, Monad m) => t (m a) -> m ()
610 sequence_ = foldr c (return ())
611 -- See Note [List fusion and continuations in 'c']
612 where c m k = m >> k
613 {-# INLINE c #-}
614
615 -- | The sum of a collection of actions, generalizing 'concat'.
616 --
617 -- >>> asum [Just "Hello", Nothing, Just "World"]
618 -- Just "Hello"
619 asum :: (Foldable t, Alternative f) => t (f a) -> f a
620 {-# INLINE asum #-}
621 asum = foldr (<|>) empty
622
623 -- | The sum of a collection of actions, generalizing 'concat'.
624 -- As of base 4.8.0.0, 'msum' is just 'asum', specialized to 'MonadPlus'.
625 msum :: (Foldable t, MonadPlus m) => t (m a) -> m a
626 {-# INLINE msum #-}
627 msum = asum
628
629 -- | The concatenation of all the elements of a container of lists.
630 concat :: Foldable t => t [a] -> [a]
631 concat xs = build (\c n -> foldr (\x y -> foldr c y x) n xs)
632 {-# INLINE concat #-}
633
634 -- | Map a function over all the elements of a container and concatenate
635 -- the resulting lists.
636 concatMap :: Foldable t => (a -> [b]) -> t a -> [b]
637 concatMap f xs = build (\c n -> foldr (\x b -> foldr c b (f x)) n xs)
638 {-# INLINE concatMap #-}
639
640 -- These use foldr rather than foldMap to avoid repeated concatenation.
641
642 -- | 'and' returns the conjunction of a container of Bools. For the
643 -- result to be 'True', the container must be finite; 'False', however,
644 -- results from a 'False' value finitely far from the left end.
645 and :: Foldable t => t Bool -> Bool
646 and = getAll #. foldMap All
647
648 -- | 'or' returns the disjunction of a container of Bools. For the
649 -- result to be 'False', the container must be finite; 'True', however,
650 -- results from a 'True' value finitely far from the left end.
651 or :: Foldable t => t Bool -> Bool
652 or = getAny #. foldMap Any
653
654 -- | Determines whether any element of the structure satisfies the predicate.
655 any :: Foldable t => (a -> Bool) -> t a -> Bool
656 any p = getAny #. foldMap (Any #. p)
657
658 -- | Determines whether all elements of the structure satisfy the predicate.
659 all :: Foldable t => (a -> Bool) -> t a -> Bool
660 all p = getAll #. foldMap (All #. p)
661
662 -- | The largest element of a non-empty structure with respect to the
663 -- given comparison function.
664
665 -- See Note [maximumBy/minimumBy space usage]
666 maximumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a
667 maximumBy cmp = foldl1 max'
668 where max' x y = case cmp x y of
669 GT -> x
670 _ -> y
671
672 -- | The least element of a non-empty structure with respect to the
673 -- given comparison function.
674
675 -- See Note [maximumBy/minimumBy space usage]
676 minimumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a
677 minimumBy cmp = foldl1 min'
678 where min' x y = case cmp x y of
679 GT -> y
680 _ -> x
681
682 -- | 'notElem' is the negation of 'elem'.
683 notElem :: (Foldable t, Eq a) => a -> t a -> Bool
684 notElem x = not . elem x
685
686 -- | The 'find' function takes a predicate and a structure and returns
687 -- the leftmost element of the structure matching the predicate, or
688 -- 'Nothing' if there is no such element.
689 find :: Foldable t => (a -> Bool) -> t a -> Maybe a
690 find p = getFirst . foldMap (\ x -> First (if p x then Just x else Nothing))
691
692 {-
693 Note [List fusion and continuations in 'c']
694 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
695 Suppose we define
696 mapM_ f = foldr ((>>) . f) (return ())
697 (this is the way it used to be).
698
699 Now suppose we want to optimise the call
700
701 mapM_ <big> (build g)
702 where
703 g c n = ...(c x1 y1)...(c x2 y2)....n...
704
705 GHC used to proceed like this:
706
707 mapM_ <big> (build g)
708
709 = { Definition of mapM_ }
710 foldr ((>>) . <big>) (return ()) (build g)
711
712 = { foldr/build rule }
713 g ((>>) . <big>) (return ())
714
715 = { Inline g }
716 let c = (>>) . <big>
717 n = return ()
718 in ...(c x1 y1)...(c x2 y2)....n...
719
720 The trouble is that `c`, being big, will not be inlined. And that can
721 be absolutely terrible for performance, as we saw in #8763.
722
723 It's much better to define
724
725 mapM_ f = foldr c (return ())
726 where
727 c x k = f x >> k
728 {-# INLINE c #-}
729
730 Now we get
731 mapM_ <big> (build g)
732
733 = { inline mapM_ }
734 foldr c (return ()) (build g)
735 where c x k = f x >> k
736 {-# INLINE c #-}
737 f = <big>
738
739 Notice that `f` does not inline into the RHS of `c`,
740 because the INLINE pragma stops it; see
741 Note [Simplifying inside stable unfoldings] in SimplUtils.
742 Continuing:
743
744 = { foldr/build rule }
745 g c (return ())
746 where ...
747 c x k = f x >> k
748 {-# INLINE c #-}
749 f = <big>
750
751 = { inline g }
752 ...(c x1 y1)...(c x2 y2)....n...
753 where c x k = f x >> k
754 {-# INLINE c #-}
755 f = <big>
756 n = return ()
757
758 Now, crucially, `c` does inline
759
760 = { inline c }
761 ...(f x1 >> y1)...(f x2 >> y2)....n...
762 where f = <big>
763 n = return ()
764
765 And all is well! The key thing is that the fragment
766 `(f x1 >> y1)` is inlined into the body of the builder
767 `g`.
768 -}
769
770 {-
771 Note [maximumBy/minimumBy space usage]
772 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
773 When the type signatures of maximumBy and minimumBy were generalized to work
774 over any Foldable instance (instead of just lists), they were defined using
775 foldr1. This was problematic for space usage, as the semantics of maximumBy
776 and minimumBy essentially require that they examine every element of the
777 data structure. Using foldr1 to examine every element results in space usage
778 proportional to the size of the data structure. For the common case of lists,
779 this could be particularly bad (see #10830).
780
781 For the common case of lists, switching the implementations of maximumBy and
782 minimumBy to foldl1 solves the issue, as GHC's strictness analysis can then
783 make these functions only use O(1) stack space. It is perhaps not the optimal
784 way to fix this problem, as there are other conceivable data structures
785 (besides lists) which might benefit from specialized implementations for
786 maximumBy and minimumBy (see
787 https://gitlab.haskell.org/ghc/ghc/issues/10830#note_129843 for a further
788 discussion). But using foldl1 is at least always better than using foldr1, so
789 GHC has chosen to adopt that approach for now.
790 -}