Module Data.Foldable

Data structures that can be folded.

Imports

import Data.wrapper.Boolean as Boolean
import Data.wrapper.Dual as Dual
import Data.wrapper.Endo as Endo
import Data.wrapper.Identity as Identity
import Data.Monoid as Monoid
import Data.wrapper.Num as Num
import frege.Prelude as Prelude
import Prelude.PreludeArrays as PreludeArrays
import Prelude.PreludeBase as PreludeBase
import Prelude.PreludeDecimal as PreludeDecimal
import Prelude.PreludeIO as PreludeIO
import Prelude.PreludeList as PreludeList
import Prelude.PreludeMonad as PreludeMonad
import Prelude.PreludeText as PreludeText
import Java.util.Regex as Regexp

Table of Content

Definitions

class Foldable t

foldr' ∷ Foldable t ⇒ (a → b → b) → b → t a → b

foldrM ∷ (Foldable t, Monad m) ⇒ (a → b → m b) → b → t a → m b

foldl' ∷ Foldable t ⇒ (a → b → a) → a → t b → a

foldlM ∷ (Foldable t, Monad m) ⇒ (a → b → m a) → a → t b → m a

traverse_ ∷ (Foldable t, Applicative f) ⇒ (a → f b) → t a → f ()

for_ ∷ (Foldable t, Applicative f) ⇒ t a → (a → f b) → f ()

mapM_ ∷ (Foldable t, Monad m) ⇒ (a → m b) → t a → m ()

forM_ ∷ (Foldable t, Monad m) ⇒ t a → (a → m b) → m ()

sequenceA_ ∷ (Foldable t, Applicative f) ⇒ t (f a) → f ()

sequence_ ∷ (Foldable t, Monad m) ⇒ t (m a) → m ()

msum ∷ (Foldable t, MonadPlus m) ⇒ t (m a) → m a

concat ∷ Foldable t ⇒ t [a] → [a]

concatMap ∷ Foldable t ⇒ (a → [b]) → t a → [b]

and ∷ Foldable t ⇒ t Bool → Bool

or ∷ Foldable t ⇒ t Bool → Bool

any ∷ Foldable t ⇒ (a → Bool) → t a → Bool

all ∷ Foldable t ⇒ (a → Bool) → t a → Bool

sum ∷ (Foldable t, Num a) ⇒ t a → a

product ∷ (Foldable t, Num a) ⇒ t a → a

maximum ∷ (Foldable t, Ord a) ⇒ t a → a

maximumBy ∷ Foldable t ⇒ (a → a → Ordering) → t a → a

minimum ∷ (Foldable t, Ord a) ⇒ t a → a

minimumBy ∷ Foldable t ⇒ (a → a → Ordering) → t a → a

elem ∷ (Foldable t, Eq a) ⇒ a → t a → Bool

notElem ∷ (Foldable t, Eq a) ⇒ a → t a → Bool

find ∷ Foldable t ⇒ (a → Bool) → t a → Maybe a
Instances

instance Foldable Identity

instance Foldable Maybe

instance Foldable []
Functions and Values by Type

Definitions

class Foldable t

Data structures that can be folded.

Minimal complete definition: Foldable.foldMap or Foldable.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 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

Known Instances

Maybe, Identity.Identity, []

Member Functions

fold ∷ (Foldable t, Monoid m) ⇒ t m → m

Combine the elements of a structure using a monoid.

fold1 ∷ (Foldable t, Semigroup m) ⇒ t m → m

versions without base case

A variant of fold that has no base case, and thus may only be applied to non-empty structures.

