----------------------------------------------------------------------------- -- | -- Module : Data.Foldable -- Copyright : Ross Paterson 2005 -- License : BSD-style (see the LICENSE file in the distribution) -- -- Maintainer : ross@soi.city.ac.uk -- Stability : experimental -- Portability : portable -- -- Class of data structures that can be folded to a summary value. -- -- Many of these functions generalize "Prelude", "Control.Monad" and -- "Data.List" functions of the same names from lists to any 'Foldable' -- functor. To avoid ambiguity, either import those modules hiding -- these names or qualify uses of these function names with an alias -- for this module.

moduleData.Foldable( -- * FoldsFoldable(..), -- ** Special biased foldsfoldr',foldl',foldrM,foldlM, -- ** Folding actions -- *** Applicative actionstraverse_,for_,sequenceA_,asum, -- *** Monadic actionsmapM_,forM_,sequence_,msum, -- ** Specialized foldstoList,concat,concatMap,and,or,any,all,sum,product,maximum,maximumBy,minimum,minimumBy, -- ** Searcheselem,notElem,find)whereimportPreludehiding(foldl,foldr,foldl1,foldr1,mapM_,sequence_,elem,notElem,concat,concatMap,and,or,any,all,sum,product,maximum,minimum)importqualifiedPrelude (foldl,foldr,foldl1,foldr1)importControl.ApplicativeimportControl.Monad (MonadPlus(..))importData.Maybe (fromMaybe,listToMaybe)importData.MonoidimportData.Array -- | Data structures that can be folded. -- -- Minimal complete definition: 'foldMap' or 'foldr'. -- -- 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 -- > 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. --classFoldabletwhere-- | Combine the elements of a structure using a monoid.fold::Monoidm=>tm->mfold=foldMapid-- | Map each element of the structure to a monoid, -- and combine the results.foldMap::Monoidm=>(a->m)->ta->mfoldMapf=foldr(mappend.f)mempty-- | Right-associative fold of a structure. -- -- @'foldr' f z = 'Prelude.foldr' f z . 'toList'@foldr::(a->b->b)->b->ta->bfoldrfzt=appEndo(foldMap(Endo.f)t)z-- | Left-associative fold of a structure. -- -- @'foldl' f z = 'Prelude.foldl' f z . 'toList'@foldl::(a->b->a)->a->tb->afoldlfzt=appEndo(getDual(foldMap(Dual.Endo.flipf)t))z-- | A variant of 'foldr' that has no base case, -- and thus may only be applied to non-empty structures. -- -- @'foldr1' f = 'Prelude.foldr1' f . 'toList'@foldr1::(a->a->a)->ta->afoldr1fxs=fromMaybe(error"foldr1: empty structure") (foldrmfNothingxs)wheremfxNothing=Justxmfx(Justy)=Just(fxy) -- | A variant of 'foldl' that has no base case, -- and thus may only be applied to non-empty structures. -- -- @'foldl1' f = 'Prelude.foldl1' f . 'toList'@foldl1::(a->a->a)->ta->afoldl1fxs=fromMaybe(error"foldl1: empty structure") (foldlmfNothingxs)wheremfNothingy=Justymf(Justx)y=Just(fxy) -- instances for Prelude typesinstanceFoldableMaybewherefoldrfzNothing=zfoldrfz(Justx)=fxzfoldlfzNothing=zfoldlfz(Justx)=fzxinstanceFoldable[]wherefoldr=Prelude.foldrfoldl=Prelude.foldlfoldr1=Prelude.foldr1foldl1=Prelude.foldl1instanceIxi=>Foldable(Arrayi)wherefoldrfz=Prelude.foldrfz.elems-- | Fold over the elements of a structure, -- associating to the right, but strictly.foldr'::Foldablet=>(a->b->b)->b->ta->bfoldr'fzxs=foldlf'idxszwheref'kxz=k$!fxz-- | 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->mbfoldrMfzxs=foldlf'returnxszwheref'kxz=fxz>>=k-- | Fold over the elements of a structure, -- associating to the left, but strictly.foldl'::Foldablet=>(a->b->a)->a->tb->afoldl'fzxs=foldrf'idxszwheref'xkz=k$!fzx-- | Monadic fold over the elements of a structure, -- associating to the left, i.e. from left to right.foldlM::(Foldablet,Monadm)=>(a->b->ma)->a->tb->mafoldlMfzxs=foldrf'returnxszwheref'xkz=fzx>>=k-- | Map each element of a structure to an action, evaluate -- these actions from left to right, and ignore the results.traverse_::(Foldablet,Applicativef)=>(a->fb)->ta->f()traverse_f=foldr((*>).f) (pure()) -- | 'for_' is 'traverse_' with its arguments flipped.for_::(Foldablet,Applicativef)=>ta->(a->fb)->f() {-# INLINE for_ #-}for_=fliptraverse_-- | Map each element of a structure to an monadic action, evaluate -- these actions from left to right, and ignore the results.mapM_::(Foldablet,Monadm)=>(a->mb)->ta->m()mapM_f=foldr((>>).f) (return()) -- | 'forM_' is 'mapM_' with its arguments flipped.forM_::(Foldablet,Monadm)=>ta->(a->mb)->m() {-# INLINE forM_ #-}forM_=flipmapM_-- | Evaluate each action in the structure from left to right, -- and ignore the results.sequenceA_::(Foldablet,Applicativef)=>t(fa)->f()sequenceA_=foldr(*>) (pure()) -- | Evaluate each monadic action in the structure from left to right, -- and ignore the results.sequence_::(Foldablet,Monadm)=>t(ma)->m()sequence_=foldr(>>) (return()) -- | The sum of a collection of actions, generalizing 'concat'.asum::(Foldablet,Alternativef)=>t(fa)->fa{-# INLINE asum #-}asum=foldr(<|>)empty-- | The sum of a collection of actions, generalizing 'concat'.msum::(Foldablet,MonadPlusm)=>t(ma)->ma{-# INLINE msum #-}msum=foldrmplusmzero-- These use foldr rather than foldMap to avoid repeated concatenation. -- | List of elements of a structure.toList::Foldablet=>ta->[a]toList=foldr(:) [] -- | The concatenation of all the elements of a container of lists.concat::Foldablet=>t[a]->[a]concat=fold-- | Map a function over all the elements of a container and concatenate -- the resulting lists.concatMap::Foldablet=>(a->[b])->ta->[b]concatMap=foldMap-- | '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=getAll.foldMapAll-- | '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=getAny.foldMapAny-- | Determines whether any element of the structure satisfies the predicate.any::Foldablet=>(a->Bool)->ta->Boolanyp=getAny.foldMap(Any.p) -- | Determines whether all elements of the structure satisfy the predicate.all::Foldablet=>(a->Bool)->ta->Boolallp=getAll.foldMap(All.p) -- | The 'sum' function computes the sum of the numbers of a structure.sum::(Foldablet,Numa)=>ta->asum=getSum.foldMapSum-- | The 'product' function computes the product of the numbers of a structure.product::(Foldablet,Numa)=>ta->aproduct=getProduct.foldMapProduct-- | The largest element of a non-empty structure.maximum::(Foldablet,Orda)=>ta->amaximum=foldr1max-- | The largest element of a non-empty structure with respect to the -- given comparison function.maximumBy::Foldablet=>(a->a->Ordering)->ta->amaximumBycmp=foldr1max'wheremax'xy=casecmpxyofGT->x_->y-- | The least element of a non-empty structure.minimum::(Foldablet,Orda)=>ta->aminimum=foldr1min-- | The least element of a non-empty structure with respect to the -- given comparison function.minimumBy::Foldablet=>(a->a->Ordering)->ta->aminimumBycmp=foldr1min'wheremin'xy=casecmpxyofGT->y_->x-- | Does the element occur in the structure?elem::(Foldablet,Eqa)=>a->ta->Boolelem=any.(==) -- | 'notElem' is the negation of 'elem'.notElem::(Foldablet,Eqa)=>a->ta->BoolnotElemx=not.elemx-- | 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->Maybeafindp=listToMaybe.concatMap(\x->ifpxthen[x]else[])

Index

(HTML for this module was generated on 2015-03-03. About the conversion tool.)