Foldable.hs 23.5 KB
Newer Older
1
2
{-# LANGUAGE DeriveFoldable #-}
{-# LANGUAGE FlexibleInstances #-}
3
{-# LANGUAGE NoImplicitPrelude #-}
4
{-# LANGUAGE ScopedTypeVariables #-}
5
6
7
{-# LANGUAGE StandaloneDeriving #-}
{-# LANGUAGE Trustworthy #-}
{-# LANGUAGE TypeOperators #-}
8

9
10
11
12
13
14
-----------------------------------------------------------------------------
-- |
-- Module      :  Data.Foldable
-- Copyright   :  Ross Paterson 2005
-- License     :  BSD-style (see the LICENSE file in the distribution)
--
15
-- Maintainer  :  libraries@haskell.org
16
17
18
19
20
-- Stability   :  experimental
-- Portability :  portable
--
-- Class of data structures that can be folded to a summary value.
--
dterei's avatar
dterei committed
21
-----------------------------------------------------------------------------
22
23

module Data.Foldable (
24
    Foldable(..),
25
    -- * Special biased folds
26
27
    foldrM,
    foldlM,
28
29
    -- * Folding actions
    -- ** Applicative actions
30
31
32
33
    traverse_,
    for_,
    sequenceA_,
    asum,
34
    -- ** Monadic actions
35
36
37
38
    mapM_,
    forM_,
    sequence_,
    msum,
39
    -- * Specialized folds
40
41
42
43
44
45
46
47
    concat,
    concatMap,
    and,
    or,
    any,
    all,
    maximumBy,
    minimumBy,
48
    -- * Searches
49
50
51
    notElem,
    find
    ) where
52

53
54
55
import Data.Bool
import Data.Either
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
65
66
                  foldlElems, foldrElems,
                  foldlElems', foldrElems',
                  foldl1Elems, foldr1Elems)
67
import GHC.Base hiding ( foldr )
68
import GHC.Generics
69
import GHC.Num  ( Num(..) )
70

71
72
infix  4 `elem`, `notElem`

73
74
75
76
77
78
79
80
-- | Data structures that can be folded.
--
-- For example, given a data type
--
-- > data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)
--
-- a suitable instance would be
--
Ross Paterson's avatar
Ross Paterson committed
81
-- > instance Foldable Tree where
82
83
84
85
86
-- >    foldMap f Empty = mempty
-- >    foldMap f (Leaf x) = f x
-- >    foldMap f (Node l k r) = foldMap f l `mappend` f k `mappend` foldMap f r
--
-- This is suitable even for abstract types, as the monoid is assumed
87
88
89
90
91
92
-- to satisfy the monoid laws.  Alternatively, one could define @foldr@:
--
-- > instance Foldable Tree where
-- >    foldr f z Empty = z
-- >    foldr f z (Leaf x) = f x z
-- >    foldr f z (Node l k r) = foldr f (f k (foldr f z r)) l
93
--
94
95
96
97
98
99
100
101
-- @Foldable@ instances are expected to satisfy the following laws:
--
-- > foldr f z t = appEndo (foldMap (Endo . f) t ) z
--
-- > foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z
--
-- > fold = foldMap id
--
102
103
-- > length = getSum . foldMap (Sum . const  1)
--
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
-- @sum@, @product@, @maximum@, and @minimum@ should all be essentially
-- equivalent to @foldMap@ forms, such as
--
-- > sum = getSum . foldMap Sum
--
-- but may be less defined.
--
-- If the type is also a 'Functor' instance, it should satisfy
--
-- > foldMap f = fold . fmap f
--
-- which implies that
--
-- > foldMap f . fmap g = foldMap (f . g)

119
class Foldable t where
120
121
    {-# MINIMAL foldMap | foldr #-}

122
123
124
125
126
127
128
    -- | Combine the elements of a structure using a monoid.
    fold :: Monoid m => t m -> m
    fold = foldMap id

    -- | Map each element of the structure to a monoid,
    -- and combine the results.
    foldMap :: Monoid m => (a -> m) -> t a -> m
129
130
    {-# INLINE foldMap #-}
    -- This INLINE allows more list functions to fuse. See Trac #9848.
131
    foldMap f = foldr (mappend . f) mempty
132
133
134
135
136
137

    -- | A variant of 'foldMap' that is strict in the accumulator.
    --
    -- @since 4.13.0.0
    foldMap' :: Monoid m => (a -> m) -> t a -> m
    foldMap' f = foldl' (\ acc a -> acc <> f a) mempty
138
139
140

    -- | Right-associative fold of a structure.
    --
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
    -- In the case of lists, 'foldr', when applied to a binary operator, a
    -- starting value (typically the right-identity of the operator), and a
    -- list, reduces the list using the binary operator, from right to left:
    --
    -- > foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)
    --
    -- Note that, since the head of the resulting expression is produced by
    -- an application of the operator to the first element of the list,
    -- 'foldr' can produce a terminating expression from an infinite list.
    --
    -- For a general 'Foldable' structure this should be semantically identical
    -- to,
    --
    -- @foldr f z = 'List.foldr' f z . 'toList'@
    --
156
    foldr :: (a -> b -> b) -> b -> t a -> b
157
    foldr f z t = appEndo (foldMap (Endo #. f) t) z
158

159
160
161
    -- | Right-associative fold of a structure, but with strict application of
    -- the operator.
    --
162
163
164
165
    foldr' :: (a -> b -> b) -> b -> t a -> b
    foldr' f z0 xs = foldl f' id xs z0
      where f' k x z = k $! f x z

166
167
    -- | Left-associative fold of a structure.
    --
168
169
170
171
172
173
174
175
176
177
178
179
180
    -- In the case of lists, 'foldl', when applied to a binary
    -- operator, a starting value (typically the left-identity of the operator),
    -- and a list, reduces the list using the binary operator, from left to
    -- right:
    --
    -- > foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn
    --
    -- Note that to produce the outermost application of the operator the
    -- entire input list must be traversed. This means that 'foldl'' will
    -- diverge if given an infinite list.
    --
    -- Also note that if you want an efficient left-fold, you probably want to
    -- use 'foldl'' instead of 'foldl'. The reason for this is that latter does
181
182
    -- not force the "inner" results (e.g. @z \`f\` x1@ in the above example)
    -- before applying them to the operator (e.g. to @(\`f\` x2)@). This results
183
184
185
186
187
188
189
190
    -- in a thunk chain @O(n)@ elements long, which then must be evaluated from
    -- the outside-in.
    --
    -- For a general 'Foldable' structure this should be semantically identical
    -- to,
    --
    -- @foldl f z = 'List.foldl' f z . 'toList'@
    --
191
    foldl :: (b -> a -> b) -> b -> t a -> b
192
    foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z
193
194
    -- There's no point mucking around with coercions here,
    -- because flip forces us to build a new function anyway.
195

196
197
198
199
200
201
202
203
204
205
206
207
    -- | Left-associative fold of a structure but with strict application of
    -- the operator.
    --
    -- This ensures that each step of the fold is forced to weak head normal
    -- form before being applied, avoiding the collection of thunks that would
    -- otherwise occur. This is often what you want to strictly reduce a finite
    -- list to a single, monolithic result (e.g. 'length').
    --
    -- For a general 'Foldable' structure this should be semantically identical
    -- to,
    --
    -- @foldl f z = 'List.foldl'' f z . 'toList'@
208
    --
209
    foldl' :: (b -> a -> b) -> b -> t a -> b
210
211
212
    foldl' f z0 xs = foldr f' id xs z0
      where f' x k z = k $! f z x

213
214
215
    -- | A variant of 'foldr' that has no base case,
    -- and thus may only be applied to non-empty structures.
    --
216
    -- @'foldr1' f = 'List.foldr1' f . 'toList'@
217
    foldr1 :: (a -> a -> a) -> t a -> a
Eric Seidel's avatar
Eric Seidel committed
218
    foldr1 f xs = fromMaybe (errorWithoutStackTrace "foldr1: empty structure")
219
220
                    (foldr mf Nothing xs)
      where
221
222
223
        mf x m = Just (case m of
                         Nothing -> x
                         Just y  -> f x y)
224
225
226
227

    -- | A variant of 'foldl' that has no base case,
    -- and thus may only be applied to non-empty structures.
    --
228
    -- @'foldl1' f = 'List.foldl1' f . 'toList'@
229
    foldl1 :: (a -> a -> a) -> t a -> a
Eric Seidel's avatar
Eric Seidel committed
230
    foldl1 f xs = fromMaybe (errorWithoutStackTrace "foldl1: empty structure")
231
232
                    (foldl mf Nothing xs)
      where
233
234
235
        mf m y = Just (case m of
                         Nothing -> y
                         Just x  -> f x y)
236

237
    -- | List of elements of a structure, from left to right.
238
    toList :: t a -> [a]
239
240
241
    {-# INLINE toList #-}
    toList t = build (\ c n -> foldr c n t)

242
243
244
    -- | Test whether the structure is empty. The default implementation is
    -- optimized for structures that are similar to cons-lists, because there
    -- is no general way to do better.
245
    null :: t a -> Bool
246
247
    null = foldr (\_ _ -> False) True

248
249
250
    -- | Returns the size/length of a finite structure as an 'Int'.  The
    -- default implementation is optimized for structures that are similar to
    -- cons-lists, because there is no general way to do better.
251
    length :: t a -> Int
252
253
    length = foldl' (\c _ -> c+1) 0

254
    -- | Does the element occur in the structure?
255
    elem :: Eq a => a -> t a -> Bool
256
257
258
    elem = any . (==)

    -- | The largest element of a non-empty structure.
259
    maximum :: forall a . Ord a => t a -> a
Eric Seidel's avatar
Eric Seidel committed
260
    maximum = fromMaybe (errorWithoutStackTrace "maximum: empty structure") .
261
       getMax . foldMap (Max #. (Just :: a -> Maybe a))
262
263

    -- | The least element of a non-empty structure.
264
    minimum :: forall a . Ord a => t a -> a
Eric Seidel's avatar
Eric Seidel committed
265
    minimum = fromMaybe (errorWithoutStackTrace "minimum: empty structure") .
266
       getMin . foldMap (Min #. (Just :: a -> Maybe a))
267
268
269

    -- | The 'sum' function computes the sum of the numbers of a structure.
    sum :: Num a => t a -> a
270
    sum = getSum #. foldMap Sum
271
272
273

    -- | The 'product' function computes the product of the numbers of a
    -- structure.
274
    product :: Num a => t a -> a
275
    product = getProduct #. foldMap Product
276
277
278

-- instances for Prelude types

279
-- | @since 2.01
280
instance Foldable Maybe where
281
282
    foldMap = maybe mempty

283
284
    foldr _ z Nothing = z
    foldr f z (Just x) = f x z
285

286
287
    foldl _ z Nothing = z
    foldl f z (Just x) = f z x
288

289
-- | @since 2.01
290
instance Foldable [] where
291
292
293
294
295
296
    elem    = List.elem
    foldl   = List.foldl
    foldl'  = List.foldl'
    foldl1  = List.foldl1
    foldr   = List.foldr
    foldr1  = List.foldr1
297
    length  = List.length
298
299
    maximum = List.maximum
    minimum = List.minimum
300
    null    = List.null
301
302
303
    product = List.product
    sum     = List.sum
    toList  = id
304

305
306
307
-- | @since 4.9.0.0
instance Foldable NonEmpty where
  foldr f z ~(a :| as) = f a (List.foldr f z as)
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
  foldl f z (a :| as) = List.foldl f (f z a) as
  foldl1 f (a :| as) = List.foldl f a as

  -- GHC isn't clever enough to transform the default definition
  -- into anything like this, so we'd end up shuffling a bunch of
  -- Maybes around.
  foldr1 f (p :| ps) = foldr go id ps p
    where
      go x r prev = f prev (r x)

  -- We used to say
  --
  --   length (_ :| as) = 1 + length as
  --
  -- but the default definition is better, counting from 1.
  --
  -- The default definition also works great for null and foldl'.
  -- As usual for cons lists, foldr' is basically hopeless.

327
328
329
330
  foldMap f ~(a :| as) = f a `mappend` foldMap f as
  fold ~(m :| ms) = m `mappend` fold ms
  toList ~(a :| as) = a : as

331
-- | @since 4.7.0.0
332
333
334
335
336
337
338
instance Foldable (Either a) where
    foldMap _ (Left _) = mempty
    foldMap f (Right y) = f y

    foldr _ z (Left _) = z
    foldr f z (Right y) = f y z

339
340
341
342
343
    length (Left _)  = 0
    length (Right _) = 1

    null             = isLeft

344
-- | @since 4.7.0.0
345
346
347
348
349
instance Foldable ((,) a) where
    foldMap f (_, y) = f y

    foldr f z (_, y) = f y z

350
-- | @since 4.8.0.0
351
instance Foldable (Array i) where
352
353
354
355
356
357
358
359
360
    foldr = foldrElems
    foldl = foldlElems
    foldl' = foldlElems'
    foldr' = foldrElems'
    foldl1 = foldl1Elems
    foldr1 = foldr1Elems
    toList = elems
    length = numElements
    null a = numElements a == 0
361

362
-- | @since 4.7.0.0
363
364
365
366
367
368
369
370
371
instance Foldable Proxy where
    foldMap _ _ = mempty
    {-# INLINE foldMap #-}
    fold _ = mempty
    {-# INLINE fold #-}
    foldr _ z _ = z
    {-# INLINE foldr #-}
    foldl _ z _ = z
    {-# INLINE foldl #-}
Eric Seidel's avatar
Eric Seidel committed
372
373
    foldl1 _ _ = errorWithoutStackTrace "foldl1: Proxy"
    foldr1 _ _ = errorWithoutStackTrace "foldr1: Proxy"
374
375
376
377
378
379
    length _   = 0
    null _     = True
    elem _ _   = False
    sum _      = 0
    product _  = 1

380
-- | @since 4.8.0.0
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
instance Foldable Dual where
    foldMap            = coerce

    elem               = (. getDual) #. (==)
    foldl              = coerce
    foldl'             = coerce
    foldl1 _           = getDual
    foldr f z (Dual x) = f x z
    foldr'             = foldr
    foldr1 _           = getDual
    length _           = 1
    maximum            = getDual
    minimum            = getDual
    null _             = False
    product            = getDual
    sum                = getDual
    toList (Dual x)    = [x]

399
-- | @since 4.8.0.0
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
instance Foldable Sum where
    foldMap            = coerce

    elem               = (. getSum) #. (==)
    foldl              = coerce
    foldl'             = coerce
    foldl1 _           = getSum
    foldr f z (Sum x)  = f x z
    foldr'             = foldr
    foldr1 _           = getSum
    length _           = 1
    maximum            = getSum
    minimum            = getSum
    null _             = False
    product            = getSum
    sum                = getSum
    toList (Sum x)     = [x]

418
-- | @since 4.8.0.0
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
instance Foldable Product where
    foldMap               = coerce

    elem                  = (. getProduct) #. (==)
    foldl                 = coerce
    foldl'                = coerce
    foldl1 _              = getProduct
    foldr f z (Product x) = f x z
    foldr'                = foldr
    foldr1 _              = getProduct
    length _              = 1
    maximum               = getProduct
    minimum               = getProduct
    null _                = False
    product               = getProduct
    sum                   = getProduct
    toList (Product x)    = [x]

437
-- | @since 4.8.0.0
438
439
440
instance Foldable First where
    foldMap f = foldMap f . getFirst

441
-- | @since 4.8.0.0
442
443
444
instance Foldable Last where
    foldMap f = foldMap f . getLast

445
446
447
448
-- | @since 4.12.0.0
instance (Foldable f) => Foldable (Alt f) where
    foldMap f = foldMap f . getAlt

chessai's avatar
chessai committed
449
450
451
452
-- | @since 4.12.0.0
instance (Foldable f) => Foldable (Ap f) where
    foldMap f = foldMap f . getAp

453
-- Instances for GHC.Generics
454
-- | @since 4.9.0.0
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
instance Foldable U1 where
    foldMap _ _ = mempty
    {-# INLINE foldMap #-}
    fold _ = mempty
    {-# INLINE fold #-}
    foldr _ z _ = z
    {-# INLINE foldr #-}
    foldl _ z _ = z
    {-# INLINE foldl #-}
    foldl1 _ _ = errorWithoutStackTrace "foldl1: U1"
    foldr1 _ _ = errorWithoutStackTrace "foldr1: U1"
    length _   = 0
    null _     = True
    elem _ _   = False
    sum _      = 0
    product _  = 1

472
-- | @since 4.9.0.0
473
deriving instance Foldable V1
474
475

-- | @since 4.9.0.0
476
deriving instance Foldable Par1
477
478

-- | @since 4.9.0.0
479
deriving instance Foldable f => Foldable (Rec1 f)
480
481

-- | @since 4.9.0.0
482
deriving instance Foldable (K1 i c)
483
484

-- | @since 4.9.0.0
485
deriving instance Foldable f => Foldable (M1 i c f)
486
487

-- | @since 4.9.0.0
488
deriving instance (Foldable f, Foldable g) => Foldable (f :+: g)
489
490

-- | @since 4.9.0.0
491
deriving instance (Foldable f, Foldable g) => Foldable (f :*: g)
492
493

-- | @since 4.9.0.0
494
deriving instance (Foldable f, Foldable g) => Foldable (f :.: g)
495
496

-- | @since 4.9.0.0
497
deriving instance Foldable UAddr
498
499

-- | @since 4.9.0.0
500
deriving instance Foldable UChar
501
502

-- | @since 4.9.0.0
503
deriving instance Foldable UDouble
504
505

-- | @since 4.9.0.0
506
deriving instance Foldable UFloat
507
508

-- | @since 4.9.0.0
509
deriving instance Foldable UInt
510
511

-- | @since 4.9.0.0
512
513
deriving instance Foldable UWord

514
515
516
517
-- Instances for Data.Ord
-- | @since 4.12.0.0
deriving instance Foldable Down

518
519
520
-- | Monadic fold over the elements of a structure,
-- associating to the right, i.e. from right to left.
foldrM :: (Foldable t, Monad m) => (a -> b -> m b) -> b -> t a -> m b
521
522
523
524
foldrM f z0 xs = foldl c return xs z0
  -- See Note [List fusion and continuations in 'c']
  where c k x z = f x z >>= k
        {-# INLINE c #-}
525
526
527

-- | Monadic fold over the elements of a structure,
-- associating to the left, i.e. from left to right.
528
foldlM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b
529
530
531
532
foldlM f z0 xs = foldr c return xs z0
  -- See Note [List fusion and continuations in 'c']
  where c x k z = f z x >>= k
        {-# INLINE c #-}
533

534
535
536
-- | Map each element of a structure to an action, evaluate these
-- actions from left to right, and ignore the results. For a version
-- that doesn't ignore the results see 'Data.Traversable.traverse'.
537
traverse_ :: (Foldable t, Applicative f) => (a -> f b) -> t a -> f ()
538
539
540
541
traverse_ f = foldr c (pure ())
  -- See Note [List fusion and continuations in 'c']
  where c x k = f x *> k
        {-# INLINE c #-}
542

543
544
545
546
547
548
549
550
-- | 'for_' is 'traverse_' with its arguments flipped. For a version
-- that doesn't ignore the results see 'Data.Traversable.for'.
--
-- >>> for_ [1..4] print
-- 1
-- 2
-- 3
-- 4
551
552
553
554
555
for_ :: (Foldable t, Applicative f) => t a -> (a -> f b) -> f ()
{-# INLINE for_ #-}
for_ = flip traverse_

-- | Map each element of a structure to a monadic action, evaluate
556
557
558
559
560
561
-- these actions from left to right, and ignore the results. For a
-- version that doesn't ignore the results see
-- 'Data.Traversable.mapM'.
--
-- As of base 4.8.0.0, 'mapM_' is just 'traverse_', specialized to
-- 'Monad'.
562
mapM_ :: (Foldable t, Monad m) => (a -> m b) -> t a -> m ()
563
564
565
566
mapM_ f = foldr c (return ())
  -- See Note [List fusion and continuations in 'c']
  where c x k = f x >> k
        {-# INLINE c #-}
567

568
569
570
571
-- | 'forM_' is 'mapM_' with its arguments flipped. For a version that
-- doesn't ignore the results see 'Data.Traversable.forM'.
--
-- As of base 4.8.0.0, 'forM_' is just 'for_', specialized to 'Monad'.
572
573
574
575
forM_ :: (Foldable t, Monad m) => t a -> (a -> m b) -> m ()
{-# INLINE forM_ #-}
forM_ = flip mapM_

576
577
578
-- | Evaluate each action in the structure from left to right, and
-- ignore the results. For a version that doesn't ignore the results
-- see 'Data.Traversable.sequenceA'.
579
sequenceA_ :: (Foldable t, Applicative f) => t (f a) -> f ()
580
581
582
583
sequenceA_ = foldr c (pure ())
  -- See Note [List fusion and continuations in 'c']
  where c m k = m *> k
        {-# INLINE c #-}
584
585

-- | Evaluate each monadic action in the structure from left to right,
586
587
588
589
590
-- and ignore the results. For a version that doesn't ignore the
-- results see 'Data.Traversable.sequence'.
--
-- As of base 4.8.0.0, 'sequence_' is just 'sequenceA_', specialized
-- to 'Monad'.
591
sequence_ :: (Foldable t, Monad m) => t (m a) -> m ()
592
593
594
595
sequence_ = foldr c (return ())
  -- See Note [List fusion and continuations in 'c']
  where c m k = m >> k
        {-# INLINE c #-}
596
597

-- | The sum of a collection of actions, generalizing 'concat'.
quchen's avatar
quchen committed
598
--
Simon Jakobi's avatar
Simon Jakobi committed
599
-- >>> asum [Just "Hello", Nothing, Just "World"]
quchen's avatar
quchen committed
600
-- Just "Hello"
601
602
603
604
605
asum :: (Foldable t, Alternative f) => t (f a) -> f a
{-# INLINE asum #-}
asum = foldr (<|>) empty

-- | The sum of a collection of actions, generalizing 'concat'.
606
-- As of base 4.8.0.0, 'msum' is just 'asum', specialized to 'MonadPlus'.
607
608
msum :: (Foldable t, MonadPlus m) => t (m a) -> m a
{-# INLINE msum #-}
609
msum = asum
610
611
612

-- | The concatenation of all the elements of a container of lists.
concat :: Foldable t => t [a] -> [a]
613
614
concat xs = build (\c n -> foldr (\x y -> foldr c y x) n xs)
{-# INLINE concat #-}
615
616
617
618

-- | Map a function over all the elements of a container and concatenate
-- the resulting lists.
concatMap :: Foldable t => (a -> [b]) -> t a -> [b]
619
620
621
622
concatMap f xs = build (\c n -> foldr (\x b -> foldr c b (f x)) n xs)
{-# INLINE concatMap #-}

-- These use foldr rather than foldMap to avoid repeated concatenation.
623
624
625
626
627

-- | 'and' returns the conjunction of a container of Bools.  For the
-- result to be 'True', the container must be finite; 'False', however,
-- results from a 'False' value finitely far from the left end.
and :: Foldable t => t Bool -> Bool
628
and = getAll #. foldMap All
629
630
631
632
633

-- | 'or' returns the disjunction of a container of Bools.  For the
-- result to be 'False', the container must be finite; 'True', however,
-- results from a 'True' value finitely far from the left end.
or :: Foldable t => t Bool -> Bool
634
or = getAny #. foldMap Any
635
636
637

-- | Determines whether any element of the structure satisfies the predicate.
any :: Foldable t => (a -> Bool) -> t a -> Bool
638
any p = getAny #. foldMap (Any #. p)
639
640
641

-- | Determines whether all elements of the structure satisfy the predicate.
all :: Foldable t => (a -> Bool) -> t a -> Bool
642
all p = getAll #. foldMap (All #. p)
643
644
645

-- | The largest element of a non-empty structure with respect to the
-- given comparison function.
646
647

-- See Note [maximumBy/minimumBy space usage]
648
maximumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a
649
maximumBy cmp = foldl1 max'
650
  where max' x y = case cmp x y of
Don Stewart's avatar
Don Stewart committed
651
652
                        GT -> x
                        _  -> y
653
654
655

-- | The least element of a non-empty structure with respect to the
-- given comparison function.
656
657

-- See Note [maximumBy/minimumBy space usage]
658
minimumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a
659
minimumBy cmp = foldl1 min'
660
  where min' x y = case cmp x y of
Don Stewart's avatar
Don Stewart committed
661
662
                        GT -> y
                        _  -> x
663
664
665
666
667
668
669
670
671

-- | 'notElem' is the negation of 'elem'.
notElem :: (Foldable t, Eq a) => a -> t a -> Bool
notElem x = not . elem x

-- | The 'find' function takes a predicate and a structure and returns
-- the leftmost element of the structure matching the predicate, or
-- 'Nothing' if there is no such element.
find :: Foldable t => (a -> Bool) -> t a -> Maybe a
672
find p = getFirst . foldMap (\ x -> First (if p x then Just x else Nothing))
673

674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
{-
Note [List fusion and continuations in 'c']
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Suppose we define
  mapM_ f = foldr ((>>) . f) (return ())
(this is the way it used to be).

Now suppose we want to optimise the call

  mapM_ <big> (build g)
    where
  g c n = ...(c x1 y1)...(c x2 y2)....n...

GHC used to proceed like this:

  mapM_ <big> (build g)

  = { Defintion of mapM_ }
    foldr ((>>) . <big>) (return ()) (build g)

  = { foldr/build rule }
    g ((>>) . <big>) (return ())

  = { Inline g }
    let c = (>>) . <big>
        n = return ()
    in ...(c x1 y1)...(c x2 y2)....n...

The trouble is that `c`, being big, will not be inlined.  And that can
be absolutely terrible for performance, as we saw in Trac #8763.

It's much better to define

  mapM_ f = foldr c (return ())
    where
      c x k = f x >> k
      {-# INLINE c #-}

Now we get
  mapM_ <big> (build g)

  = { inline mapM_ }
    foldr c (return ()) (build g)
      where c x k = f x >> k
            {-# INLINE c #-}
            f = <big>

Notice that `f` does not inline into the RHS of `c`,
because the INLINE pragma stops it; see
Note [Simplifying inside stable unfoldings] in SimplUtils.
Continuing:

  = { foldr/build rule }
    g c (return ())
      where ...
         c x k = f x >> k
         {-# INLINE c #-}
            f = <big>

  = { inline g }
    ...(c x1 y1)...(c x2 y2)....n...
      where c x k = f x >> k
            {-# INLINE c #-}
            f = <big>
            n = return ()

      Now, crucially, `c` does inline

  = { inline c }
    ...(f x1 >> y1)...(f x2 >> y2)....n...
      where f = <big>
            n = return ()

And all is well!  The key thing is that the fragment
`(f x1 >> y1)` is inlined into the body of the builder
`g`.
-}

752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
{-
Note [maximumBy/minimumBy space usage]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
When the type signatures of maximumBy and minimumBy were generalized to work
over any Foldable instance (instead of just lists), they were defined using
foldr1. This was problematic for space usage, as the semantics of maximumBy
and minimumBy essentially require that they examine every element of the
data structure. Using foldr1 to examine every element results in space usage
proportional to the size of the data structure. For the common case of lists,
this could be particularly bad (see Trac #10830).

For the common case of lists, switching the implementations of maximumBy and
minimumBy to foldl1 solves the issue, as GHC's strictness analysis can then
make these functions only use O(1) stack space. It is perhaps not the optimal
way to fix this problem, as there are other conceivable data structures
(besides lists) which might benefit from specialized implementations for
maximumBy and minimumBy (see
https://ghc.haskell.org/trac/ghc/ticket/10830#comment:26 for a further
discussion). But using foldl1 is at least always better than using foldr1, so
GHC has chosen to adopt that approach for now.
-}