Control.Foldl

This module provides efficient and streaming left folds that you can combine using Applicative style.

Import this module qualified to avoid clashing with the Prelude:

>>> import qualified Control.Foldl as L

Use fold to apply a Fold to a list:

>>> L.fold L.sum [1..100]
5050

Folds are Applicatives, so you can combine them using Applicative combinators:

>>> import Control.Applicative
>>> let average = (/) <$> L.sum <*> L.genericLength

These combined folds will still traverse the list only once, streaming efficiently over the list in constant space without space leaks:

>>> L.fold average [1..10000000]
5000000.5
>>> L.fold ((,) <$> L.minimum <*> L.maximum) [1..10000000]
(Just 1,Just 10000000)

You can also unpack the Fold type if you want to extract the individual components of combined folds for use with your own customized folding utilities:

 case ((/) <$> L.sum <*> L.genericLength) of
     L.Foldl step begin done -> ...

Fold Types

data Fold a b

Efficient representation of a left fold that preserves the fold's step function, initial accumulator, and extraction function

This allows the Applicative instance to assemble derived folds that traverse the container only once

Constructors

forall x . Fold (x -> a -> x) x (x -> b)

Instances

Functor (Fold a)

Applicative (Fold a)

fold :: Fold a b -> [a] -> b

Apply a strict left Fold to a list and extract the final result

data FoldM m a b

Like Fold, but monadic

Constructors

forall x . FoldM (x -> a -> m x) (m x) (x -> m b)

Instances

Monad m => Functor (FoldM m a)

Monad m => Applicative (FoldM m a)

foldM :: Monad m => FoldM m a b -> [a] -> m b

Like fold, but monadic

Folds

mconcat :: Monoid a => Fold a a

Fold all values within a container using mappend and mempty

foldMap :: Monoid w => (a -> w) -> (w -> b) -> Fold a b

Convert a "foldMap" to a Fold

head :: Fold a (Maybe a)

Get the first element of a container or return Nothing if the container is empty

last :: Fold a (Maybe a)

Get the last element of a container or return Nothing if the container is empty

null :: Fold a Bool

Returns True if the container is empty, False otherwise

length :: Fold a Int

Return the length of the container

and :: Fold Bool Bool

Returns True if all elements are True, False otherwise

or :: Fold Bool Bool

Returns True if any element is True, False otherwise

all :: (a -> Bool) -> Fold a Bool

(all predicate) returns True if all elements satisfy the predicate, False otherwise

any :: (a -> Bool) -> Fold a Bool

(any predicate) returns True is any element satisfies the predicate, False otherwise

sum :: Num a => Fold a a

Computes the sum of all elements

product :: Num a => Fold a a

Computes the product all elements

maximum :: Ord a => Fold a (Maybe a)

Computes the maximum element

minimum :: Ord a => Fold a (Maybe a)

Computes the minimum element

elem :: Eq a => a -> Fold a Bool

(elem a) returns True if the container has an element equal to a, False otherwise

notElem :: Eq a => a -> Fold a Bool

(notElem a) returns False if the container has an element equal to a, True otherwise

find :: (a -> Bool) -> Fold a (Maybe a)

(find predicate) returns the first element that satisfies the predicate or Nothing if no element satisfies the predicate

index :: Int -> Fold a (Maybe a)

(index n) returns the nth element of the container, or Nothing if the container has an insufficient number of elements

elemIndex :: Eq a => a -> Fold a (Maybe Int)

(elemIndex a) returns the index of the first element that equals a, or Nothing if no element matches

findIndex :: (a -> Bool) -> Fold a (Maybe Int)

(findIndex predicate) returns the index of the first element that satisfies the predicate, or Nothing if no element satisfies the predicate

Generic Folds

genericLength :: Num b => Fold a b

Like length, except with a more general Num return value

genericIndex :: Integral i => i -> Fold a (Maybe a)

Like index, except with a more general Integral argument