- elem, notElem, concat, concatMap, and, or, any, all,
- sum, product, maximum, minimum)
+ elem, notElem, concat, concatMap, and, or, any, all,
+ sum, product, maximum, minimum)
import qualified Prelude (foldl, foldr, foldl1, foldr1)
import Control.Applicative
import Control.Monad (MonadPlus(..))
import Data.Maybe (fromMaybe, listToMaybe)
import Data.Monoid
import qualified Prelude (foldl, foldr, foldl1, foldr1)
import Control.Applicative
import Control.Monad (MonadPlus(..))
import Data.Maybe (fromMaybe, listToMaybe)
import Data.Monoid
-- > 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
-- > 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
- -- | Combine the elements of a structure using a monoid.
- fold :: Monoid m => t m -> m
- fold = foldMap id
-
- -- | Map each element of the structure to a monoid,
- -- and combine the results.
- foldMap :: Monoid m => (a -> m) -> t a -> m
- foldMap f = foldr (mappend . f) mempty
-
- -- | Right-associative fold of a structure.
- --
- -- @'foldr' f z = 'Prelude.foldr' f z . 'toList'@
- foldr :: (a -> b -> b) -> b -> t a -> b
- foldr f z t = 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 -> t b -> a
- foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) 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) -> t a -> a
- foldr1 f xs = fromMaybe (error "foldr1: empty structure")
- (foldr mf Nothing xs)
- where mf x Nothing = Just x
- mf x (Just y) = Just (f x y)
-
- -- | 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) -> t a -> a
- foldl1 f xs = fromMaybe (error "foldl1: empty structure")
- (foldl mf Nothing xs)
- where mf Nothing y = Just y
- mf (Just x) y = Just (f x y)
+ -- | Combine the elements of a structure using a monoid.
+ fold :: Monoid m => t m -> m
+ fold = foldMap id
+
+ -- | Map each element of the structure to a monoid,
+ -- and combine the results.
+ foldMap :: Monoid m => (a -> m) -> t a -> m
+ foldMap f = foldr (mappend . f) mempty
+
+ -- | Right-associative fold of a structure.
+ --
+ -- @'foldr' f z = 'Prelude.foldr' f z . 'toList'@
+ foldr :: (a -> b -> b) -> b -> t a -> b
+ foldr f z t = 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 -> t b -> a
+ foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) 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) -> t a -> a
+ foldr1 f xs = fromMaybe (error "foldr1: empty structure")
+ (foldr mf Nothing xs)
+ where mf x Nothing = Just x
+ mf x (Just y) = Just (f x y)
+
+ -- | 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) -> t a -> a
+ foldl1 f xs = fromMaybe (error "foldl1: empty structure")
+ (foldl mf Nothing xs)
+ where mf Nothing y = Just y
+ mf (Just x) y = Just (f x y)
where f' k x z = k $! f x z
-- | 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
where f' k x z = k $! f x z
-- | 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
where f' k x z = f x z >>= k
-- | Fold over the elements of a structure,
-- associating to the left, but strictly.
foldl' :: Foldable t => (a -> b -> a) -> a -> t b -> a
where f' k x z = f x z >>= k
-- | Fold over the elements of a structure,
-- associating to the left, but strictly.
foldl' :: Foldable t => (a -> b -> a) -> a -> t b -> a
where f' x k z = k $! f z x
-- | Monadic fold over the elements of a structure,
-- associating to the left, i.e. from left to right.
foldlM :: (Foldable t, Monad m) => (a -> b -> m a) -> a -> t b -> m a
where f' x k z = k $! f z x
-- | Monadic fold over the elements of a structure,
-- associating to the left, i.e. from left to right.
foldlM :: (Foldable t, Monad m) => (a -> b -> m a) -> a -> t b -> m a