{-# LANGUAGE DeriveFoldable #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE NoImplicitPrelude #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE StandaloneDeriving #-}
{-# LANGUAGE Trustworthy #-}
{-# LANGUAGE TypeOperators #-}

-----------------------------------------------------------------------------
-- |
-- Module      :  Data.Foldable
-- Copyright   :  Ross Paterson 2005
-- License     :  BSD-style (see the LICENSE file in the distribution)
--
-- Maintainer  :  libraries@haskell.org
-- Stability   :  experimental
-- Portability :  portable
--
-- Class of data structures that can be folded to a summary value.
--
-----------------------------------------------------------------------------

module Data.Foldable (
    Foldable(..),
    -- * Special biased folds
    foldrM,
    foldlM,
    -- * Folding actions
    -- ** Applicative actions
    traverse_,
    for_,
    sequenceA_,
    asum,
    -- ** Monadic actions
    mapM_,
    forM_,
    sequence_,
    msum,
    -- * Specialized folds
    concat,
    concatMap,
    and,
    or,
    any,
    all,
    maximumBy,
    minimumBy,
    -- * Searches
    notElem,
    find
    ) where

import Data.Bool
import Data.Either
import Data.Eq
import Data.Functor.Utils (Max(..), Min(..), (#.))
import qualified GHC.List as List
import Data.Maybe
import Data.Monoid
import Data.Ord
import Data.Proxy

import GHC.Arr  ( Array(..), elems, numElements,
                  foldlElems, foldrElems,
                  foldlElems', foldrElems',
                  foldl1Elems, foldr1Elems)
import GHC.Base hiding ( foldr )
import GHC.Generics
import GHC.Num  ( Num(..) )

infix  4 `elem`, `notElem`

-- | 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
--
-- > instance Foldable Tree where
-- >    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
-- 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
--
-- @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
--
-- > length = getSum . foldMap (Sum . const  1)
--
-- @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)

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

    -- | Combine the elements of a structure using a monoid.
    --
    -- ==== __Examples__
    --
    -- Basic usage:
    --
    -- >>> fold [[1, 2, 3], [4, 5], [6], []]
    -- [1,2,3,4,5,6]
    --
    -- >>> fold [Sum 1, Sum 3, Sum 5]
    -- Sum {getSum = 9}
    --
    -- Infinite structures never terminate:
    --
    -- >>> fold (repeat Nothing)
    -- * Hangs forever *
    fold :: Monoid m => t m -> m
    fold = (m -> m) -> t m -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
Evidence bound by a type signature of the constraint type Monoid m
Evidence bound by a type signature of the constraint type Foldable t
foldMap m -> m
forall a. a -> a
id

    -- | Map each element of the structure to a monoid,
    -- and combine the results.
    --
    -- ==== __Examples__
    --
    -- Basic usage:
    --
    -- >>> foldMap Sum [1, 3, 5]
    -- Sum {getSum = 9}
    --
    -- >>> foldMap Product [1, 3, 5]
    -- Product {getProduct = 15}
    --
    -- >>> foldMap (replicate 3) [1, 2, 3]
    -- [1,1,1,2,2,2,3,3,3]
    --
    -- Infinite structures never terminate:
    --
    -- >>> foldMap Sum [1..]
    -- * Hangs forever *
    foldMap :: Monoid m => (a -> m) -> t a -> m
    {-# INLINE foldMap #-}
    -- This INLINE allows more list functions to fuse. See #9848.
    foldMap a -> m
f = (a -> m -> m) -> m -> t a -> m
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Evidence bound by a type signature of the constraint type Foldable t
foldr (m -> m -> m
forall a. Monoid a => a -> a -> a
Evidence bound by a type signature of the constraint type Monoid m
mappend (m -> m -> m) -> (a -> m) -> a -> m -> m
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> m
f) m
forall a. Monoid a => a
Evidence bound by a type signature of the constraint type Monoid m
mempty

    -- | A variant of 'foldMap' that is strict in the accumulator.
    --
    -- @since 4.13.0.0
    foldMap' :: Monoid m => (a -> m) -> t a -> m
    foldMap' a -> m
f = (m -> a -> m) -> m -> t a -> m
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
Evidence bound by a type signature of the constraint type Foldable t
foldl' (\ m
acc a
a -> m
acc m -> m -> m
forall a. Semigroup a => a -> a -> a
External instance of the constraint type forall a. Monoid a => Semigroup a
Evidence bound by a type signature of the constraint type Monoid m
<> a -> m
f a
a) m
forall a. Monoid a => a
Evidence bound by a type signature of the constraint type Monoid m
mempty

    -- | Right-associative fold of a structure.
    --
    -- 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'@
    --
    -- ==== __Examples__
    --
    -- Basic usage:
    --
    -- >>> foldr (||) False [False, True, False]
    -- True
    --
    -- >>> foldr (||) False []
    -- False
    --
    -- >>> foldr (\nextChar reversedString -> reversedString ++ [nextChar]) "foo" ['a', 'b', 'c', 'd']
    -- "foodcba"
    --
    -- ===== Infinite structures
    --
    -- ⚠️ Applying 'foldr' to infinite structures usually doesn't terminate.
    --
    -- It may still terminate in one of the following conditions:
    --
    -- * the folding function is short-circuiting
    -- * the folding function is lazy on its second argument
    --
    -- ====== Short-circuiting
    --
    -- '(||)' short-circuits on 'True' values, so the following terminates because there is a 'True' value finitely far from the left side:
    --
    -- >>> foldr (||) False (True : repeat False)
    -- True
    --
    -- But the following doesn't terminate:
    --
    -- >>> foldr (||) False (repeat False ++ [True])
    -- * Hangs forever *
    --
    -- ====== Laziness in the second argument
    --
    -- Applying 'foldr' to infinite structures terminates when the folding function is lazy on its second argument:
    --
    -- >>> foldr (\nextElement accumulator -> nextElement : fmap (+3) accumulator) [42] (repeat 1)
    -- [1,4,7,10,13,16,19,22,25,28,31,34,37,40,43...
    --
    -- >>> take 5 $ foldr (\nextElement accumulator -> nextElement : fmap (+3) accumulator) [42] (repeat 1)
    -- [1,4,7,10,13]
    foldr :: (a -> b -> b) -> b -> t a -> b
    foldr a -> b -> b
f b
z t a
t = Endo b -> b -> b
forall a. Endo a -> a -> a
appEndo ((a -> Endo b) -> t a -> Endo b
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
External instance of the constraint type forall a. Monoid (Endo a)
Evidence bound by a type signature of the constraint type Foldable t
foldMap ((b -> b) -> Endo b
forall a. (a -> a) -> Endo a
Endo ((b -> b) -> Endo b) -> (a -> b -> b) -> a -> Endo b
forall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c
#. a -> b -> b
f) t a
t) b
z

    -- | Right-associative fold of a structure, but with strict application of
    -- the operator.
    --
    -- @since 4.6.0.0
    foldr' :: (a -> b -> b) -> b -> t a -> b
    foldr' a -> b -> b
f b
z0 t a
xs = ((b -> b) -> a -> b -> b) -> (b -> b) -> t a -> b -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
Evidence bound by a type signature of the constraint type Foldable t
foldl (b -> b) -> a -> b -> b
forall {b}. (b -> b) -> a -> b -> b
f' b -> b
forall a. a -> a
id t a
xs b
z0
      where f' :: (b -> b) -> a -> b -> b
f' b -> b
k a
x b
z = b -> b
k (b -> b) -> b -> b
forall a b. (a -> b) -> a -> b
$! a -> b -> b
f a
x b
z

    -- | Left-associative fold of a structure.
    --
    -- 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
    -- 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
    -- in a thunk chain \(\mathcal{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'@
    --
    -- ==== __Examples__
    --
    -- Basic usage:
    --
    -- >>> foldl (+) 42 (Node (Leaf 1) 3 (Node Empty 4 (Leaf 2)))
    -- 52
    --
    -- >>> foldl (+) 42 Empty
    -- 42
    --
    -- >>> foldl (\string nextElement -> nextElement : string) "abcd" (Node (Leaf 'd') 'e' (Node Empty 'f' (Leaf 'g')))
    -- "gfedabcd"
    --
    -- Left-folding infinite structures never terminates:
    --
    -- >>> let infiniteNode = Node Empty 1 infiniteNode in foldl (+) 42 infiniteNode
    -- * Hangs forever *
    --
    -- Evaluating the head of the result (when applicable) does not terminate, unlike 'foldr':
    --
    -- >>> let infiniteNode = Node Empty 'd' infiniteNode in take 5 (foldl (\string nextElement -> nextElement : string) "abc" infiniteNode)
    -- * Hangs forever *
    foldl :: (b -> a -> b) -> b -> t a -> b
    foldl b -> a -> b
f b
z t a
t = Endo b -> b -> b
forall a. Endo a -> a -> a
appEndo (Dual (Endo b) -> Endo b
forall a. Dual a -> a
getDual ((a -> Dual (Endo b)) -> t a -> Dual (Endo b)
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
External instance of the constraint type forall a. Monoid a => Monoid (Dual a)
External instance of the constraint type forall a. Monoid (Endo a)
Evidence bound by a type signature of the constraint type Foldable t
foldMap (Endo b -> Dual (Endo b)
forall a. a -> Dual a
Dual (Endo b -> Dual (Endo b)) -> (a -> Endo b) -> a -> Dual (Endo b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (b -> b) -> Endo b
forall a. (a -> a) -> Endo a
Endo ((b -> b) -> Endo b) -> (a -> b -> b) -> a -> Endo b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (b -> a -> b) -> a -> b -> b
forall a b c. (a -> b -> c) -> b -> a -> c
flip b -> a -> b
f) t a
t)) b
z
    -- There's no point mucking around with coercions here,
    -- because flip forces us to build a new function anyway.

    -- | 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'@
    --
    -- @since 4.6.0.0
    foldl' :: (b -> a -> b) -> b -> t a -> b
    foldl' b -> a -> b
f b
z0 t a
xs = (a -> (b -> b) -> b -> b) -> (b -> b) -> t a -> b -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Evidence bound by a type signature of the constraint type Foldable t
foldr a -> (b -> b) -> b -> b
forall {b}. a -> (b -> b) -> b -> b
f' b -> b
forall a. a -> a
id t a
xs b
z0
      where f' :: a -> (b -> b) -> b -> b
f' a
x b -> b
k b
z = b -> b
k (b -> b) -> b -> b
forall a b. (a -> b) -> a -> b
$! b -> a -> b
f b
z a
x

    -- | A variant of 'foldr' that has no base case,
    -- and thus may only be applied to non-empty structures.
    --
    -- ⚠️ This function is non-total and will raise a runtime exception if the structure happens to be empty.
    --
    -- ==== __Examples__
    --
    -- Basic usage:
    --
    -- >>> foldr1 (+) [1..4]
    -- 10
    --
    -- >>> foldr1 (+) []
    -- Exception: Prelude.foldr1: empty list
    --
    -- >>> foldr1 (+) Nothing
    -- *** Exception: foldr1: empty structure
    --
    -- >>> foldr1 (-) [1..4]
    -- -2
    --
    -- >>> foldr1 (&&) [True, False, True, True]
    -- False
    --
    -- >>> foldr1 (||) [False, False, True, True]
    -- True
    --
    -- >>> foldr1 (+) [1..]
    -- * Hangs forever *
    foldr1 :: (a -> a -> a) -> t a -> a
    foldr1 a -> a -> a
f t a
xs = a -> Maybe a -> a
forall a. a -> Maybe a -> a
fromMaybe ([Char] -> a
forall a. [Char] -> a
errorWithoutStackTrace [Char]
"foldr1: empty structure")
                    ((a -> Maybe a -> Maybe a) -> Maybe a -> t a -> Maybe a
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Evidence bound by a type signature of the constraint type Foldable t
foldr a -> Maybe a -> Maybe a
mf Maybe a
forall a. Maybe a
Nothing t a
xs)
      where
        mf :: a -> Maybe a -> Maybe a
mf a
x Maybe a
m = a -> Maybe a
forall a. a -> Maybe a
Just (case Maybe a
m of
                         Maybe a
Nothing -> a
x
                         Just a
y  -> a -> a -> a
f a
x a
y)

    -- | A variant of 'foldl' that has no base case,
    -- and thus may only be applied to non-empty structures.
    --
    -- ⚠️ This function is non-total and will raise a runtime exception if the structure happens to be empty.
    --
    -- @'foldl1' f = 'List.foldl1' f . 'toList'@
    --
    -- ==== __Examples__
    --
    -- Basic usage:
    --
    -- >>> foldl1 (+) [1..4]
    -- 10
    --
    -- >>> foldl1 (+) []
    -- *** Exception: Prelude.foldl1: empty list
    --
    -- >>> foldl1 (+) Nothing
    -- *** Exception: foldl1: empty structure
    --
    -- >>> foldl1 (-) [1..4]
    -- -8
    --
    -- >>> foldl1 (&&) [True, False, True, True]
    -- False
    --
    -- >>> foldl1 (||) [False, False, True, True]
    -- True
    --
    -- >>> foldl1 (+) [1..]
    -- * Hangs forever *
    foldl1 :: (a -> a -> a) -> t a -> a
    foldl1 a -> a -> a
f t a
xs = a -> Maybe a -> a
forall a. a -> Maybe a -> a
fromMaybe ([Char] -> a
forall a. [Char] -> a
errorWithoutStackTrace [Char]
"foldl1: empty structure")
                    ((Maybe a -> a -> Maybe a) -> Maybe a -> t a -> Maybe a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
Evidence bound by a type signature of the constraint type Foldable t
foldl Maybe a -> a -> Maybe a
mf Maybe a
forall a. Maybe a
Nothing t a
xs)
      where
        mf :: Maybe a -> a -> Maybe a
mf Maybe a
m a
y = a -> Maybe a
forall a. a -> Maybe a
Just (case Maybe a
m of
                         Maybe a
Nothing -> a
y
                         Just a
x  -> a -> a -> a
f a
x a
y)

    -- | List of elements of a structure, from left to right.
    --
    -- ==== __Examples__
    --
    -- Basic usage:
    --
    -- >>> toList Nothing
    -- []
    --
    -- >>> toList (Just 42)
    -- [42]
    --
    -- >>> toList (Left "foo")
    -- []
    --
    -- >>> toList (Node (Leaf 5) 17 (Node Empty 12 (Leaf 8)))
    -- [5,17,12,8]
    --
    -- For lists, 'toList' is the identity:
    --
    -- >>> toList [1, 2, 3]
    -- [1,2,3]
    --
    -- @since 4.8.0.0
    toList :: t a -> [a]
    {-# INLINE toList #-}
    toList t a
t = (forall b. (a -> b -> b) -> b -> b) -> [a]
forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
build (\ a -> b -> b
c b
n -> (a -> b -> b) -> b -> t a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Evidence bound by a type signature of the constraint type Foldable t
foldr a -> b -> b
c b
n t a
t)

    -- | 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.
    --
    -- ==== __Examples__
    --
    -- Basic usage:
    --
    -- >>> null []
    -- True
    --
    -- >>> null [1]
    -- False
    --
    -- 'null' terminates even for infinite structures:
    --
    -- >>> null [1..]
    -- False
    --
    -- @since 4.8.0.0
    null :: t a -> Bool
    null = (a -> Bool -> Bool) -> Bool -> t a -> Bool
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Evidence bound by a type signature of the constraint type Foldable t
foldr (\a
_ Bool
_ -> Bool
False) Bool
True

    -- | 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.
    --
    -- ==== __Examples__
    --
    -- Basic usage:
    --
    -- >>> length []
    -- 0
    --
    -- >>> length ['a', 'b', 'c']
    -- 3
    -- >>> length [1..]
    -- * Hangs forever *
    --
    -- @since 4.8.0.0
    length :: t a -> Int
    length = (Int -> a -> Int) -> Int -> t a -> Int
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
Evidence bound by a type signature of the constraint type Foldable t
foldl' (\Int
c a
_ -> Int
cInt -> Int -> Int
forall a. Num a => a -> a -> a
External instance of the constraint type Num Int
+Int
1) Int
0

    -- | Does the element occur in the structure?
    --
    -- Note: 'elem' is often used in infix form.
    --
    -- ==== __Examples__
    --
    -- Basic usage:
    --
    -- >>> 3 `elem` []
    -- False
    --
    -- >>> 3 `elem` [1,2]
    -- False
    --
    -- >>> 3 `elem` [1,2,3,4,5]
    -- True
    --
    -- For infinite structures, 'elem' terminates if the value exists at a
    -- finite distance from the left side of the structure:
    --
    -- >>> 3 `elem` [1..]
    -- True
    --
    -- >>> 3 `elem` ([4..] ++ [3])
    -- * Hangs forever *
    --
    -- @since 4.8.0.0
    elem :: Eq a => a -> t a -> Bool
    elem = (a -> Bool) -> t a -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
Evidence bound by a type signature of the constraint type Foldable t
any ((a -> Bool) -> t a -> Bool)
-> (a -> a -> Bool) -> a -> t a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> a -> Bool
forall a. Eq a => a -> a -> Bool
Evidence bound by a type signature of the constraint type Eq a
(==)

    -- | The largest element of a non-empty structure.
    --
    -- ⚠️ This function is non-total and will raise a runtime exception if the structure happens to be empty.
    --
    -- ==== __Examples__
    --
    -- Basic usage:
    --
    -- >>> maximum [1..10]
    -- 10
    --
    -- >>> maximum []
    -- *** Exception: Prelude.maximum: empty list
    --
    -- >>> maximum Nothing
    -- *** Exception: maximum: empty structure
    --
    -- @since 4.8.0.0
    maximum :: forall a . Ord a => t a -> a
    maximum = a -> Maybe a -> a
forall a. a -> Maybe a -> a
fromMaybe ([Char] -> a
forall a. [Char] -> a
errorWithoutStackTrace [Char]
"maximum: empty structure") (Maybe a -> a) -> (t a -> Maybe a) -> t a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
       Max a -> Maybe a
forall a. Max a -> Maybe a
getMax (Max a -> Maybe a) -> (t a -> Max a) -> t a -> Maybe a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Max a) -> t a -> Max a
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
External instance of the constraint type forall a. Ord a => Monoid (Max a)
Evidence bound by a type signature of the constraint type Ord a
Evidence bound by a type signature of the constraint type Foldable t
foldMap (Maybe a -> Max a
forall a. Maybe a -> Max a
Max (Maybe a -> Max a) -> (a -> Maybe a) -> a -> Max a
forall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c
#. (a -> Maybe a
forall a. a -> Maybe a
Just :: a -> Maybe a))

    -- | The least element of a non-empty structure.
    --
    -- ⚠️ This function is non-total and will raise a runtime exception if the structure happens to be empty
    --
    -- ==== __Examples__
    --
    -- Basic usage:
    --
    -- >>> minimum [1..10]
    -- 1
    --
    -- >>> minimum []
    -- *** Exception: Prelude.minimum: empty list
    --
    -- >>> minimum Nothing
    -- *** Exception: minimum: empty structure
    --
    -- @since 4.8.0.0
    minimum :: forall a . Ord a => t a -> a
    minimum = a -> Maybe a -> a
forall a. a -> Maybe a -> a
fromMaybe ([Char] -> a
forall a. [Char] -> a
errorWithoutStackTrace [Char]
"minimum: empty structure") (Maybe a -> a) -> (t a -> Maybe a) -> t a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
       Min a -> Maybe a
forall a. Min a -> Maybe a
getMin (Min a -> Maybe a) -> (t a -> Min a) -> t a -> Maybe a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Min a) -> t a -> Min a
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
External instance of the constraint type forall a. Ord a => Monoid (Min a)
Evidence bound by a type signature of the constraint type Ord a
Evidence bound by a type signature of the constraint type Foldable t
foldMap (Maybe a -> Min a
forall a. Maybe a -> Min a
Min (Maybe a -> Min a) -> (a -> Maybe a) -> a -> Min a
forall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c
#. (a -> Maybe a
forall a. a -> Maybe a
Just :: a -> Maybe a))

    -- | The 'sum' function computes the sum of the numbers of a structure.
    --
    -- ==== __Examples__
    --
    -- Basic usage:
    --
    -- >>> sum []
    -- 0
    --
    -- >>> sum [42]
    -- 42
    --
    -- >>> sum [1..10]
    -- 55
    --
    -- >>> sum [4.1, 2.0, 1.7]
    -- 7.8
    --
    -- >>> sum [1..]
    -- * Hangs forever *
    --
    -- @since 4.8.0.0
    sum :: Num a => t a -> a
    sum = Sum a -> a
forall a. Sum a -> a
getSum (Sum a -> a) -> (t a -> Sum a) -> t a -> a
forall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c
#. (a -> Sum a) -> t a -> Sum a
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
External instance of the constraint type forall a. Num a => Monoid (Sum a)
Evidence bound by a type signature of the constraint type Num a
Evidence bound by a type signature of the constraint type Foldable t
foldMap a -> Sum a
forall a. a -> Sum a
Sum

    -- | The 'product' function computes the product of the numbers of a
    -- structure.
    --
    -- ==== __Examples__
    --
    -- Basic usage:
    --
    -- >>> product []
    -- 1
    --
    -- >>> product [42]
    -- 42
    --
    -- >>> product [1..10]
    -- 3628800
    --
    -- >>> product [4.1, 2.0, 1.7]
    -- 13.939999999999998
    --
    -- >>> product [1..]
    -- * Hangs forever *
    --
    -- @since 4.8.0.0
    product :: Num a => t a -> a
    product = Product a -> a
forall a. Product a -> a
getProduct (Product a -> a) -> (t a -> Product a) -> t a -> a
forall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c
#. (a -> Product a) -> t a -> Product a
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
External instance of the constraint type forall a. Num a => Monoid (Product a)
Evidence bound by a type signature of the constraint type Num a
Evidence bound by a type signature of the constraint type Foldable t
foldMap a -> Product a
forall a. a -> Product a
Product

-- instances for Prelude types

-- | @since 2.01
instance Foldable Maybe where
    foldMap :: (a -> m) -> Maybe a -> m
foldMap = m -> (a -> m) -> Maybe a -> m
forall b a. b -> (a -> b) -> Maybe a -> b
maybe m
forall a. Monoid a => a
Evidence bound by a type signature of the constraint type Monoid m
mempty

    foldr :: (a -> b -> b) -> b -> Maybe a -> b
foldr a -> b -> b
_ b
z Maybe a
Nothing = b
z
    foldr a -> b -> b
f b
z (Just a
x) = a -> b -> b
f a
x b
z

    foldl :: (b -> a -> b) -> b -> Maybe a -> b
foldl b -> a -> b
_ b
z Maybe a
Nothing = b
z
    foldl b -> a -> b
f b
z (Just a
x) = b -> a -> b
f b
z a
x

-- | @since 2.01
instance Foldable [] where
    elem :: a -> [a] -> Bool
elem    = a -> [a] -> Bool
forall a. Eq a => a -> [a] -> Bool
Evidence bound by a type signature of the constraint type Eq a
List.elem
    foldl :: (b -> a -> b) -> b -> [a] -> b
foldl   = (b -> a -> b) -> b -> [a] -> b
forall a b. (b -> a -> b) -> b -> [a] -> b
List.foldl
    foldl' :: (b -> a -> b) -> b -> [a] -> b
foldl'  = (b -> a -> b) -> b -> [a] -> b
forall a b. (b -> a -> b) -> b -> [a] -> b
List.foldl'
    foldl1 :: (a -> a -> a) -> [a] -> a
foldl1  = (a -> a -> a) -> [a] -> a
forall a. (a -> a -> a) -> [a] -> a
List.foldl1
    foldr :: (a -> b -> b) -> b -> [a] -> b
foldr   = (a -> b -> b) -> b -> [a] -> b
forall a b. (a -> b -> b) -> b -> [a] -> b
List.foldr
    foldr1 :: (a -> a -> a) -> [a] -> a
foldr1  = (a -> a -> a) -> [a] -> a
forall a. (a -> a -> a) -> [a] -> a
List.foldr1
    length :: [a] -> Int
length  = [a] -> Int
forall a. [a] -> Int
List.length
    maximum :: [a] -> a
maximum = [a] -> a
forall a. Ord a => [a] -> a
Evidence bound by a type signature of the constraint type Ord a
List.maximum
    minimum :: [a] -> a
minimum = [a] -> a
forall a. Ord a => [a] -> a
Evidence bound by a type signature of the constraint type Ord a
List.minimum
    null :: [a] -> Bool
null    = [a] -> Bool
forall a. [a] -> Bool
List.null
    product :: [a] -> a
product = [a] -> a
forall a. Num a => [a] -> a
Evidence bound by a type signature of the constraint type Num a
List.product
    sum :: [a] -> a
sum     = [a] -> a
forall a. Num a => [a] -> a
Evidence bound by a type signature of the constraint type Num a
List.sum
    toList :: [a] -> [a]
toList  = [a] -> [a]
forall a. a -> a
id

-- | @since 4.9.0.0
instance Foldable NonEmpty where
  foldr :: (a -> b -> b) -> b -> NonEmpty a -> b
foldr a -> b -> b
f b
z ~(a
a :| [a]
as) = a -> b -> b
f a
a ((a -> b -> b) -> b -> [a] -> b
forall a b. (a -> b -> b) -> b -> [a] -> b
List.foldr a -> b -> b
f b
z [a]
as)
  foldl :: (b -> a -> b) -> b -> NonEmpty a -> b
foldl b -> a -> b
f b
z (a
a :| [a]
as) = (b -> a -> b) -> b -> [a] -> b
forall a b. (b -> a -> b) -> b -> [a] -> b
List.foldl b -> a -> b
f (b -> a -> b
f b
z a
a) [a]
as
  foldl1 :: (a -> a -> a) -> NonEmpty a -> a
foldl1 a -> a -> a
f (a
a :| [a]
as) = (a -> a -> a) -> a -> [a] -> a
forall a b. (b -> a -> b) -> b -> [a] -> b
List.foldl a -> a -> a
f a
a [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 :: (a -> a -> a) -> NonEmpty a -> a
foldr1 a -> a -> a
f (a
p :| [a]
ps) = (a -> (a -> a) -> a -> a) -> (a -> a) -> [a] -> a -> a
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Instance of class: Foldable of the constraint type Foldable []
foldr a -> (a -> a) -> a -> a
forall {t}. t -> (t -> a) -> a -> a
go a -> a
forall a. a -> a
id [a]
ps a
p
    where
      go :: t -> (t -> a) -> a -> a
go t
x t -> a
r a
prev = a -> a -> a
f a
prev (t -> a
r t
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.

  foldMap :: (a -> m) -> NonEmpty a -> m
foldMap a -> m
f ~(a
a :| [a]
as) = a -> m
f a
a m -> m -> m
forall a. Monoid a => a -> a -> a
Evidence bound by a type signature of the constraint type Monoid m
`mappend` (a -> m) -> [a] -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
Evidence bound by a type signature of the constraint type Monoid m
Instance of class: Foldable of the constraint type Foldable []
foldMap a -> m
f [a]
as
  fold :: NonEmpty m -> m
fold ~(m
m :| [m]
ms) = m
m m -> m -> m
forall a. Monoid a => a -> a -> a
Evidence bound by a type signature of the constraint type Monoid m
`mappend` [m] -> m
forall (t :: * -> *) m. (Foldable t, Monoid m) => t m -> m
Evidence bound by a type signature of the constraint type Monoid m
Instance of class: Foldable of the constraint type Foldable []
fold [m]
ms
  toList :: NonEmpty a -> [a]
toList ~(a
a :| [a]
as) = a
a a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
as

-- | @since 4.7.0.0
instance Foldable (Either a) where
    foldMap :: (a -> m) -> Either a a -> m
foldMap a -> m
_ (Left a
_) = m
forall a. Monoid a => a
Evidence bound by a type signature of the constraint type Monoid m
mempty
    foldMap a -> m
f (Right a
y) = a -> m
f a
y

    foldr :: (a -> b -> b) -> b -> Either a a -> b
foldr a -> b -> b
_ b
z (Left a
_) = b
z
    foldr a -> b -> b
f b
z (Right a
y) = a -> b -> b
f a
y b
z

    length :: Either a a -> Int
length (Left a
_)  = Int
0
    length (Right a
_) = Int
1

    null :: Either a a -> Bool
null             = Either a a -> Bool
forall a a. Either a a -> Bool
isLeft

-- | @since 4.7.0.0
instance Foldable ((,) a) where
    foldMap :: (a -> m) -> (a, a) -> m
foldMap a -> m
f (a
_, a
y) = a -> m
f a
y

    foldr :: (a -> b -> b) -> b -> (a, a) -> b
foldr a -> b -> b
f b
z (a
_, a
y) = a -> b -> b
f a
y b
z
    length :: (a, a) -> Int
length (a, a)
_  = Int
1
    null :: (a, a) -> Bool
null (a, a)
_ = Bool
False

-- | @since 4.8.0.0
instance Foldable (Array i) where
    foldr :: (a -> b -> b) -> b -> Array i a -> b
foldr = (a -> b -> b) -> b -> Array i a -> b
forall a b i. (a -> b -> b) -> b -> Array i a -> b
foldrElems
    foldl :: (b -> a -> b) -> b -> Array i a -> b
foldl = (b -> a -> b) -> b -> Array i a -> b
forall b a i. (b -> a -> b) -> b -> Array i a -> b
foldlElems
    foldl' :: (b -> a -> b) -> b -> Array i a -> b
foldl' = (b -> a -> b) -> b -> Array i a -> b
forall b a i. (b -> a -> b) -> b -> Array i a -> b
foldlElems'
    foldr' :: (a -> b -> b) -> b -> Array i a -> b
foldr' = (a -> b -> b) -> b -> Array i a -> b
forall a b i. (a -> b -> b) -> b -> Array i a -> b
foldrElems'
    foldl1 :: (a -> a -> a) -> Array i a -> a
foldl1 = (a -> a -> a) -> Array i a -> a
forall a i. (a -> a -> a) -> Array i a -> a
foldl1Elems
    foldr1 :: (a -> a -> a) -> Array i a -> a
foldr1 = (a -> a -> a) -> Array i a -> a
forall a i. (a -> a -> a) -> Array i a -> a
foldr1Elems
    toList :: Array i a -> [a]
toList = Array i a -> [a]
forall i a. Array i a -> [a]
elems
    length :: Array i a -> Int
length = Array i a -> Int
forall i a. Array i a -> Int
numElements
    null :: Array i a -> Bool
null Array i a
a = Array i a -> Int
forall i a. Array i a -> Int
numElements Array i a
a Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
External instance of the constraint type Eq Int
== Int
0

-- | @since 4.7.0.0
instance Foldable Proxy where
    foldMap :: (a -> m) -> Proxy a -> m
foldMap a -> m
_ Proxy a
_ = m
forall a. Monoid a => a
Evidence bound by a type signature of the constraint type Monoid m
mempty
    {-# INLINE foldMap #-}
    fold :: Proxy m -> m
fold Proxy m
_ = m
forall a. Monoid a => a
Evidence bound by a type signature of the constraint type Monoid m
mempty
    {-# INLINE fold #-}
    foldr :: (a -> b -> b) -> b -> Proxy a -> b
foldr a -> b -> b
_ b
z Proxy a
_ = b
z
    {-# INLINE foldr #-}
    foldl :: (b -> a -> b) -> b -> Proxy a -> b
foldl b -> a -> b
_ b
z Proxy a
_ = b
z
    {-# INLINE foldl #-}
    foldl1 :: (a -> a -> a) -> Proxy a -> a
foldl1 a -> a -> a
_ Proxy a
_ = [Char] -> a
forall a. [Char] -> a
errorWithoutStackTrace [Char]
"foldl1: Proxy"
    foldr1 :: (a -> a -> a) -> Proxy a -> a
foldr1 a -> a -> a
_ Proxy a
_ = [Char] -> a
forall a. [Char] -> a
errorWithoutStackTrace [Char]
"foldr1: Proxy"
    length :: Proxy a -> Int
length Proxy a
_   = Int
0
    null :: Proxy a -> Bool
null Proxy a
_     = Bool
True
    elem :: a -> Proxy a -> Bool
elem a
_ Proxy a
_   = Bool
False
    sum :: Proxy a -> a
sum Proxy a
_      = a
0
    product :: Proxy a -> a
product Proxy a
_  = a
1

-- | @since 4.8.0.0
instance Foldable Dual where
    foldMap :: (a -> m) -> Dual a -> m
foldMap            = (a -> m) -> Dual a -> m
coerce

    elem :: a -> Dual a -> Bool
elem               = ((a -> Bool) -> (Dual a -> a) -> Dual a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Dual a -> a
forall a. Dual a -> a
getDual) ((a -> Bool) -> Dual a -> Bool)
-> (a -> a -> Bool) -> a -> Dual a -> Bool
forall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c
#. a -> a -> Bool
forall a. Eq a => a -> a -> Bool
Evidence bound by a type signature of the constraint type Eq a
(==)
    foldl :: (b -> a -> b) -> b -> Dual a -> b
foldl              = (b -> a -> b) -> b -> Dual a -> b
coerce
    foldl' :: (b -> a -> b) -> b -> Dual a -> b
foldl'             = (b -> a -> b) -> b -> Dual a -> b
coerce
    foldl1 :: (a -> a -> a) -> Dual a -> a
foldl1 a -> a -> a
_           = Dual a -> a
forall a. Dual a -> a
getDual
    foldr :: (a -> b -> b) -> b -> Dual a -> b
foldr a -> b -> b
f b
z (Dual a
x) = a -> b -> b
f a
x b
z
    foldr' :: (a -> b -> b) -> b -> Dual a -> b
foldr'             = (a -> b -> b) -> b -> Dual a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Instance of class: Foldable of the constraint type Foldable Dual
foldr
    foldr1 :: (a -> a -> a) -> Dual a -> a
foldr1 a -> a -> a
_           = Dual a -> a
forall a. Dual a -> a
getDual
    length :: Dual a -> Int
length Dual a
_           = Int
1
    maximum :: Dual a -> a
maximum            = Dual a -> a
forall a. Dual a -> a
getDual
    minimum :: Dual a -> a
minimum            = Dual a -> a
forall a. Dual a -> a
getDual
    null :: Dual a -> Bool
null Dual a
_             = Bool
False
    product :: Dual a -> a
product            = Dual a -> a
forall a. Dual a -> a
getDual
    sum :: Dual a -> a
sum                = Dual a -> a
forall a. Dual a -> a
getDual
    toList :: Dual a -> [a]
toList (Dual a
x)    = [a
x]

-- | @since 4.8.0.0
instance Foldable Sum where
    foldMap :: (a -> m) -> Sum a -> m
foldMap            = (a -> m) -> Sum a -> m
coerce

    elem :: a -> Sum a -> Bool
elem               = ((a -> Bool) -> (Sum a -> a) -> Sum a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Sum a -> a
forall a. Sum a -> a
getSum) ((a -> Bool) -> Sum a -> Bool)
-> (a -> a -> Bool) -> a -> Sum a -> Bool
forall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c
#. a -> a -> Bool
forall a. Eq a => a -> a -> Bool
Evidence bound by a type signature of the constraint type Eq a
(==)
    foldl :: (b -> a -> b) -> b -> Sum a -> b
foldl              = (b -> a -> b) -> b -> Sum a -> b
coerce
    foldl' :: (b -> a -> b) -> b -> Sum a -> b
foldl'             = (b -> a -> b) -> b -> Sum a -> b
coerce
    foldl1 :: (a -> a -> a) -> Sum a -> a
foldl1 a -> a -> a
_           = Sum a -> a
forall a. Sum a -> a
getSum
    foldr :: (a -> b -> b) -> b -> Sum a -> b
foldr a -> b -> b
f b
z (Sum a
x)  = a -> b -> b
f a
x b
z
    foldr' :: (a -> b -> b) -> b -> Sum a -> b
foldr'             = (a -> b -> b) -> b -> Sum a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Instance of class: Foldable of the constraint type Foldable Sum
foldr
    foldr1 :: (a -> a -> a) -> Sum a -> a
foldr1 a -> a -> a
_           = Sum a -> a
forall a. Sum a -> a
getSum
    length :: Sum a -> Int
length Sum a
_           = Int
1
    maximum :: Sum a -> a
maximum            = Sum a -> a
forall a. Sum a -> a
getSum
    minimum :: Sum a -> a
minimum            = Sum a -> a
forall a. Sum a -> a
getSum
    null :: Sum a -> Bool
null Sum a
_             = Bool
False
    product :: Sum a -> a
product            = Sum a -> a
forall a. Sum a -> a
getSum
    sum :: Sum a -> a
sum                = Sum a -> a
forall a. Sum a -> a
getSum
    toList :: Sum a -> [a]
toList (Sum a
x)     = [a
x]

-- | @since 4.8.0.0
instance Foldable Product where
    foldMap :: (a -> m) -> Product a -> m
foldMap               = (a -> m) -> Product a -> m
coerce

    elem :: a -> Product a -> Bool
elem                  = ((a -> Bool) -> (Product a -> a) -> Product a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Product a -> a
forall a. Product a -> a
getProduct) ((a -> Bool) -> Product a -> Bool)
-> (a -> a -> Bool) -> a -> Product a -> Bool
forall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c
#. a -> a -> Bool
forall a. Eq a => a -> a -> Bool
Evidence bound by a type signature of the constraint type Eq a
(==)
    foldl :: (b -> a -> b) -> b -> Product a -> b
foldl                 = (b -> a -> b) -> b -> Product a -> b
coerce
    foldl' :: (b -> a -> b) -> b -> Product a -> b
foldl'                = (b -> a -> b) -> b -> Product a -> b
coerce
    foldl1 :: (a -> a -> a) -> Product a -> a
foldl1 a -> a -> a
_              = Product a -> a
forall a. Product a -> a
getProduct
    foldr :: (a -> b -> b) -> b -> Product a -> b
foldr a -> b -> b
f b
z (Product a
x) = a -> b -> b
f a
x b
z
    foldr' :: (a -> b -> b) -> b -> Product a -> b
foldr'                = (a -> b -> b) -> b -> Product a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Instance of class: Foldable of the constraint type Foldable Product
foldr
    foldr1 :: (a -> a -> a) -> Product a -> a
foldr1 a -> a -> a
_              = Product a -> a
forall a. Product a -> a
getProduct
    length :: Product a -> Int
length Product a
_              = Int
1
    maximum :: Product a -> a
maximum               = Product a -> a
forall a. Product a -> a
getProduct
    minimum :: Product a -> a
minimum               = Product a -> a
forall a. Product a -> a
getProduct
    null :: Product a -> Bool
null Product a
_                = Bool
False
    product :: Product a -> a
product               = Product a -> a
forall a. Product a -> a
getProduct
    sum :: Product a -> a
sum                   = Product a -> a
forall a. Product a -> a
getProduct
    toList :: Product a -> [a]
toList (Product a
x)    = [a
x]

-- | @since 4.8.0.0
instance Foldable First where
    foldMap :: (a -> m) -> First a -> m
foldMap a -> m
f = (a -> m) -> Maybe a -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
Evidence bound by a type signature of the constraint type Monoid m
Instance of class: Foldable of the constraint type Foldable Maybe
foldMap a -> m
f (Maybe a -> m) -> (First a -> Maybe a) -> First a -> m
forall b c a. (b -> c) -> (a -> b) -> a -> c
. First a -> Maybe a
forall a. First a -> Maybe a
getFirst

-- | @since 4.8.0.0
instance Foldable Last where
    foldMap :: (a -> m) -> Last a -> m
foldMap a -> m
f = (a -> m) -> Maybe a -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
Evidence bound by a type signature of the constraint type Monoid m
Instance of class: Foldable of the constraint type Foldable Maybe
foldMap a -> m
f (Maybe a -> m) -> (Last a -> Maybe a) -> Last a -> m
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Last a -> Maybe a
forall a. Last a -> Maybe a
getLast

-- | @since 4.12.0.0
instance (Foldable f) => Foldable (Alt f) where
    foldMap :: (a -> m) -> Alt f a -> m
foldMap a -> m
f = (a -> m) -> f a -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
Evidence bound by a type signature of the constraint type Monoid m
Evidence bound by a type signature of the constraint type Foldable f
foldMap a -> m
f (f a -> m) -> (Alt f a -> f a) -> Alt f a -> m
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Alt f a -> f a
forall {k} (f :: k -> *) (a :: k). Alt f a -> f a
getAlt

-- | @since 4.12.0.0
instance (Foldable f) => Foldable (Ap f) where
    foldMap :: (a -> m) -> Ap f a -> m
foldMap a -> m
f = (a -> m) -> f a -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
Evidence bound by a type signature of the constraint type Monoid m
Evidence bound by a type signature of the constraint type Foldable f
foldMap a -> m
f (f a -> m) -> (Ap f a -> f a) -> Ap f a -> m
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Ap f a -> f a
forall {k} (f :: k -> *) (a :: k). Ap f a -> f a
getAp

-- Instances for GHC.Generics
-- | @since 4.9.0.0
instance Foldable U1 where
    foldMap :: (a -> m) -> U1 a -> m
foldMap a -> m
_ U1 a
_ = m
forall a. Monoid a => a
Evidence bound by a type signature of the constraint type Monoid m
mempty
    {-# INLINE foldMap #-}
    fold :: U1 m -> m
fold U1 m
_ = m
forall a. Monoid a => a
Evidence bound by a type signature of the constraint type Monoid m
mempty
    {-# INLINE fold #-}
    foldr :: (a -> b -> b) -> b -> U1 a -> b
foldr a -> b -> b
_ b
z U1 a
_ = b
z
    {-# INLINE foldr #-}
    foldl :: (b -> a -> b) -> b -> U1 a -> b
foldl b -> a -> b
_ b
z U1 a
_ = b
z
    {-# INLINE foldl #-}
    foldl1 :: (a -> a -> a) -> U1 a -> a
foldl1 a -> a -> a
_ U1 a
_ = [Char] -> a
forall a. [Char] -> a
errorWithoutStackTrace [Char]
"foldl1: U1"
    foldr1 :: (a -> a -> a) -> U1 a -> a
foldr1 a -> a -> a
_ U1 a
_ = [Char] -> a
forall a. [Char] -> a
errorWithoutStackTrace [Char]
"foldr1: U1"
    length :: U1 a -> Int
length U1 a
_   = Int
0
    null :: U1 a -> Bool
null U1 a
_     = Bool
True
    elem :: a -> U1 a -> Bool
elem a
_ U1 a
_   = Bool
False
    sum :: U1 a -> a
sum U1 a
_      = a
0
    product :: U1 a -> a
product U1 a
_  = a
1

-- | @since 4.9.0.0
deriving instance Foldable V1

-- | @since 4.9.0.0
deriving instance Foldable Par1

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

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

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

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

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

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

-- | @since 4.9.0.0
deriving instance Foldable UAddr

-- | @since 4.9.0.0
deriving instance Foldable UChar

-- | @since 4.9.0.0
deriving instance Foldable UDouble

-- | @since 4.9.0.0
deriving instance Foldable UFloat

-- | @since 4.9.0.0
deriving instance Foldable UInt

-- | @since 4.9.0.0
deriving instance Foldable UWord

-- Instances for Data.Ord
-- | @since 4.12.0.0
deriving instance Foldable Down

-- | Monadic fold over the elements of a structure,
-- associating to the right, i.e. from right to left.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> foldrM (\string acc -> print string >> pure (acc + length string)) 42 ["Hello", "world", "!"]
-- "!"
-- "world"
-- "Hello"
-- 53
foldrM :: (Foldable t, Monad m) => (a -> b -> m b) -> b -> t a -> m b
foldrM :: (a -> b -> m b) -> b -> t a -> m b
foldrM a -> b -> m b
f b
z0 t a
xs = ((b -> m b) -> a -> b -> m b) -> (b -> m b) -> t a -> b -> m b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
Evidence bound by a type signature of the constraint type Foldable t
foldl (b -> m b) -> a -> b -> m b
forall {b}. (b -> m b) -> a -> b -> m b
c b -> m b
forall (m :: * -> *) a. Monad m => a -> m a
Evidence bound by a type signature of the constraint type Monad m
return t a
xs b
z0
  -- See Note [List fusion and continuations in 'c']
  where c :: (b -> m b) -> a -> b -> m b
c b -> m b
k a
x b
z = a -> b -> m b
f a
x b
z m b -> (b -> m b) -> m b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
Evidence bound by a type signature of the constraint type Monad m
>>= b -> m b
k
        {-# INLINE c #-}

-- | Monadic fold over the elements of a structure,
-- associating to the left, i.e. from left to right.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> foldlM (\acc string -> print string >> pure (acc + length string)) 42 ["Hello", "world", "!"]
-- "Hello"
-- "world"
-- "!"
-- 53
foldlM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b
foldlM :: (b -> a -> m b) -> b -> t a -> m b
foldlM b -> a -> m b
f b
z0 t a
xs = (a -> (b -> m b) -> b -> m b) -> (b -> m b) -> t a -> b -> m b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Evidence bound by a type signature of the constraint type Foldable t
foldr a -> (b -> m b) -> b -> m b
forall {b}. a -> (b -> m b) -> b -> m b
c b -> m b
forall (m :: * -> *) a. Monad m => a -> m a
Evidence bound by a type signature of the constraint type Monad m
return t a
xs b
z0
  -- See Note [List fusion and continuations in 'c']
  where c :: a -> (b -> m b) -> b -> m b
c a
x b -> m b
k b
z = b -> a -> m b
f b
z a
x m b -> (b -> m b) -> m b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
Evidence bound by a type signature of the constraint type Monad m
>>= b -> m b
k
        {-# INLINE c #-}

-- | 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'.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> traverse_ print ["Hello", "world", "!"]
-- "Hello"
-- "world"
-- "!"
traverse_ :: (Foldable t, Applicative f) => (a -> f b) -> t a -> f ()
traverse_ :: (a -> f b) -> t a -> f ()
traverse_ a -> f b
f = (a -> f () -> f ()) -> f () -> t a -> f ()
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Evidence bound by a type signature of the constraint type Foldable t
foldr a -> f () -> f ()
forall {b}. a -> f b -> f b
c (() -> f ()
forall (f :: * -> *) a. Applicative f => a -> f a
Evidence bound by a type signature of the constraint type Applicative f
pure ())
  -- See Note [List fusion and continuations in 'c']
  where c :: a -> f b -> f b
c a
x f b
k = a -> f b
f a
x f b -> f b -> f b
forall (f :: * -> *) a b. Applicative f => f a -> f b -> f b
Evidence bound by a type signature of the constraint type Applicative f
*> f b
k
        {-# INLINE c #-}

-- | 'for_' is 'traverse_' with its arguments flipped. For a version
-- that doesn't ignore the results see 'Data.Traversable.for'.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> for_ [1..4] print
-- 1
-- 2
-- 3
-- 4
for_ :: (Foldable t, Applicative f) => t a -> (a -> f b) -> f ()
{-# INLINE for_ #-}
for_ :: t a -> (a -> f b) -> f ()
for_ = ((a -> f b) -> t a -> f ()) -> t a -> (a -> f b) -> f ()
forall a b c. (a -> b -> c) -> b -> a -> c
flip (a -> f b) -> t a -> f ()
forall (t :: * -> *) (f :: * -> *) a b.
(Foldable t, Applicative f) =>
(a -> f b) -> t a -> f ()
Evidence bound by a type signature of the constraint type Applicative f
Evidence bound by a type signature of the constraint type Foldable t
traverse_

-- | Map each element of a structure to a monadic action, evaluate
-- 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'.
mapM_ :: (Foldable t, Monad m) => (a -> m b) -> t a -> m ()
mapM_ :: (a -> m b) -> t a -> m ()
mapM_ a -> m b
f = (a -> m () -> m ()) -> m () -> t a -> m ()
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Evidence bound by a type signature of the constraint type Foldable t
foldr a -> m () -> m ()
forall {b}. a -> m b -> m b
c (() -> m ()
forall (m :: * -> *) a. Monad m => a -> m a
Evidence bound by a type signature of the constraint type Monad m
return ())
  -- See Note [List fusion and continuations in 'c']
  where c :: a -> m b -> m b
c a
x m b
k = a -> m b
f a
x m b -> m b -> m b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
Evidence bound by a type signature of the constraint type Monad m
>> m b
k
        {-# INLINE c #-}

-- | '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'.
forM_ :: (Foldable t, Monad m) => t a -> (a -> m b) -> m ()
{-# INLINE forM_ #-}
forM_ :: t a -> (a -> m b) -> m ()
forM_ = ((a -> m b) -> t a -> m ()) -> t a -> (a -> m b) -> m ()
forall a b c. (a -> b -> c) -> b -> a -> c
flip (a -> m b) -> t a -> m ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
(a -> m b) -> t a -> m ()
Evidence bound by a type signature of the constraint type Monad m
Evidence bound by a type signature of the constraint type Foldable t
mapM_

-- | 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'.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> sequenceA_ [print "Hello", print "world", print "!"]
-- "Hello"
-- "world"
-- "!"
sequenceA_ :: (Foldable t, Applicative f) => t (f a) -> f ()
sequenceA_ :: t (f a) -> f ()
sequenceA_ = (f a -> f () -> f ()) -> f () -> t (f a) -> f ()
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Evidence bound by a type signature of the constraint type Foldable t
foldr f a -> f () -> f ()
forall {f :: * -> *} {a} {b}. Applicative f => f a -> f b -> f b
Evidence bound by a type signature of the constraint type Applicative f
c (() -> f ()
forall (f :: * -> *) a. Applicative f => a -> f a
Evidence bound by a type signature of the constraint type Applicative f
pure ())
  -- See Note [List fusion and continuations in 'c']
  where c :: f a -> f b -> f b
c f a
m f b
k = f a
m f a -> f b -> f b
forall (f :: * -> *) a b. Applicative f => f a -> f b -> f b
Evidence bound by a type signature of the constraint type Applicative f
*> f b
k
        {-# INLINE c #-}

-- | Evaluate each monadic action in the structure from left to right,
-- 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'.
sequence_ :: (Foldable t, Monad m) => t (m a) -> m ()
sequence_ :: t (m a) -> m ()
sequence_ = (m a -> m () -> m ()) -> m () -> t (m a) -> m ()
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Evidence bound by a type signature of the constraint type Foldable t
foldr m a -> m () -> m ()
forall {m :: * -> *} {a} {b}. Monad m => m a -> m b -> m b
Evidence bound by a type signature of the constraint type Monad m
c (() -> m ()
forall (m :: * -> *) a. Monad m => a -> m a
Evidence bound by a type signature of the constraint type Monad m
return ())
  -- See Note [List fusion and continuations in 'c']
  where c :: m a -> m b -> m b
c m a
m m b
k = m a
m m a -> m b -> m b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
Evidence bound by a type signature of the constraint type Monad m
>> m b
k
        {-# INLINE c #-}

-- | The sum of a collection of actions, generalizing 'concat'.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> asum [Just "Hello", Nothing, Just "World"]
-- Just "Hello"
asum :: (Foldable t, Alternative f) => t (f a) -> f a
{-# INLINE asum #-}
asum :: t (f a) -> f a
asum = (f a -> f a -> f a) -> f a -> t (f a) -> f a
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Evidence bound by a type signature of the constraint type Foldable t
foldr f a -> f a -> f a
forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
Evidence bound by a type signature of the constraint type Alternative f
(<|>) f a
forall (f :: * -> *) a. Alternative f => f a
Evidence bound by a type signature of the constraint type Alternative f
empty

-- | The sum of a collection of actions, generalizing 'concat'.
-- As of base 4.8.0.0, 'msum' is just 'asum', specialized to 'MonadPlus'.
msum :: (Foldable t, MonadPlus m) => t (m a) -> m a
{-# INLINE msum #-}
msum :: t (m a) -> m a
msum = t (m a) -> m a
forall (t :: * -> *) (f :: * -> *) a.
(Foldable t, Alternative f) =>
t (f a) -> f a
External instance of the constraint type forall (m :: * -> *). MonadPlus m => Alternative m
Evidence bound by a type signature of the constraint type MonadPlus m
Evidence bound by a type signature of the constraint type Foldable t
asum

-- | The concatenation of all the elements of a container of lists.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> concat (Just [1, 2, 3])
-- [1,2,3]
--
-- >>> concat (Node (Leaf [1, 2, 3]) [4, 5] (Node Empty [6] (Leaf [])))
-- [1,2,3,4,5,6]
concat :: Foldable t => t [a] -> [a]
concat :: t [a] -> [a]
concat t [a]
xs = (forall b. (a -> b -> b) -> b -> b) -> [a]
forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
build (\a -> b -> b
c b
n -> ([a] -> b -> b) -> b -> t [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Evidence bound by a type signature of the constraint type Foldable t
foldr (\[a]
x b
y -> (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Instance of class: Foldable of the constraint type Foldable []
foldr a -> b -> b
c b
y [a]
x) b
n t [a]
xs)
{-# INLINE concat #-}

-- | Map a function over all the elements of a container and concatenate
-- the resulting lists.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> concatMap (take 3) [[1..], [10..], [100..], [1000..]]
-- [1,2,3,10,11,12,100,101,102,1000,1001,1002]
--
-- >>> concatMap (take 3) (Node (Leaf [1..]) [10..] Empty)
-- [1,2,3,10,11,12]
concatMap :: Foldable t => (a -> [b]) -> t a -> [b]
concatMap :: (a -> [b]) -> t a -> [b]
concatMap a -> [b]
f t a
xs = (forall b. (b -> b -> b) -> b -> b) -> [b]
forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
build (\b -> b -> b
c b
n -> (a -> b -> b) -> b -> t a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Evidence bound by a type signature of the constraint type Foldable t
foldr (\a
x b
b -> (b -> b -> b) -> b -> [b] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Instance of class: Foldable of the constraint type Foldable []
foldr b -> b -> b
c b
b (a -> [b]
f a
x)) b
n t a
xs)
{-# INLINE concatMap #-}

-- These use foldr rather than foldMap to avoid repeated concatenation.

-- | '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.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> and []
-- True
--
-- >>> and [True]
-- True
--
-- >>> and [False]
-- False
--
-- >>> and [True, True, False]
-- False
--
-- >>> and (False : repeat True) -- Infinite list [False,True,True,True,True,True,True...
-- False
--
-- >>> and (repeat True)
-- * Hangs forever *
and :: Foldable t => t Bool -> Bool
and :: t Bool -> Bool
and = All -> Bool
getAll (All -> Bool) -> (t Bool -> All) -> t Bool -> Bool
forall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c
#. (Bool -> All) -> t Bool -> All
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
External instance of the constraint type Monoid All
Evidence bound by a type signature of the constraint type Foldable t
foldMap Bool -> All
All

-- | '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.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> or []
-- False
--
-- >>> or [True]
-- True
--
-- >>> or [False]
-- False
--
-- >>> or [True, True, False]
-- True
--
-- >>> or (True : repeat False) -- Infinite list [True,False,False,False,False,False,False...
-- True
--
-- >>> or (repeat False)
-- * Hangs forever *
or :: Foldable t => t Bool -> Bool
or :: t Bool -> Bool
or = Any -> Bool
getAny (Any -> Bool) -> (t Bool -> Any) -> t Bool -> Bool
forall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c
#. (Bool -> Any) -> t Bool -> Any
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
External instance of the constraint type Monoid Any
Evidence bound by a type signature of the constraint type Foldable t
foldMap Bool -> Any
Any

-- | Determines whether any element of the structure satisfies the predicate.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> any (> 3) []
-- False
--
-- >>> any (> 3) [1,2]
-- False
--
-- >>> any (> 3) [1,2,3,4,5]
-- True
--
-- >>> any (> 3) [1..]
-- True
--
-- >>> any (> 3) [0, -1..]
-- * Hangs forever *
any :: Foldable t => (a -> Bool) -> t a -> Bool
any :: (a -> Bool) -> t a -> Bool
any a -> Bool
p = Any -> Bool
getAny (Any -> Bool) -> (t a -> Any) -> t a -> Bool
forall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c
#. (a -> Any) -> t a -> Any
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
External instance of the constraint type Monoid Any
Evidence bound by a type signature of the constraint type Foldable t
foldMap (Bool -> Any
Any (Bool -> Any) -> (a -> Bool) -> a -> Any
forall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c
#. a -> Bool
p)

-- | Determines whether all elements of the structure satisfy the predicate.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> all (> 3) []
-- True
--
-- >>> all (> 3) [1,2]
-- False
--
-- >>> all (> 3) [1,2,3,4,5]
-- False
--
-- >>> all (> 3) [1..]
-- False
--
-- >>> all (> 3) [4..]
-- * Hangs forever *
all :: Foldable t => (a -> Bool) -> t a -> Bool
all :: (a -> Bool) -> t a -> Bool
all a -> Bool
p = All -> Bool
getAll (All -> Bool) -> (t a -> All) -> t a -> Bool
forall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c
#. (a -> All) -> t a -> All
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
External instance of the constraint type Monoid All
Evidence bound by a type signature of the constraint type Foldable t
foldMap (Bool -> All
All (Bool -> All) -> (a -> Bool) -> a -> All
forall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c
#. a -> Bool
p)

-- | The largest element of a non-empty structure with respect to the
-- given comparison function.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> maximumBy (compare `on` length) ["Hello", "World", "!", "Longest", "bar"]
-- "Longest"

-- See Note [maximumBy/minimumBy space usage]
maximumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a
maximumBy :: (a -> a -> Ordering) -> t a -> a
maximumBy a -> a -> Ordering
cmp = (a -> a -> a) -> t a -> a
forall (t :: * -> *) a. Foldable t => (a -> a -> a) -> t a -> a
Evidence bound by a type signature of the constraint type Foldable t
foldl1 a -> a -> a
max'
  where max' :: a -> a -> a
max' a
x a
y = case a -> a -> Ordering
cmp a
x a
y of
                        Ordering
GT -> a
x
                        Ordering
_  -> a
y

-- | The least element of a non-empty structure with respect to the
-- given comparison function.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> minimumBy (compare `on` length) ["Hello", "World", "!", "Longest", "bar"]
-- "!"

-- See Note [maximumBy/minimumBy space usage]
minimumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a
minimumBy :: (a -> a -> Ordering) -> t a -> a
minimumBy a -> a -> Ordering
cmp = (a -> a -> a) -> t a -> a
forall (t :: * -> *) a. Foldable t => (a -> a -> a) -> t a -> a
Evidence bound by a type signature of the constraint type Foldable t
foldl1 a -> a -> a
min'
  where min' :: a -> a -> a
min' a
x a
y = case a -> a -> Ordering
cmp a
x a
y of
                        Ordering
GT -> a
y
                        Ordering
_  -> a
x

-- | 'notElem' is the negation of 'elem'.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> 3 `notElem` []
-- True
--
-- >>> 3 `notElem` [1,2]
-- True
--
-- >>> 3 `notElem` [1,2,3,4,5]
-- False
--
-- For infinite structures, 'notElem' terminates if the value exists at a
-- finite distance from the left side of the structure:
--
-- >>> 3 `notElem` [1..]
-- False
--
-- >>> 3 `notElem` ([4..] ++ [3])
-- * Hangs forever *
notElem :: (Foldable t, Eq a) => a -> t a -> Bool
notElem :: a -> t a -> Bool
notElem a
x = Bool -> Bool
not (Bool -> Bool) -> (t a -> Bool) -> t a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> t a -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
Evidence bound by a type signature of the constraint type Eq a
Evidence bound by a type signature of the constraint type Foldable t
elem a
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.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> find (> 42) [0, 5..]
-- Just 45
--
-- >>> find (> 4) (Node (Leaf 3) 17 (Node Empty 12 (Leaf 8)))
-- Just 17
--
-- >>> find (> 12) [1..7]
-- Nothing
find :: Foldable t => (a -> Bool) -> t a -> Maybe a
find :: (a -> Bool) -> t a -> Maybe a
find a -> Bool
p = First a -> Maybe a
forall a. First a -> Maybe a
getFirst (First a -> Maybe a) -> (t a -> First a) -> t a -> Maybe a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> First a) -> t a -> First a
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
External instance of the constraint type forall a. Monoid (First a)
Evidence bound by a type signature of the constraint type Foldable t
foldMap (\ a
x -> Maybe a -> First a
forall a. Maybe a -> First a
First (if a -> Bool
p a
x then a -> Maybe a
forall a. a -> Maybe a
Just a
x else Maybe a
forall a. Maybe a
Nothing))

{-
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)

  = { Definition 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 #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 GHC.Core.Opt.Simplify.Utils.
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`.
-}

{-
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 #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://gitlab.haskell.org/ghc/ghc/issues/10830#note_129843 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.
-}