Movatterモバイル変換

{-# 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.-------------------------------------------------------------------------------moduleData.Foldable(Foldable(..),-- * Special biased foldsfoldrM,foldlM,-- * Folding actions-- ** Applicative actionstraverse_,for_,sequenceA_,asum,-- ** Monadic actionsmapM_,forM_,sequence_,msum,-- * Specialized foldsconcat,concatMap,and,or,any,all,maximumBy,minimumBy,-- * SearchesnotElem,find)whereimportData.BoolimportData.EitherimportData.EqimportData.Functor.Utils(Max(..),Min(..),(#.))importqualifiedGHC.ListasListimportData.MaybeimportData.MonoidimportData.OrdimportData.ProxyimportGHC.Arr(Array(..),elems,numElements,foldlElems,foldrElems,foldlElems',foldrElems',foldl1Elems,foldr1Elems)importGHC.Basehiding(foldr)importGHC.GenericsimportGHC.Num(Num(..))infix4`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)classFoldabletwhere{-# MINIMALfoldMap|foldr#-}-- | Combine the elements of a structure using a monoid.fold::Monoidm=>tm->mfold=(m -> m) -> t m -> mforall (t :: * -> *) m a.(Foldable t, Monoid m) =>(a -> m) -> t a -> mfoldMapm -> mforall a. a -> aid-- | Map each element of the structure to a monoid,-- and combine the results.foldMap::Monoidm=>(a->m)->ta->m{-# INLINEfoldMap#-}-- This INLINE allows more list functions to fuse. See #9848.foldMapa -> mf=(a -> m -> m) -> m -> t a -> mforall (t :: * -> *) a b.Foldable t =>(a -> b -> b) -> b -> t a -> bfoldr(m -> m -> mforall a. Monoid a => a -> a -> amappend(m -> m -> m) -> (a -> m) -> a -> m -> mforall b c a. (b -> c) -> (a -> b) -> a -> c.a -> mf)mforall a. Monoid a => amempty-- | A variant of 'foldMap' that is strict in the accumulator.---- @since 4.13.0.0foldMap'::Monoidm=>(a->m)->ta->mfoldMap'a -> mf=(m -> a -> m) -> m -> t a -> mforall (t :: * -> *) b a.Foldable t =>(b -> a -> b) -> b -> t a -> bfoldl'(\maccaa->maccm -> m -> mforall a. Semigroup a => a -> a -> a<>a -> mfaa)mforall a. Monoid a => amempty-- | 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'@--foldr::(a->b->b)->b->ta->bfoldra -> b -> bfbzt at=Endo b -> b -> bforall a. Endo a -> a -> aappEndo((a -> Endo b) -> t a -> Endo bforall (t :: * -> *) m a.(Foldable t, Monoid m) =>(a -> m) -> t a -> mfoldMap((b -> b) -> Endo bforall a. (a -> a) -> Endo aEndo((b -> b) -> Endo b) -> (a -> b -> b) -> a -> Endo bforall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c#.a -> b -> bf)t at)bz-- | Right-associative fold of a structure, but with strict application of-- the operator.---- @since 4.6.0.0foldr'::(a->b->b)->b->ta->bfoldr'a -> b -> bfbz0t axs=((b -> b) -> a -> b -> b) -> (b -> b) -> t a -> b -> bforall (t :: * -> *) b a.Foldable t =>(b -> a -> b) -> b -> t a -> bfoldl(b -> b) -> a -> b -> bforall b. (b -> b) -> a -> b -> bf'b -> bforall a. a -> aidt axsbz0wheref' :: (b -> b) -> a -> b -> bf'b -> bkaxbz=b -> bk(b -> b) -> b -> bforall a b. (a -> b) -> a -> b$!a -> b -> bfaxbz-- | 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'@--foldl::(b->a->b)->b->ta->bfoldlb -> a -> bfbzt at=Endo b -> b -> bforall a. Endo a -> a -> aappEndo(Dual (Endo b) -> Endo bforall a. Dual a -> agetDual((a -> Dual (Endo b)) -> t a -> Dual (Endo b)forall (t :: * -> *) m a.(Foldable t, Monoid m) =>(a -> m) -> t a -> mfoldMap(Endo b -> Dual (Endo b)forall a. a -> Dual aDual(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 bforall a. (a -> a) -> Endo aEndo((b -> b) -> Endo b) -> (a -> b -> b) -> a -> Endo bforall b c a. (b -> c) -> (a -> b) -> a -> c.(b -> a -> b) -> a -> b -> bforall a b c. (a -> b -> c) -> b -> a -> cflipb -> a -> bf)t at))bz-- 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.0foldl'::(b->a->b)->b->ta->bfoldl'b -> a -> bfbz0t axs=(a -> (b -> b) -> b -> b) -> (b -> b) -> t a -> b -> bforall (t :: * -> *) a b.Foldable t =>(a -> b -> b) -> b -> t a -> bfoldra -> (b -> b) -> b -> bforall b. a -> (b -> b) -> b -> bf'b -> bforall a. a -> aidt axsbz0wheref' :: a -> (b -> b) -> b -> bf'axb -> bkbz=b -> bk(b -> b) -> b -> bforall a b. (a -> b) -> a -> b$!b -> a -> bfbzax-- | A variant of 'foldr' that has no base case,-- and thus may only be applied to non-empty structures.---- @'foldr1' f = 'List.foldr1' f . 'toList'@foldr1::(a->a->a)->ta->afoldr1a -> a -> aft axs=a -> Maybe a -> aforall a. a -> Maybe a -> afromMaybe([Char] -> aforall a. [Char] -> aerrorWithoutStackTrace[Char]"foldr1: empty structure")((a -> Maybe a -> Maybe a) -> Maybe a -> t a -> Maybe aforall (t :: * -> *) a b.Foldable t =>(a -> b -> b) -> b -> t a -> bfoldra -> Maybe a -> Maybe amfMaybe aforall a. Maybe aNothingt axs)wheremf :: a -> Maybe a -> Maybe amfaxMaybe am=a -> Maybe aforall a. a -> Maybe aJust(caseMaybe amofMaybe aNothing->axJustay->a -> a -> afaxay)-- | A variant of 'foldl' that has no base case,-- and thus may only be applied to non-empty structures.---- @'foldl1' f = 'List.foldl1' f . 'toList'@foldl1::(a->a->a)->ta->afoldl1a -> a -> aft axs=a -> Maybe a -> aforall a. a -> Maybe a -> afromMaybe([Char] -> aforall a. [Char] -> aerrorWithoutStackTrace[Char]"foldl1: empty structure")((Maybe a -> a -> Maybe a) -> Maybe a -> t a -> Maybe aforall (t :: * -> *) b a.Foldable t =>(b -> a -> b) -> b -> t a -> bfoldlMaybe a -> a -> Maybe amfMaybe aforall a. Maybe aNothingt axs)wheremf :: Maybe a -> a -> Maybe amfMaybe amay=a -> Maybe aforall a. a -> Maybe aJust(caseMaybe amofMaybe aNothing->ayJustax->a -> a -> afaxay)-- | List of elements of a structure, from left to right.---- @since 4.8.0.0toList::ta->[a]{-# INLINEtoList#-}toListt at=(forall b. (a -> b -> b) -> b -> b) -> [a]forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]build(\a -> b -> bcbn->(a -> b -> b) -> b -> t a -> bforall (t :: * -> *) a b.Foldable t =>(a -> b -> b) -> b -> t a -> bfoldra -> b -> bcbnt at)-- | 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.---- @since 4.8.0.0null::ta->Boolnull=(a -> Bool -> Bool) -> Bool -> t a -> Boolforall (t :: * -> *) a b.Foldable t =>(a -> b -> b) -> b -> t a -> bfoldr(\a_Bool_->BoolFalse)BoolTrue-- | 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.---- @since 4.8.0.0length::ta->Intlength=(Int -> a -> Int) -> Int -> t a -> Intforall (t :: * -> *) b a.Foldable t =>(b -> a -> b) -> b -> t a -> bfoldl'(\Intca_->IntcInt -> Int -> Intforall a. Num a => a -> a -> a+Int1)Int0-- | Does the element occur in the structure?---- @since 4.8.0.0elem::Eqa=>a->ta->Boolelem=(a -> Bool) -> t a -> Boolforall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Boolany((a -> Bool) -> t a -> Bool)-> (a -> a -> Bool) -> a -> t a -> Boolforall b c a. (b -> c) -> (a -> b) -> a -> c.a -> a -> Boolforall a. Eq a => a -> a -> Bool(==)-- | The largest element of a non-empty structure.---- @since 4.8.0.0maximum::foralla.Orda=>ta->amaximum=a -> Maybe a -> aforall a. a -> Maybe a -> afromMaybe([Char] -> aforall a. [Char] -> aerrorWithoutStackTrace[Char]"maximum: empty structure")(Maybe a -> a) -> (t a -> Maybe a) -> t a -> aforall b c a. (b -> c) -> (a -> b) -> a -> c.Max a -> Maybe aforall a. Max a -> Maybe agetMax(Max a -> Maybe a) -> (t a -> Max a) -> t a -> Maybe aforall b c a. (b -> c) -> (a -> b) -> a -> c.(a -> Max a) -> t a -> Max aforall (t :: * -> *) m a.(Foldable t, Monoid m) =>(a -> m) -> t a -> mfoldMap(Maybe a -> Max aforall a. Maybe a -> Max aMax(Maybe a -> Max a) -> (a -> Maybe a) -> a -> Max aforall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c#.(a -> Maybe aforall a. a -> Maybe aJust::a->Maybea))-- | The least element of a non-empty structure.---- @since 4.8.0.0minimum::foralla.Orda=>ta->aminimum=a -> Maybe a -> aforall a. a -> Maybe a -> afromMaybe([Char] -> aforall a. [Char] -> aerrorWithoutStackTrace[Char]"minimum: empty structure")(Maybe a -> a) -> (t a -> Maybe a) -> t a -> aforall b c a. (b -> c) -> (a -> b) -> a -> c.Min a -> Maybe aforall a. Min a -> Maybe agetMin(Min a -> Maybe a) -> (t a -> Min a) -> t a -> Maybe aforall b c a. (b -> c) -> (a -> b) -> a -> c.(a -> Min a) -> t a -> Min aforall (t :: * -> *) m a.(Foldable t, Monoid m) =>(a -> m) -> t a -> mfoldMap(Maybe a -> Min aforall a. Maybe a -> Min aMin(Maybe a -> Min a) -> (a -> Maybe a) -> a -> Min aforall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c#.(a -> Maybe aforall a. a -> Maybe aJust::a->Maybea))-- | The 'sum' function computes the sum of the numbers of a structure.---- @since 4.8.0.0sum::Numa=>ta->asum=Sum a -> aforall a. Sum a -> agetSum(Sum a -> a) -> (t a -> Sum a) -> t a -> aforall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c#.(a -> Sum a) -> t a -> Sum aforall (t :: * -> *) m a.(Foldable t, Monoid m) =>(a -> m) -> t a -> mfoldMapa -> Sum aforall a. a -> Sum aSum-- | The 'product' function computes the product of the numbers of a-- structure.---- @since 4.8.0.0product::Numa=>ta->aproduct=Product a -> aforall a. Product a -> agetProduct(Product a -> a) -> (t a -> Product a) -> t a -> aforall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c#.(a -> Product a) -> t a -> Product aforall (t :: * -> *) m a.(Foldable t, Monoid m) =>(a -> m) -> t a -> mfoldMapa -> Product aforall a. a -> Product aProduct-- instances for Prelude types-- | @since 2.01instanceFoldableMaybewherefoldMap :: (a -> m) -> Maybe a -> mfoldMap=m -> (a -> m) -> Maybe a -> mforall b a. b -> (a -> b) -> Maybe a -> bmaybemforall a. Monoid a => amemptyfoldr :: (a -> b -> b) -> b -> Maybe a -> bfoldra -> b -> b_bzMaybe aNothing=bzfoldra -> b -> bfbz(Justax)=a -> b -> bfaxbzfoldl :: (b -> a -> b) -> b -> Maybe a -> bfoldlb -> a -> b_bzMaybe aNothing=bzfoldlb -> a -> bfbz(Justax)=b -> a -> bfbzax-- | @since 2.01instanceFoldable[]whereelem :: a -> [a] -> Boolelem=a -> [a] -> Boolforall a. Eq a => a -> [a] -> BoolList.elemfoldl :: (b -> a -> b) -> b -> [a] -> bfoldl=(b -> a -> b) -> b -> [a] -> bforall a b. (b -> a -> b) -> b -> [a] -> bList.foldlfoldl' :: (b -> a -> b) -> b -> [a] -> bfoldl'=(b -> a -> b) -> b -> [a] -> bforall a b. (b -> a -> b) -> b -> [a] -> bList.foldl'foldl1 :: (a -> a -> a) -> [a] -> afoldl1=(a -> a -> a) -> [a] -> aforall a. (a -> a -> a) -> [a] -> aList.foldl1foldr :: (a -> b -> b) -> b -> [a] -> bfoldr=(a -> b -> b) -> b -> [a] -> bforall a b. (a -> b -> b) -> b -> [a] -> bList.foldrfoldr1 :: (a -> a -> a) -> [a] -> afoldr1=(a -> a -> a) -> [a] -> aforall a. (a -> a -> a) -> [a] -> aList.foldr1length :: [a] -> Intlength=[a] -> Intforall a. [a] -> IntList.lengthmaximum :: [a] -> amaximum=[a] -> aforall a. Ord a => [a] -> aList.maximumminimum :: [a] -> aminimum=[a] -> aforall a. Ord a => [a] -> aList.minimumnull :: [a] -> Boolnull=[a] -> Boolforall a. [a] -> BoolList.nullproduct :: [a] -> aproduct=[a] -> aforall a. Num a => [a] -> aList.productsum :: [a] -> asum=[a] -> aforall a. Num a => [a] -> aList.sumtoList :: [a] -> [a]toList=[a] -> [a]forall a. a -> aid-- | @since 4.9.0.0instanceFoldableNonEmptywherefoldr :: (a -> b -> b) -> b -> NonEmpty a -> bfoldra -> b -> bfbz~(aa:|[a]as)=a -> b -> bfaa((a -> b -> b) -> b -> [a] -> bforall a b. (a -> b -> b) -> b -> [a] -> bList.foldra -> b -> bfbz[a]as)foldl :: (b -> a -> b) -> b -> NonEmpty a -> bfoldlb -> a -> bfbz(aa:|[a]as)=(b -> a -> b) -> b -> [a] -> bforall a b. (b -> a -> b) -> b -> [a] -> bList.foldlb -> a -> bf(b -> a -> bfbzaa)[a]asfoldl1 :: (a -> a -> a) -> NonEmpty a -> afoldl1a -> a -> af(aa:|[a]as)=(a -> a -> a) -> a -> [a] -> aforall a b. (b -> a -> b) -> b -> [a] -> bList.foldla -> a -> afaa[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 -> afoldr1a -> a -> af(ap:|[a]ps)=(a -> (a -> a) -> a -> a) -> (a -> a) -> [a] -> a -> aforall (t :: * -> *) a b.Foldable t =>(a -> b -> b) -> b -> t a -> bfoldra -> (a -> a) -> a -> aforall t. t -> (t -> a) -> a -> agoa -> aforall a. a -> aid[a]psapwherego :: t -> (t -> a) -> a -> agotxt -> araprev=a -> a -> afaprev(t -> artx)-- 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 -> mfoldMapa -> mf~(aa:|[a]as)=a -> mfaam -> m -> mforall a. Monoid a => a -> a -> a`mappend`(a -> m) -> [a] -> mforall (t :: * -> *) m a.(Foldable t, Monoid m) =>(a -> m) -> t a -> mfoldMapa -> mf[a]asfold :: NonEmpty m -> mfold~(mm:|[m]ms)=mmm -> m -> mforall a. Monoid a => a -> a -> a`mappend`[m] -> mforall (t :: * -> *) m. (Foldable t, Monoid m) => t m -> mfold[m]mstoList :: NonEmpty a -> [a]toList~(aa:|[a]as)=aaa -> [a] -> [a]forall a. a -> [a] -> [a]:[a]as-- | @since 4.7.0.0instanceFoldable(Eithera)wherefoldMap :: (a -> m) -> Either a a -> mfoldMapa -> m_(Lefta_)=mforall a. Monoid a => amemptyfoldMapa -> mf(Rightay)=a -> mfayfoldr :: (a -> b -> b) -> b -> Either a a -> bfoldra -> b -> b_bz(Lefta_)=bzfoldra -> b -> bfbz(Rightay)=a -> b -> bfaybzlength :: Either a a -> Intlength(Lefta_)=Int0length(Righta_)=Int1null :: Either a a -> Boolnull=Either a a -> Boolforall a a. Either a a -> BoolisLeft-- | @since 4.7.0.0instanceFoldable((,)a)wherefoldMap :: (a -> m) -> (a, a) -> mfoldMapa -> mf(a_,ay)=a -> mfayfoldr :: (a -> b -> b) -> b -> (a, a) -> bfoldra -> b -> bfbz(a_,ay)=a -> b -> bfaybzlength :: (a, a) -> Intlength(a, a)_=Int1null :: (a, a) -> Boolnull(a, a)_=BoolFalse-- | @since 4.8.0.0instanceFoldable(Arrayi)wherefoldr :: (a -> b -> b) -> b -> Array i a -> bfoldr=(a -> b -> b) -> b -> Array i a -> bforall a b i. (a -> b -> b) -> b -> Array i a -> bfoldrElemsfoldl :: (b -> a -> b) -> b -> Array i a -> bfoldl=(b -> a -> b) -> b -> Array i a -> bforall b a i. (b -> a -> b) -> b -> Array i a -> bfoldlElemsfoldl' :: (b -> a -> b) -> b -> Array i a -> bfoldl'=(b -> a -> b) -> b -> Array i a -> bforall b a i. (b -> a -> b) -> b -> Array i a -> bfoldlElems'foldr' :: (a -> b -> b) -> b -> Array i a -> bfoldr'=(a -> b -> b) -> b -> Array i a -> bforall a b i. (a -> b -> b) -> b -> Array i a -> bfoldrElems'foldl1 :: (a -> a -> a) -> Array i a -> afoldl1=(a -> a -> a) -> Array i a -> aforall a i. (a -> a -> a) -> Array i a -> afoldl1Elemsfoldr1 :: (a -> a -> a) -> Array i a -> afoldr1=(a -> a -> a) -> Array i a -> aforall a i. (a -> a -> a) -> Array i a -> afoldr1ElemstoList :: Array i a -> [a]toList=Array i a -> [a]forall i a. Array i a -> [a]elemslength :: Array i a -> Intlength=Array i a -> Intforall i a. Array i a -> IntnumElementsnull :: Array i a -> BoolnullArray i aa=Array i a -> Intforall i a. Array i a -> IntnumElementsArray i aaInt -> Int -> Boolforall a. Eq a => a -> a -> Bool==Int0-- | @since 4.7.0.0instanceFoldableProxywherefoldMap :: (a -> m) -> Proxy a -> mfoldMapa -> m_Proxy a_=mforall a. Monoid a => amempty{-# INLINEfoldMap#-}fold :: Proxy m -> mfoldProxy m_=mforall a. Monoid a => amempty{-# INLINEfold#-}foldr :: (a -> b -> b) -> b -> Proxy a -> bfoldra -> b -> b_bzProxy a_=bz{-# INLINEfoldr#-}foldl :: (b -> a -> b) -> b -> Proxy a -> bfoldlb -> a -> b_bzProxy a_=bz{-# INLINEfoldl#-}foldl1 :: (a -> a -> a) -> Proxy a -> afoldl1a -> a -> a_Proxy a_=[Char] -> aforall a. [Char] -> aerrorWithoutStackTrace[Char]"foldl1: Proxy"foldr1 :: (a -> a -> a) -> Proxy a -> afoldr1a -> a -> a_Proxy a_=[Char] -> aforall a. [Char] -> aerrorWithoutStackTrace[Char]"foldr1: Proxy"length :: Proxy a -> IntlengthProxy a_=Int0null :: Proxy a -> BoolnullProxy a_=BoolTrueelem :: a -> Proxy a -> Boolelema_Proxy a_=BoolFalsesum :: Proxy a -> asumProxy a_=a0product :: Proxy a -> aproductProxy a_=a1-- | @since 4.8.0.0instanceFoldableDualwherefoldMap :: (a -> m) -> Dual a -> mfoldMap=(a -> m) -> Dual a -> mcoerceelem :: a -> Dual a -> Boolelem=((a -> Bool) -> (Dual a -> a) -> Dual a -> Boolforall b c a. (b -> c) -> (a -> b) -> a -> c.Dual a -> aforall a. Dual a -> agetDual)((a -> Bool) -> Dual a -> Bool)-> (a -> a -> Bool) -> a -> Dual a -> Boolforall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c#.a -> a -> Boolforall a. Eq a => a -> a -> Bool(==)foldl :: (b -> a -> b) -> b -> Dual a -> bfoldl=(b -> a -> b) -> b -> Dual a -> bcoercefoldl' :: (b -> a -> b) -> b -> Dual a -> bfoldl'=(b -> a -> b) -> b -> Dual a -> bcoercefoldl1 :: (a -> a -> a) -> Dual a -> afoldl1a -> a -> a_=Dual a -> aforall a. Dual a -> agetDualfoldr :: (a -> b -> b) -> b -> Dual a -> bfoldra -> b -> bfbz(Dualax)=a -> b -> bfaxbzfoldr' :: (a -> b -> b) -> b -> Dual a -> bfoldr'=(a -> b -> b) -> b -> Dual a -> bforall (t :: * -> *) a b.Foldable t =>(a -> b -> b) -> b -> t a -> bfoldrfoldr1 :: (a -> a -> a) -> Dual a -> afoldr1a -> a -> a_=Dual a -> aforall a. Dual a -> agetDuallength :: Dual a -> IntlengthDual a_=Int1maximum :: Dual a -> amaximum=Dual a -> aforall a. Dual a -> agetDualminimum :: Dual a -> aminimum=Dual a -> aforall a. Dual a -> agetDualnull :: Dual a -> BoolnullDual a_=BoolFalseproduct :: Dual a -> aproduct=Dual a -> aforall a. Dual a -> agetDualsum :: Dual a -> asum=Dual a -> aforall a. Dual a -> agetDualtoList :: Dual a -> [a]toList(Dualax)=[ax]-- | @since 4.8.0.0instanceFoldableSumwherefoldMap :: (a -> m) -> Sum a -> mfoldMap=(a -> m) -> Sum a -> mcoerceelem :: a -> Sum a -> Boolelem=((a -> Bool) -> (Sum a -> a) -> Sum a -> Boolforall b c a. (b -> c) -> (a -> b) -> a -> c.Sum a -> aforall a. Sum a -> agetSum)((a -> Bool) -> Sum a -> Bool)-> (a -> a -> Bool) -> a -> Sum a -> Boolforall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c#.a -> a -> Boolforall a. Eq a => a -> a -> Bool(==)foldl :: (b -> a -> b) -> b -> Sum a -> bfoldl=(b -> a -> b) -> b -> Sum a -> bcoercefoldl' :: (b -> a -> b) -> b -> Sum a -> bfoldl'=(b -> a -> b) -> b -> Sum a -> bcoercefoldl1 :: (a -> a -> a) -> Sum a -> afoldl1a -> a -> a_=Sum a -> aforall a. Sum a -> agetSumfoldr :: (a -> b -> b) -> b -> Sum a -> bfoldra -> b -> bfbz(Sumax)=a -> b -> bfaxbzfoldr' :: (a -> b -> b) -> b -> Sum a -> bfoldr'=(a -> b -> b) -> b -> Sum a -> bforall (t :: * -> *) a b.Foldable t =>(a -> b -> b) -> b -> t a -> bfoldrfoldr1 :: (a -> a -> a) -> Sum a -> afoldr1a -> a -> a_=Sum a -> aforall a. Sum a -> agetSumlength :: Sum a -> IntlengthSum a_=Int1maximum :: Sum a -> amaximum=Sum a -> aforall a. Sum a -> agetSumminimum :: Sum a -> aminimum=Sum a -> aforall a. Sum a -> agetSumnull :: Sum a -> BoolnullSum a_=BoolFalseproduct :: Sum a -> aproduct=Sum a -> aforall a. Sum a -> agetSumsum :: Sum a -> asum=Sum a -> aforall a. Sum a -> agetSumtoList :: Sum a -> [a]toList(Sumax)=[ax]-- | @since 4.8.0.0instanceFoldableProductwherefoldMap :: (a -> m) -> Product a -> mfoldMap=(a -> m) -> Product a -> mcoerceelem :: a -> Product a -> Boolelem=((a -> Bool) -> (Product a -> a) -> Product a -> Boolforall b c a. (b -> c) -> (a -> b) -> a -> c.Product a -> aforall a. Product a -> agetProduct)((a -> Bool) -> Product a -> Bool)-> (a -> a -> Bool) -> a -> Product a -> Boolforall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c#.a -> a -> Boolforall a. Eq a => a -> a -> Bool(==)foldl :: (b -> a -> b) -> b -> Product a -> bfoldl=(b -> a -> b) -> b -> Product a -> bcoercefoldl' :: (b -> a -> b) -> b -> Product a -> bfoldl'=(b -> a -> b) -> b -> Product a -> bcoercefoldl1 :: (a -> a -> a) -> Product a -> afoldl1a -> a -> a_=Product a -> aforall a. Product a -> agetProductfoldr :: (a -> b -> b) -> b -> Product a -> bfoldra -> b -> bfbz(Productax)=a -> b -> bfaxbzfoldr' :: (a -> b -> b) -> b -> Product a -> bfoldr'=(a -> b -> b) -> b -> Product a -> bforall (t :: * -> *) a b.Foldable t =>(a -> b -> b) -> b -> t a -> bfoldrfoldr1 :: (a -> a -> a) -> Product a -> afoldr1a -> a -> a_=Product a -> aforall a. Product a -> agetProductlength :: Product a -> IntlengthProduct a_=Int1maximum :: Product a -> amaximum=Product a -> aforall a. Product a -> agetProductminimum :: Product a -> aminimum=Product a -> aforall a. Product a -> agetProductnull :: Product a -> BoolnullProduct a_=BoolFalseproduct :: Product a -> aproduct=Product a -> aforall a. Product a -> agetProductsum :: Product a -> asum=Product a -> aforall a. Product a -> agetProducttoList :: Product a -> [a]toList(Productax)=[ax]-- | @since 4.8.0.0instanceFoldableFirstwherefoldMap :: (a -> m) -> First a -> mfoldMapa -> mf=(a -> m) -> Maybe a -> mforall (t :: * -> *) m a.(Foldable t, Monoid m) =>(a -> m) -> t a -> mfoldMapa -> mf(Maybe a -> m) -> (First a -> Maybe a) -> First a -> mforall b c a. (b -> c) -> (a -> b) -> a -> c.First a -> Maybe aforall a. First a -> Maybe agetFirst-- | @since 4.8.0.0instanceFoldableLastwherefoldMap :: (a -> m) -> Last a -> mfoldMapa -> mf=(a -> m) -> Maybe a -> mforall (t :: * -> *) m a.(Foldable t, Monoid m) =>(a -> m) -> t a -> mfoldMapa -> mf(Maybe a -> m) -> (Last a -> Maybe a) -> Last a -> mforall b c a. (b -> c) -> (a -> b) -> a -> c.Last a -> Maybe aforall a. Last a -> Maybe agetLast-- | @since 4.12.0.0instance(Foldablef)=>Foldable(Altf)wherefoldMap :: (a -> m) -> Alt f a -> mfoldMapa -> mf=(a -> m) -> f a -> mforall (t :: * -> *) m a.(Foldable t, Monoid m) =>(a -> m) -> t a -> mfoldMapa -> mf(f a -> m) -> (Alt f a -> f a) -> Alt f a -> mforall b c a. (b -> c) -> (a -> b) -> a -> c.Alt f a -> f aforall k (f :: k -> *) (a :: k). Alt f a -> f agetAlt-- | @since 4.12.0.0instance(Foldablef)=>Foldable(Apf)wherefoldMap :: (a -> m) -> Ap f a -> mfoldMapa -> mf=(a -> m) -> f a -> mforall (t :: * -> *) m a.(Foldable t, Monoid m) =>(a -> m) -> t a -> mfoldMapa -> mf(f a -> m) -> (Ap f a -> f a) -> Ap f a -> mforall b c a. (b -> c) -> (a -> b) -> a -> c.Ap f a -> f aforall k (f :: k -> *) (a :: k). Ap f a -> f agetAp-- Instances for GHC.Generics-- | @since 4.9.0.0instanceFoldableU1wherefoldMap :: (a -> m) -> U1 a -> mfoldMapa -> m_U1 a_=mforall a. Monoid a => amempty{-# INLINEfoldMap#-}fold :: U1 m -> mfoldU1 m_=mforall a. Monoid a => amempty{-# INLINEfold#-}foldr :: (a -> b -> b) -> b -> U1 a -> bfoldra -> b -> b_bzU1 a_=bz{-# INLINEfoldr#-}foldl :: (b -> a -> b) -> b -> U1 a -> bfoldlb -> a -> b_bzU1 a_=bz{-# INLINEfoldl#-}foldl1 :: (a -> a -> a) -> U1 a -> afoldl1a -> a -> a_U1 a_=[Char] -> aforall a. [Char] -> aerrorWithoutStackTrace[Char]"foldl1: U1"foldr1 :: (a -> a -> a) -> U1 a -> afoldr1a -> a -> a_U1 a_=[Char] -> aforall a. [Char] -> aerrorWithoutStackTrace[Char]"foldr1: U1"length :: U1 a -> IntlengthU1 a_=Int0null :: U1 a -> BoolnullU1 a_=BoolTrueelem :: a -> U1 a -> Boolelema_U1 a_=BoolFalsesum :: U1 a -> asumU1 a_=a0product :: U1 a -> aproductU1 a_=a1-- | @since 4.9.0.0derivinginstanceFoldableV1-- | @since 4.9.0.0derivinginstanceFoldablePar1-- | @since 4.9.0.0derivinginstanceFoldablef=>Foldable(Rec1f)-- | @since 4.9.0.0derivinginstanceFoldable(K1ic)-- | @since 4.9.0.0derivinginstanceFoldablef=>Foldable(M1icf)-- | @since 4.9.0.0derivinginstance(Foldablef,Foldableg)=>Foldable(f:+:g)-- | @since 4.9.0.0derivinginstance(Foldablef,Foldableg)=>Foldable(f:*:g)-- | @since 4.9.0.0derivinginstance(Foldablef,Foldableg)=>Foldable(f:.:g)-- | @since 4.9.0.0derivinginstanceFoldableUAddr-- | @since 4.9.0.0derivinginstanceFoldableUChar-- | @since 4.9.0.0derivinginstanceFoldableUDouble-- | @since 4.9.0.0derivinginstanceFoldableUFloat-- | @since 4.9.0.0derivinginstanceFoldableUInt-- | @since 4.9.0.0derivinginstanceFoldableUWord-- Instances for Data.Ord-- | @since 4.12.0.0derivinginstanceFoldableDown-- | Monadic fold over the elements of a structure,-- associating to the right, i.e. from right to left.foldrM::(Foldablet,Monadm)=>(a->b->mb)->b->ta->mbfoldrM :: (a -> b -> m b) -> b -> t a -> m bfoldrMa -> b -> m bfbz0t axs=((b -> m b) -> a -> b -> m b) -> (b -> m b) -> t a -> b -> m bforall (t :: * -> *) b a.Foldable t =>(b -> a -> b) -> b -> t a -> bfoldl(b -> m b) -> a -> b -> m bforall b. (b -> m b) -> a -> b -> m bcb -> m bforall (m :: * -> *) a. Monad m => a -> m areturnt axsbz0-- See Note [List fusion and continuations in 'c']wherec :: (b -> m b) -> a -> b -> m bcb -> m bkaxbz=a -> b -> m bfaxbzm b -> (b -> m b) -> m bforall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b>>=b -> m bk{-# INLINEc#-}-- | Monadic fold over the elements of a structure,-- associating to the left, i.e. from left to right.foldlM::(Foldablet,Monadm)=>(b->a->mb)->b->ta->mbfoldlM :: (b -> a -> m b) -> b -> t a -> m bfoldlMb -> a -> m bfbz0t axs=(a -> (b -> m b) -> b -> m b) -> (b -> m b) -> t a -> b -> m bforall (t :: * -> *) a b.Foldable t =>(a -> b -> b) -> b -> t a -> bfoldra -> (b -> m b) -> b -> m bforall b. a -> (b -> m b) -> b -> m bcb -> m bforall (m :: * -> *) a. Monad m => a -> m areturnt axsbz0-- See Note [List fusion and continuations in 'c']wherec :: a -> (b -> m b) -> b -> m bcaxb -> m bkbz=b -> a -> m bfbzaxm b -> (b -> m b) -> m bforall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b>>=b -> m bk{-# INLINEc#-}-- | 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'.traverse_::(Foldablet,Applicativef)=>(a->fb)->ta->f()traverse_ :: (a -> f b) -> t a -> f ()traverse_a -> f bf=(a -> f () -> f ()) -> f () -> t a -> f ()forall (t :: * -> *) a b.Foldable t =>(a -> b -> b) -> b -> t a -> bfoldra -> f () -> f ()forall b. a -> f b -> f bc(() -> f ()forall (f :: * -> *) a. Applicative f => a -> f apure())-- See Note [List fusion and continuations in 'c']wherec :: a -> f b -> f bcaxf bk=a -> f bfaxf b -> f b -> f bforall (f :: * -> *) a b. Applicative f => f a -> f b -> f b*>f bk{-# INLINEc#-}-- | '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-- 4for_::(Foldablet,Applicativef)=>ta->(a->fb)->f(){-# INLINEfor_#-}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 -> cflip(a -> f b) -> t a -> f ()forall (t :: * -> *) (f :: * -> *) a b.(Foldable t, Applicative f) =>(a -> f b) -> t a -> f ()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_::(Foldablet,Monadm)=>(a->mb)->ta->m()mapM_ :: (a -> m b) -> t a -> m ()mapM_a -> m bf=(a -> m () -> m ()) -> m () -> t a -> m ()forall (t :: * -> *) a b.Foldable t =>(a -> b -> b) -> b -> t a -> bfoldra -> m () -> m ()forall b. a -> m b -> m bc(() -> m ()forall (m :: * -> *) a. Monad m => a -> m areturn())-- See Note [List fusion and continuations in 'c']wherec :: a -> m b -> m bcaxm bk=a -> m bfaxm b -> m b -> m bforall (m :: * -> *) a b. Monad m => m a -> m b -> m b>>m bk{-# INLINEc#-}-- | '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_::(Foldablet,Monadm)=>ta->(a->mb)->m(){-# INLINEforM_#-}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 -> cflip(a -> m b) -> t a -> m ()forall (t :: * -> *) (m :: * -> *) a b.(Foldable t, Monad m) =>(a -> m b) -> t a -> m ()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'.sequenceA_::(Foldablet,Applicativef)=>t(fa)->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 -> bfoldrf a -> f () -> f ()forall (f :: * -> *) a b. Applicative f => f a -> f b -> f bc(() -> f ()forall (f :: * -> *) a. Applicative f => a -> f apure())-- See Note [List fusion and continuations in 'c']wherec :: f a -> f b -> f bcf amf bk=f amf a -> f b -> f bforall (f :: * -> *) a b. Applicative f => f a -> f b -> f b*>f bk{-# INLINEc#-}-- | 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_::(Foldablet,Monadm)=>t(ma)->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 -> bfoldrm a -> m () -> m ()forall (m :: * -> *) a b. Monad m => m a -> m b -> m bc(() -> m ()forall (m :: * -> *) a. Monad m => a -> m areturn())-- See Note [List fusion and continuations in 'c']wherec :: m a -> m b -> m bcm amm bk=m amm a -> m b -> m bforall (m :: * -> *) a b. Monad m => m a -> m b -> m b>>m bk{-# INLINEc#-}-- | The sum of a collection of actions, generalizing 'concat'.---- >>> asum [Just "Hello", Nothing, Just "World"]-- Just "Hello"asum::(Foldablet,Alternativef)=>t(fa)->fa{-# INLINEasum#-}asum :: t (f a) -> f aasum=(f a -> f a -> f a) -> f a -> t (f a) -> f aforall (t :: * -> *) a b.Foldable t =>(a -> b -> b) -> b -> t a -> bfoldrf a -> f a -> f aforall (f :: * -> *) a. Alternative f => f a -> f a -> f a(<|>)f aforall (f :: * -> *) a. Alternative f => f aempty-- | The sum of a collection of actions, generalizing 'concat'.-- As of base 4.8.0.0, 'msum' is just 'asum', specialized to 'MonadPlus'.msum::(Foldablet,MonadPlusm)=>t(ma)->ma{-# INLINEmsum#-}msum :: t (m a) -> m amsum=t (m a) -> m aforall (t :: * -> *) (f :: * -> *) a.(Foldable t, Alternative f) =>t (f a) -> f aasum-- | The concatenation of all the elements of a container of lists.concat::Foldablet=>t[a]->[a]concat :: t [a] -> [a]concatt [a]xs=(forall b. (a -> b -> b) -> b -> b) -> [a]forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]build(\a -> b -> bcbn->([a] -> b -> b) -> b -> t [a] -> bforall (t :: * -> *) a b.Foldable t =>(a -> b -> b) -> b -> t a -> bfoldr(\[a]xby->(a -> b -> b) -> b -> [a] -> bforall (t :: * -> *) a b.Foldable t =>(a -> b -> b) -> b -> t a -> bfoldra -> b -> bcby[a]x)bnt [a]xs){-# INLINEconcat#-}-- | Map a function over all the elements of a container and concatenate-- the resulting lists.concatMap::Foldablet=>(a->[b])->ta->[b]concatMap :: (a -> [b]) -> t a -> [b]concatMapa -> [b]ft axs=(forall b. (b -> b -> b) -> b -> b) -> [b]forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]build(\b -> b -> bcbn->(a -> b -> b) -> b -> t a -> bforall (t :: * -> *) a b.Foldable t =>(a -> b -> b) -> b -> t a -> bfoldr(\axbb->(b -> b -> b) -> b -> [b] -> bforall (t :: * -> *) a b.Foldable t =>(a -> b -> b) -> b -> t a -> bfoldrb -> b -> bcbb(a -> [b]fax))bnt axs){-# INLINEconcatMap#-}-- 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.and::Foldablet=>tBool->Booland :: t Bool -> Booland=All -> BoolgetAll(All -> Bool) -> (t Bool -> All) -> t Bool -> Boolforall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c#.(Bool -> All) -> t Bool -> Allforall (t :: * -> *) m a.(Foldable t, Monoid m) =>(a -> m) -> t a -> mfoldMapBool -> AllAll-- | '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::Foldablet=>tBool->Boolor :: t Bool -> Boolor=Any -> BoolgetAny(Any -> Bool) -> (t Bool -> Any) -> t Bool -> Boolforall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c#.(Bool -> Any) -> t Bool -> Anyforall (t :: * -> *) m a.(Foldable t, Monoid m) =>(a -> m) -> t a -> mfoldMapBool -> AnyAny-- | Determines whether any element of the structure satisfies the predicate.any::Foldablet=>(a->Bool)->ta->Boolany :: (a -> Bool) -> t a -> Boolanya -> Boolp=Any -> BoolgetAny(Any -> Bool) -> (t a -> Any) -> t a -> Boolforall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c#.(a -> Any) -> t a -> Anyforall (t :: * -> *) m a.(Foldable t, Monoid m) =>(a -> m) -> t a -> mfoldMap(Bool -> AnyAny(Bool -> Any) -> (a -> Bool) -> a -> Anyforall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c#.a -> Boolp)-- | Determines whether all elements of the structure satisfy the predicate.all::Foldablet=>(a->Bool)->ta->Boolall :: (a -> Bool) -> t a -> Boolalla -> Boolp=All -> BoolgetAll(All -> Bool) -> (t a -> All) -> t a -> Boolforall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c#.(a -> All) -> t a -> Allforall (t :: * -> *) m a.(Foldable t, Monoid m) =>(a -> m) -> t a -> mfoldMap(Bool -> AllAll(Bool -> All) -> (a -> Bool) -> a -> Allforall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c#.a -> Boolp)-- | The largest element of a non-empty structure with respect to the-- given comparison function.-- See Note [maximumBy/minimumBy space usage]maximumBy::Foldablet=>(a->a->Ordering)->ta->amaximumBy :: (a -> a -> Ordering) -> t a -> amaximumBya -> a -> Orderingcmp=(a -> a -> a) -> t a -> aforall (t :: * -> *) a. Foldable t => (a -> a -> a) -> t a -> afoldl1a -> a -> amax'wheremax' :: a -> a -> amax'axay=casea -> a -> OrderingcmpaxayofOrderingGT->axOrdering_->ay-- | The least element of a non-empty structure with respect to the-- given comparison function.-- See Note [maximumBy/minimumBy space usage]minimumBy::Foldablet=>(a->a->Ordering)->ta->aminimumBy :: (a -> a -> Ordering) -> t a -> aminimumBya -> a -> Orderingcmp=(a -> a -> a) -> t a -> aforall (t :: * -> *) a. Foldable t => (a -> a -> a) -> t a -> afoldl1a -> a -> amin'wheremin' :: a -> a -> amin'axay=casea -> a -> OrderingcmpaxayofOrderingGT->ayOrdering_->ax-- | 'notElem' is the negation of 'elem'.notElem::(Foldablet,Eqa)=>a->ta->BoolnotElem :: a -> t a -> BoolnotElemax=Bool -> Boolnot(Bool -> Bool) -> (t a -> Bool) -> t a -> Boolforall b c a. (b -> c) -> (a -> b) -> a -> c.a -> t a -> Boolforall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Boolelemax-- | 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::Foldablet=>(a->Bool)->ta->Maybeafind :: (a -> Bool) -> t a -> Maybe afinda -> Boolp=First a -> Maybe aforall a. First a -> Maybe agetFirst(First a -> Maybe a) -> (t a -> First a) -> t a -> Maybe aforall b c a. (b -> c) -> (a -> b) -> a -> c.(a -> First a) -> t a -> First aforall (t :: * -> *) m a.(Foldable t, Monoid m) =>(a -> m) -> t a -> mfoldMap(\ax->Maybe a -> First aforall a. Maybe a -> First aFirst(ifa -> Boolpaxthena -> Maybe aforall a. a -> Maybe aJustaxelseMaybe aforall a. Maybe aNothing)){-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 canbe 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; seeNote [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`.-}{-Note [maximumBy/minimumBy space usage]~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~When the type signatures of maximumBy and minimumBy were generalized to workover any Foldable instance (instead of just lists), they were defined usingfoldr1. This was problematic for space usage, as the semantics of maximumByand minimumBy essentially require that they examine every element of thedata structure. Using foldr1 to examine every element results in space usageproportional 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 andminimumBy to foldl1 solves the issue, as GHC's strictness analysis can thenmake these functions only use O(1) stack space. It is perhaps not the optimalway to fix this problem, as there are other conceivable data structures(besides lists) which might benefit from specialized implementations formaximumBy and minimumBy (seehttps://gitlab.haskell.org/ghc/ghc/issues/10830#note_129843 for a furtherdiscussion). But using foldl1 is at least always better than using foldr1, soGHC has chosen to adopt that approach for now.-}