{-# 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. 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 foldMap m -> m forall a. a -> a id -- | Map each element of the structure to a monoid, -- and combine the results. 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 foldr (m -> m -> m forall a. Monoid a => a -> a -> a 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 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 foldl' (\ m acc a a -> m acc m -> m -> m forall a. Semigroup a => a -> a -> a <> a -> m f a a) m forall a. Monoid a => a 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'@ -- 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 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 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'@ -- 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 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 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. -- -- @'foldr1' f = 'List.foldr1' f . 'toList'@ 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 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. -- -- @'foldl1' f = 'List.foldl1' f . 'toList'@ 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 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. -- -- @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 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. -- -- @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 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. -- -- @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 foldl' (\Int c a _ -> Int cInt -> Int -> Int forall a. Num a => a -> a -> a +Int 1) Int 0 -- | Does the element occur in the structure? -- -- @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 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 (==) -- | The largest element of a non-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 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. -- -- @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 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. -- -- @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 foldMap a -> Sum a forall a. a -> Sum a Sum -- | The 'product' function computes the product of the numbers of a -- structure. -- -- @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 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 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 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 List.maximum minimum :: [a] -> a minimum = [a] -> a forall a. Ord a => [a] -> 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 List.product sum :: [a] -> a sum = [a] -> a forall a. Num a => [a] -> 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 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 `mappend` (a -> m) -> [a] -> m forall (t :: * -> *) m a. (Foldable t, Monoid m) => (a -> m) -> t a -> m 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 `mappend` [m] -> m forall (t :: * -> *) m. (Foldable t, Monoid m) => t m -> m 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 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 == 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 mempty {-# INLINE foldMap #-} fold :: Proxy m -> m fold Proxy m _ = m forall a. Monoid a => a 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 (==) 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 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 (==) 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 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 (==) 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 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 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 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 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 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 mempty {-# INLINE foldMap #-} fold :: U1 m -> m fold U1 m _ = m forall a. Monoid a => a 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. 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 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 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 >>= b -> m b k {-# INLINE c #-} -- | Monadic fold over the elements of a structure, -- associating to the left, i.e. from left to right. 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 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 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 >>= 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'. 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 foldr a -> f () -> f () forall b. a -> f b -> f b c (() -> f () forall (f :: * -> *) a. Applicative f => a -> f a 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 *> 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'. -- -- >>> 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 () 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 foldr a -> m () -> m () forall b. a -> m b -> m b c (() -> m () forall (m :: * -> *) a. Monad m => a -> m a 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 >> 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 () 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_ :: (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 foldr f a -> f () -> f () forall (f :: * -> *) a b. Applicative f => f a -> f b -> f b c (() -> f () forall (f :: * -> *) a. Applicative f => a -> f a 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 *> 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 foldr m a -> m () -> m () forall (m :: * -> *) a b. Monad m => m a -> m b -> m b c (() -> m () forall (m :: * -> *) a. Monad m => a -> m a 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 >> m b k {-# INLINE c #-} -- | The sum of a collection of actions, generalizing 'concat'. -- -- >>> 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 foldr f a -> f a -> f a forall (f :: * -> *) a. Alternative f => f a -> f a -> f a (<|>) f a forall (f :: * -> *) a. Alternative f => f a 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 asum -- | The concatenation of all the elements of a container of lists. 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 foldr (\[a] x b y -> (a -> b -> b) -> b -> [a] -> b forall (t :: * -> *) a b. Foldable t => (a -> b -> b) -> b -> t a -> b 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. 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 foldr (\a x b b -> (b -> b -> b) -> b -> [b] -> b forall (t :: * -> *) a b. Foldable t => (a -> b -> b) -> b -> t a -> b 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. 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 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. 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 foldMap Bool -> Any Any -- | Determines whether any element of the structure satisfies the predicate. 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 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. 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 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. -- 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 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. -- 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 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'. 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 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. 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 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 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 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. -}