(not in Haskell's Foldable, because they have no Semigroup)

foldMap ∷ (Foldable t, Monoid m) ⇒ (a → m) → t a → m

Map each element of the structure to a monoid, and combine the results.

foldMap1 ∷ (Foldable t, Semigroup m) ⇒ (a → m) → t a → m

A variant of foldMap that has no base case, and thus may only be applied to non-empty structures.

(not in Haskell's Foldable, because they have no Semigroup)

foldl ∷ Foldable t ⇒ (a → b → a) → a → t b → a

Left-associative fold of a structure.

foldl1 ∷ Foldable t ⇒ (a → a → a) → t a → a

nowarn: not easy enough

A variant of foldl that has no base case, and thus may only be applied to non-empty structures.

foldr ∷ Foldable t ⇒ (a → b → b) → b → t a → b

Right-associative fold of a structure.

foldr1 ∷ Foldable t ⇒ (a → a → a) → t a → a

nowarn: not easy enough

A variant of foldr that has no base case, and thus may only be applied to non-empty structures.

foldr' ∷ Foldable t ⇒ (a → b → b) → b → t a → b

Fold over the elements of a structure, associating to the right, but strictly.

foldrM ∷ (Foldable t, Monad m) ⇒ (a → b → m b) → b → t a → m b

Monadic fold over the elements of a structure, associating to the right, i.e. from right to left.

foldl' ∷ Foldable t ⇒ (a → b → a) → a → t b → a

Fold over the elements of a structure, associating to the left, but strictly.

foldlM ∷ (Foldable t, Monad m) ⇒ (a → b → m a) → a → t b → m a

Monadic fold over the elements of a structure, associating to the left, i.e. from left to right.

traverse_ ∷ (Foldable t, Applicative f) ⇒ (a → f b) → t a → f ()

Map each element of a structure to an action, evaluate these actions from left to right, and ignore the results.

for_ ∷ (Foldable t, Applicative f) ⇒ t a → (a → f b) → f ()

for_ is traverse_ with its arguments flipped.

mapM_ ∷ (Foldable t, Monad m) ⇒ (a → m b) → t a → m ()

Map each element of a structure to a monadic action, evaluate these actions from left to right, and ignore the results.

forM_ ∷ (Foldable t, Monad m) ⇒ t a → (a → m b) → m ()

forM_ is mapM_ with its arguments flipped.

sequenceA_ ∷ (Foldable t, Applicative f) ⇒ t (f a) → f ()

Evaluate each action in the structure from left to right, and ignore the results.

sequence_ ∷ (Foldable t, Monad m) ⇒ t (m a) → m ()

Evaluate each monadic action in the structure from left to right, and ignore the results.

msum ∷ (Foldable t, MonadPlus m) ⇒ t (m a) → m a

The sum of a collection of actions, generalizing concat.

concat ∷ Foldable t ⇒ t [a] → [a]

The concatenation of all the elements of a container of lists.

concatMap ∷ Foldable t ⇒ (a → [b]) → t a → [b]

Map a function over all the elements of a container and concatenate the resulting lists.

and ∷ Foldable t ⇒ t Bool → Bool

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.

or ∷ Foldable t ⇒ t Bool → Bool

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.

any ∷ Foldable t ⇒ (a → Bool) → t a → Bool

Determines whether any element of the structure satisfies the predicate.

all ∷ Foldable t ⇒ (a → Bool) → t a → Bool

Determines whether all elements of the structure satisfy the predicate.

sum ∷ (Foldable t, Num a) ⇒ t a → a

The sum function computes the sum of the numbers of a structure.

product ∷ (Foldable t, Num a) ⇒ t a → a

The product function computes the product of the numbers of a structure.

maximum ∷ (Foldable t, Ord a) ⇒ t a → a

The largest element of a non-empty structure.

maximumBy ∷ Foldable t ⇒ (a → a → Ordering) → t a → a

The largest element of a non-empty structure with respect to the given comparison function.

minimum ∷ (Foldable t, Ord a) ⇒ t a → a

The least element of a non-empty structure.

minimumBy ∷ Foldable t ⇒ (a → a → Ordering) → t a → a

The least element of a non-empty structure with respect to the given comparison function.

elem ∷ (Foldable t, Eq a) ⇒ a → t a → Bool

Does the element occur in the structure?

notElem ∷ (Foldable t, Eq a) ⇒ a → t a → Bool

notElem is the negation of elem.

find ∷ Foldable t ⇒ (a → Bool) → t a → Maybe a

The find function takes a predicate and a structure and returns the leftmost element of the structure matching the predicate, or Maybe.Nothing if there is no such element.

Instances

instance Foldable Identity

Member Functions

fold ∷ Monoid 𝖆 ⇒ Identity 𝖆 → 𝖆: inherited from Foldable.fold
fold1 ∷ Semigroup 𝖆 ⇒ Identity 𝖆 → 𝖆: inherited from Foldable.fold1
foldMap ∷ Monoid 𝖇 ⇒ (𝖆 → 𝖇) → Identity 𝖆 → 𝖇
foldMap1 ∷ Semigroup 𝖇 ⇒ (𝖆 → 𝖇) → Identity 𝖆 → 𝖇: inherited from Foldable.foldMap1
foldl ∷ (𝖆 → 𝖇 → 𝖆) → 𝖆 → Identity 𝖇 → 𝖆: inherited from Foldable.foldl
foldl1 ∷ (𝖆 → 𝖆 → 𝖆) → Identity 𝖆 → 𝖆: inherited from Foldable.foldl1
foldr ∷ (𝖆 → 𝖇 → 𝖇) → 𝖇 → Identity 𝖆 → 𝖇: inherited from Foldable.foldr
foldr1 ∷ (𝖆 → 𝖆 → 𝖆) → Identity 𝖆 → 𝖆: inherited from Foldable.foldr1

instance Foldable Maybe

Member Functions

fold ∷ Monoid 𝖆 ⇒ Maybe 𝖆 → 𝖆: inherited from Foldable.fold
fold1 ∷ Semigroup 𝖆 ⇒ Maybe 𝖆 → 𝖆: inherited from Foldable.fold1
foldMap ∷ Monoid 𝖇 ⇒ (𝖆 → 𝖇) → Maybe 𝖆 → 𝖇: inherited from Foldable.foldMap
foldMap1 ∷ Semigroup 𝖇 ⇒ (𝖆 → 𝖇) → Maybe 𝖆 → 𝖇: inherited from Foldable.foldMap1
foldl ∷ (𝖆 → 𝖇 → 𝖆) → 𝖆 → Maybe 𝖇 → 𝖆
foldl1 ∷ (𝖆 → 𝖆 → 𝖆) → Maybe 𝖆 → 𝖆: inherited from Foldable.foldl1
foldr ∷ (𝖆 → 𝖇 → 𝖇) → 𝖇 → Maybe 𝖆 → 𝖇
foldr1 ∷ (𝖆 → 𝖆 → 𝖆) → Maybe 𝖆 → 𝖆: inherited from Foldable.foldr1

instance Foldable []

Member Functions

fold ∷ Monoid 𝖆 ⇒ [𝖆] → 𝖆: inherited from Foldable.fold
fold1 ∷ Semigroup 𝖆 ⇒ [𝖆] → 𝖆: inherited from Foldable.fold1
foldMap ∷ Monoid 𝖇 ⇒ (𝖆 → 𝖇) → [𝖆] → 𝖇: inherited from Foldable.foldMap
foldMap1 ∷ Semigroup 𝖇 ⇒ (𝖆 → 𝖇) → [𝖆] → 𝖇: inherited from Foldable.foldMap1
foldl ∷ (𝖆 → 𝖇 → 𝖆) → 𝖆 → [𝖇] → 𝖆
foldl1 ∷ (𝖆 → 𝖆 → 𝖆) → [𝖆] → 𝖆: inherited from Foldable.foldl1
foldr ∷ (𝖆 → 𝖇 → 𝖇) → 𝖇 → [𝖆] → 𝖇
foldr1 ∷ (𝖆 → 𝖆 → 𝖆) → [𝖆] → 𝖆: inherited from Foldable.foldr1

Functions and Values by Type

(𝖆 → 𝖆 → 𝖆) → Identity 𝖆 → 𝖆: Foldable_Identity.foldr1, Foldable_Identity.foldl1
(𝖆 → 𝖆 → 𝖆) → Maybe 𝖆 → 𝖆: Foldable_Maybe.foldr1, Foldable_Maybe.foldl1
(𝖆 → 𝖆 → 𝖆) → [𝖆] → 𝖆: Foldable_[].foldr1, Foldable_[].foldl1
Foldable t ⇒ t Bool → Bool: and, or
Monoid 𝖆 ⇒ Identity 𝖆 → 𝖆: Foldable_Identity.fold
Monoid 𝖆 ⇒ Maybe 𝖆 → 𝖆: Foldable_Maybe.fold
Monoid 𝖆 ⇒ [𝖆] → 𝖆: Foldable_[].fold
Semigroup 𝖆 ⇒ Identity 𝖆 → 𝖆: Foldable_Identity.fold1
Semigroup 𝖆 ⇒ Maybe 𝖆 → 𝖆: Foldable_Maybe.fold1
Semigroup 𝖆 ⇒ [𝖆] → 𝖆: Foldable_[].fold1
(𝖆 → 𝖇 → 𝖆) → 𝖆 → Identity 𝖇 → 𝖆: Foldable_Identity.foldl
(𝖆 → 𝖇 → 𝖆) → 𝖆 → Maybe 𝖇 → 𝖆: Foldable_Maybe.foldl
(𝖆 → 𝖇 → 𝖆) → 𝖆 → [𝖇] → 𝖆: Foldable_[].foldl
(𝖆 → 𝖇 → 𝖇) → 𝖇 → Identity 𝖆 → 𝖇: Foldable_Identity.foldr
(𝖆 → 𝖇 → 𝖇) → 𝖇 → Maybe 𝖆 → 𝖇: Foldable_Maybe.foldr
(𝖆 → 𝖇 → 𝖇) → 𝖇 → [𝖆] → 𝖇: Foldable_[].foldr
Foldable t ⇒ (a → a → Ordering) → t a → a: maximumBy, minimumBy
Foldable t ⇒ (a → a → a) → t a → a: Foldable.foldr1, Foldable.foldl1
Foldable t ⇒ (a → Bool) → t a → Maybe a: find
Foldable t ⇒ (a → Bool) → t a → Bool: all, any
Foldable t ⇒ t [a] → [a]: concat
(Foldable t, Monoid m) ⇒ t m → m: Foldable.fold
(Foldable t, Semigroup m) ⇒ t m → m: Foldable.fold1
(Foldable t, Eq a) ⇒ a → t a → Bool: elem, notElem
(Foldable t, Num a) ⇒ t a → a: product, sum
(Foldable t, Ord a) ⇒ t a → a: maximum, minimum
Monoid 𝖇 ⇒ (𝖆 → 𝖇) → Identity 𝖆 → 𝖇: Foldable_Identity.foldMap
Monoid 𝖇 ⇒ (𝖆 → 𝖇) → Maybe 𝖆 → 𝖇: Foldable_Maybe.foldMap
Monoid 𝖇 ⇒ (𝖆 → 𝖇) → [𝖆] → 𝖇: Foldable_[].foldMap
Semigroup 𝖇 ⇒ (𝖆 → 𝖇) → Identity 𝖆 → 𝖇: Foldable_Identity.foldMap1
Semigroup 𝖇 ⇒ (𝖆 → 𝖇) → Maybe 𝖆 → 𝖇: Foldable_Maybe.foldMap1
Semigroup 𝖇 ⇒ (𝖆 → 𝖇) → [𝖆] → 𝖇: Foldable_[].foldMap1
Foldable t ⇒ (a → b → a) → a → t b → a: foldl', Foldable.foldl
Foldable t ⇒ (a → b → b) → b → t a → b: foldr', Foldable.foldr
Foldable t ⇒ (a → [b]) → t a → [b]: concatMap
(Foldable t, Monoid m) ⇒ (a → m) → t a → m: Foldable.foldMap
(Foldable t, Semigroup m) ⇒ (a → m) → t a → m: Foldable.foldMap1
(Foldable t, Applicative f) ⇒ t (f a) → f (): sequenceA_
(Foldable t, Monad m) ⇒ t (m a) → m (): sequence_
(Foldable t, MonadPlus m) ⇒ t (m a) → m a: msum
(Foldable t, Applicative f) ⇒ (a → f b) → t a → f (): traverse_
(Foldable t, Applicative f) ⇒ t a → (a → f b) → f (): for_
(Foldable t, Monad m) ⇒ (a → b → m a) → a → t b → m a: foldlM
(Foldable t, Monad m) ⇒ (a → b → m b) → b → t a → m b: foldrM
(Foldable t, Monad m) ⇒ (a → m b) → t a → m (): mapM_
(Foldable t, Monad m) ⇒ t a → (a → m b) → m (): forM_