{-# LANGUAGE DeriveFoldable #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE NoImplicitPrelude #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE StandaloneDeriving #-}
{-# LANGUAGE Trustworthy #-}
{-# LANGUAGE TypeOperators #-}
module Data.Foldable (
Foldable(..),
foldrM,
foldlM,
traverse_,
for_,
sequenceA_,
asum,
mapM_,
forM_,
sequence_,
msum,
concat,
concatMap,
and,
or,
any,
all,
maximumBy,
minimumBy,
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`
class Foldable t where
{-# MINIMAL foldMap | foldr #-}
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
foldMap :: Monoid m => (a -> m) -> t a -> m
{-# INLINE foldMap #-}
foldMap f :: 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
foldMap' :: Monoid m => (a -> m) -> t a -> m
foldMap' f :: a -> m
f = (m -> a -> m) -> m -> t a -> m
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\ acc :: m
acc a :: 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
foldr :: (a -> b -> b) -> b -> t a -> b
foldr f :: a -> b -> b
f z :: b
z t :: 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
foldr' :: (a -> b -> b) -> b -> t a -> b
foldr' f :: a -> b -> b
f z0 :: b
z0 xs :: 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' k :: b -> b
k x :: a
x z :: b
z = b -> b
k (b -> b) -> b -> b
forall a b. (a -> b) -> a -> b
$! a -> b -> b
f a
x b
z
foldl :: (b -> a -> b) -> b -> t a -> b
foldl f :: b -> a -> b
f z :: b
z t :: 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
foldl' :: (b -> a -> b) -> b -> t a -> b
foldl' f :: b -> a -> b
f z0 :: b
z0 xs :: 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' x :: a
x k :: b -> b
k z :: b
z = b -> b
k (b -> b) -> b -> b
forall a b. (a -> b) -> a -> b
$! b -> a -> b
f b
z a
x
foldr1 :: (a -> a -> a) -> t a -> a
foldr1 f :: a -> a -> a
f xs :: t a
xs = a -> Maybe a -> a
forall a. a -> Maybe a -> a
fromMaybe ([Char] -> a
forall a. [Char] -> a
errorWithoutStackTrace "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 x :: a
x m :: Maybe a
m = a -> Maybe a
forall a. a -> Maybe a
Just (case Maybe a
m of
Nothing -> a
x
Just y :: a
y -> a -> a -> a
f a
x a
y)
foldl1 :: (a -> a -> a) -> t a -> a
foldl1 f :: a -> a -> a
f xs :: t a
xs = a -> Maybe a -> a
forall a. a -> Maybe a -> a
fromMaybe ([Char] -> a
forall a. [Char] -> a
errorWithoutStackTrace "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 m :: Maybe a
m y :: a
y = a -> Maybe a
forall a. a -> Maybe a
Just (case Maybe a
m of
Nothing -> a
y
Just x :: a
x -> a -> a -> a
f a
x a
y)
toList :: t a -> [a]
{-# INLINE toList #-}
toList t :: t a
t = (forall b. (a -> b -> b) -> b -> b) -> [a]
forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
build (\ c :: a -> b -> b
c n :: 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)
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 (\_ _ -> Bool
False) Bool
True
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' (\c :: Int
c _ -> Int
cInt -> Int -> Int
forall a. Num a => a -> a -> a
+1) 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
(==)
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 "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))
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 "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))
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
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
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 _ z :: b
z Nothing = b
z
foldr f :: a -> b -> b
f z :: b
z (Just x :: a
x) = a -> b -> b
f a
x b
z
foldl :: (b -> a -> b) -> b -> Maybe a -> b
foldl _ z :: b
z Nothing = b
z
foldl f :: b -> a -> b
f z :: b
z (Just x :: a
x) = b -> a -> b
f b
z a
x
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
instance Foldable NonEmpty where
foldr :: (a -> b -> b) -> b -> NonEmpty a -> b
foldr f :: a -> b -> b
f z :: b
z ~(a :: a
a :| as :: [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 f :: b -> a -> b
f z :: b
z (a :: a
a :| as :: [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 f :: a -> a -> a
f (a :: a
a :| as :: [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
foldr1 :: (a -> a -> a) -> NonEmpty a -> a
foldr1 f :: a -> a -> a
f (p :: a
p :| ps :: [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 x :: t
x r :: t -> a
r prev :: a
prev = a -> a -> a
f a
prev (t -> a
r t
x)
foldMap :: (a -> m) -> NonEmpty a -> m
foldMap f :: a -> m
f ~(a :: a
a :| as :: [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]
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]
as) = a
a a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
as
instance Foldable (Either a) where
foldMap :: (a -> m) -> Either a a -> m
foldMap _ (Left _) = m
forall a. Monoid a => a
mempty
foldMap f :: a -> m
f (Right y :: a
y) = a -> m
f a
y
foldr :: (a -> b -> b) -> b -> Either a a -> b
foldr _ z :: b
z (Left _) = b
z
foldr f :: a -> b -> b
f z :: b
z (Right y :: a
y) = a -> b -> b
f a
y b
z
length :: Either a a -> Int
length (Left _) = 0
length (Right _) = 1
null :: Either a a -> Bool
null = Either a a -> Bool
forall a a. Either a a -> Bool
isLeft
instance Foldable ((,) a) where
foldMap :: (a -> m) -> (a, a) -> m
foldMap f :: a -> m
f (_, y :: a
y) = a -> m
f a
y
foldr :: (a -> b -> b) -> b -> (a, a) -> b
foldr f :: a -> b -> b
f z :: b
z (_, y :: a
y) = a -> b -> b
f a
y b
z
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 a :: 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
== 0
instance Foldable Proxy where
foldMap :: (a -> m) -> Proxy a -> m
foldMap _ _ = m
forall a. Monoid a => a
mempty
{-# INLINE foldMap #-}
fold :: Proxy m -> m
fold _ = m
forall a. Monoid a => a
mempty
{-# INLINE fold #-}
foldr :: (a -> b -> b) -> b -> Proxy a -> b
foldr _ z :: b
z _ = b
z
{-# INLINE foldr #-}
foldl :: (b -> a -> b) -> b -> Proxy a -> b
foldl _ z :: b
z _ = b
z
{-# INLINE foldl #-}
foldl1 :: (a -> a -> a) -> Proxy a -> a
foldl1 _ _ = [Char] -> a
forall a. [Char] -> a
errorWithoutStackTrace "foldl1: Proxy"
foldr1 :: (a -> a -> a) -> Proxy a -> a
foldr1 _ _ = [Char] -> a
forall a. [Char] -> a
errorWithoutStackTrace "foldr1: Proxy"
length :: Proxy a -> Int
length _ = 0
null :: Proxy a -> Bool
null _ = Bool
True
elem :: a -> Proxy a -> Bool
elem _ _ = Bool
False
sum :: Proxy a -> a
sum _ = 0
product :: Proxy a -> a
product _ = 1
instance Foldable Dual where
foldMap :: (a -> m) -> Dual a -> m
foldMap = (a -> m) -> Dual a -> m
forall a b. Coercible a b => a -> b
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
forall a b. Coercible a b => a -> b
coerce
foldl' :: (b -> a -> b) -> b -> Dual a -> b
foldl' = (b -> a -> b) -> b -> Dual a -> b
forall a b. Coercible a b => a -> b
coerce
foldl1 :: (a -> a -> a) -> Dual a -> a
foldl1 _ = Dual a -> a
forall a. Dual a -> a
getDual
foldr :: (a -> b -> b) -> b -> Dual a -> b
foldr f :: a -> b -> b
f z :: b
z (Dual x :: 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 _ = Dual a -> a
forall a. Dual a -> a
getDual
length :: Dual a -> Int
length _ = 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 _ = 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 x :: a
x) = [a
x]
instance Foldable Sum where
foldMap :: (a -> m) -> Sum a -> m
foldMap = (a -> m) -> Sum a -> m
forall a b. Coercible a b => a -> b
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
forall a b. Coercible a b => a -> b
coerce
foldl' :: (b -> a -> b) -> b -> Sum a -> b
foldl' = (b -> a -> b) -> b -> Sum a -> b
forall a b. Coercible a b => a -> b
coerce
foldl1 :: (a -> a -> a) -> Sum a -> a
foldl1 _ = Sum a -> a
forall a. Sum a -> a
getSum
foldr :: (a -> b -> b) -> b -> Sum a -> b
foldr f :: a -> b -> b
f z :: b
z (Sum x :: 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 _ = Sum a -> a
forall a. Sum a -> a
getSum
length :: Sum a -> Int
length _ = 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 _ = 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 x :: a
x) = [a
x]
instance Foldable Product where
foldMap :: (a -> m) -> Product a -> m
foldMap = (a -> m) -> Product a -> m
forall a b. Coercible a b => a -> b
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
forall a b. Coercible a b => a -> b
coerce
foldl' :: (b -> a -> b) -> b -> Product a -> b
foldl' = (b -> a -> b) -> b -> Product a -> b
forall a b. Coercible a b => a -> b
coerce
foldl1 :: (a -> a -> a) -> Product a -> a
foldl1 _ = Product a -> a
forall a. Product a -> a
getProduct
foldr :: (a -> b -> b) -> b -> Product a -> b
foldr f :: a -> b -> b
f z :: b
z (Product x :: 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 _ = Product a -> a
forall a. Product a -> a
getProduct
length :: Product a -> Int
length _ = 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 _ = 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 x :: a
x) = [a
x]
instance Foldable First where
foldMap :: (a -> m) -> First a -> m
foldMap f :: 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
instance Foldable Last where
foldMap :: (a -> m) -> Last a -> m
foldMap f :: 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
instance (Foldable f) => Foldable (Alt f) where
foldMap :: (a -> m) -> Alt f a -> m
foldMap f :: 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
instance (Foldable f) => Foldable (Ap f) where
foldMap :: (a -> m) -> Ap f a -> m
foldMap f :: 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
instance Foldable U1 where
foldMap :: (a -> m) -> U1 a -> m
foldMap _ _ = m
forall a. Monoid a => a
mempty
{-# INLINE foldMap #-}
fold :: U1 m -> m
fold _ = m
forall a. Monoid a => a
mempty
{-# INLINE fold #-}
foldr :: (a -> b -> b) -> b -> U1 a -> b
foldr _ z :: b
z _ = b
z
{-# INLINE foldr #-}
foldl :: (b -> a -> b) -> b -> U1 a -> b
foldl _ z :: b
z _ = b
z
{-# INLINE foldl #-}
foldl1 :: (a -> a -> a) -> U1 a -> a
foldl1 _ _ = [Char] -> a
forall a. [Char] -> a
errorWithoutStackTrace "foldl1: U1"
foldr1 :: (a -> a -> a) -> U1 a -> a
foldr1 _ _ = [Char] -> a
forall a. [Char] -> a
errorWithoutStackTrace "foldr1: U1"
length :: U1 a -> Int
length _ = 0
null :: U1 a -> Bool
null _ = Bool
True
elem :: a -> U1 a -> Bool
elem _ _ = Bool
False
sum :: U1 a -> a
sum _ = 0
product :: U1 a -> a
product _ = 1
deriving instance Foldable V1
deriving instance Foldable Par1
deriving instance Foldable f => Foldable (Rec1 f)
deriving instance Foldable (K1 i c)
deriving instance Foldable f => Foldable (M1 i c f)
deriving instance (Foldable f, Foldable g) => Foldable (f :+: g)
deriving instance (Foldable f, Foldable g) => Foldable (f :*: g)
deriving instance (Foldable f, Foldable g) => Foldable (f :.: g)
deriving instance Foldable UAddr
deriving instance Foldable UChar
deriving instance Foldable UDouble
deriving instance Foldable UFloat
deriving instance Foldable UInt
deriving instance Foldable UWord
deriving instance Foldable Down
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 f :: a -> b -> m b
f z0 :: b
z0 xs :: 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
where c :: (b -> m b) -> a -> b -> m b
c k :: b -> m b
k x :: a
x z :: 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 #-}
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 f :: b -> a -> m b
f z0 :: b
z0 xs :: 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
where c :: a -> (b -> m b) -> b -> m b
c x :: a
x k :: b -> m b
k z :: 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 #-}
traverse_ :: (Foldable t, Applicative f) => (a -> f b) -> t a -> f ()
traverse_ :: (a -> f b) -> t a -> f ()
traverse_ f :: 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 ())
where c :: a -> f b -> f b
c x :: a
x k :: 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_ :: (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_
mapM_ :: (Foldable t, Monad m) => (a -> m b) -> t a -> m ()
mapM_ :: (a -> m b) -> t a -> m ()
mapM_ f :: 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 ())
where c :: a -> m b -> m b
c x :: a
x k :: 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_ :: (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_
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 ())
where c :: f a -> f b -> f b
c m :: f a
m k :: 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 #-}
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 ())
where c :: m a -> m b -> m b
c m :: m a
m k :: 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 #-}
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
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
concat :: Foldable t => t [a] -> [a]
concat :: t [a] -> [a]
concat xs :: t [a]
xs = (forall b. (a -> b -> b) -> b -> b) -> [a]
forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
build (\c :: a -> b -> b
c n :: b
n -> ([a] -> b -> b) -> b -> t [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (\x :: [a]
x y :: 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 #-}
concatMap :: Foldable t => (a -> [b]) -> t a -> [b]
concatMap :: (a -> [b]) -> t a -> [b]
concatMap f :: a -> [b]
f xs :: t a
xs = (forall b. (b -> b -> b) -> b -> b) -> [b]
forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
build (\c :: b -> b -> b
c n :: b
n -> (a -> b -> b) -> b -> t a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (\x :: a
x b :: 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 #-}
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 :: 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
any :: Foldable t => (a -> Bool) -> t a -> Bool
any :: (a -> Bool) -> t a -> Bool
any p :: 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)
all :: Foldable t => (a -> Bool) -> t a -> Bool
all :: (a -> Bool) -> t a -> Bool
all p :: 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)
maximumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a
maximumBy :: (a -> a -> Ordering) -> t a -> a
maximumBy cmp :: 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' x :: a
x y :: a
y = case a -> a -> Ordering
cmp a
x a
y of
GT -> a
x
_ -> a
y
minimumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a
minimumBy :: (a -> a -> Ordering) -> t a -> a
minimumBy cmp :: 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' x :: a
x y :: a
y = case a -> a -> Ordering
cmp a
x a
y of
GT -> a
y
_ -> a
x
notElem :: (Foldable t, Eq a) => a -> t a -> Bool
notElem :: a -> t a -> Bool
notElem x :: 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
find :: Foldable t => (a -> Bool) -> t a -> Maybe a
find :: (a -> Bool) -> t a -> Maybe a
find p :: 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 (\ x :: 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))