Data.Fold

Scaners and Foldings

class Choice p => Scan p where

Minimal complete definition

interspersing

Methods

prefix1 :: a -> p a b -> p a b

postfix1 :: p a b -> a -> p a b

run1 :: a -> p a b -> b

Apply a Folding to a single element of input

interspersing :: a -> p a b -> p a b

Instances

Scan L

Scan L'

Scan L1

Scan L1'

Scan M

Scan M1

Scan R

Scan R1

class Scan p => Folding p where

Minimal complete definition

prefixOf, postfixOf, runOf, filtering

Methods

prefix :: Foldable t => t a -> p a b -> p a b

Partially apply a Folding to some initial input on the left.

prefixOf :: Fold s a -> s -> p a b -> p a b

postfix :: Foldable t => p a b -> t a -> p a b

postfixOf :: Fold s a -> p a b -> s -> p a b

run :: Foldable t => t a -> p a b -> b

Apply a Folding to a container full of input:

>>> run ["hello","world"] $ L id (++) []
"helloworld"

>>> run [1,2,3] $ L id (+) 0
6

runOf :: Fold s a -> s -> p a b -> b

filtering :: (a -> Bool) -> p a b -> p a b

Instances

Folding L

efficient prefix, leaky postfix

Folding L'

efficient prefix, leaky postfix

Folding M

efficient prefix, efficient postfix

Folding R

leaky prefix, efficient postfix

Combinators

beneath :: Profunctor p => Optic p Identity s t a b -> p a b -> p s t

Lift a Folding into a Prism.

This acts like a generalized notion of "costrength", when applied to a Folding, causing it to return the left-most value that fails to match the Prism, or the result of accumulating rewrapped in the Prism if everything matches.

>>> run [Left 1, Left 2, Left 3] $ beneath _Left $ R id (+) 0
Left 6

>>> run [Left 1, Right 2, Right 3] $ beneath _Left $ R id (+) 0
Right 2

beneath :: Prism s t a b -> p a b -> p s t
beneath :: Iso s t a b   -> p a b -> p s t

Scans

Left Scans

data L1 a b

A Mealy Machine

Constructors

forall c . L1 (c -> b) (c -> a -> c) (a -> c)

Instances

Arrow L1

ArrowChoice L1

Corepresentable L1

Profunctor L1

Choice L1

Closed L1

Strong L1

Costrong L1

Scan L1

AsL1' L1

AsRM1 L1

Category * L1

Cosieve L1 NonEmpty

Semigroupoid * L1

Monad (L1 a)

Functor (L1 a)

MonadFix (L1 a)

Applicative (L1 a)

Distributive (L1 a)

Representable (L1 a)

MonadZip (L1 a)

Pointed (L1 a)

Apply (L1 a)

MonadReader (NonEmpty a) (L1 a)

type Corep L1 = NonEmpty

type Rep (L1 a) = NonEmpty a

data L1' a b

A strict Mealy Machine

Constructors

forall c . L1' (c -> b) (c -> a -> c) (a -> c)

Instances

Arrow L1'

ArrowChoice L1'

Corepresentable L1'

Profunctor L1'

Choice L1'

Closed L1'

Strong L1'

Costrong L1'

Scan L1'

AsL1' L1'

AsRM1 L1'

Category * L1'

Cosieve L1' NonEmpty

Semigroupoid * L1'

Monad (L1' a)

Functor (L1' a)

MonadFix (L1' a)

Applicative (L1' a)

Distributive (L1' a)

Representable (L1' a)

Pointed (L1' a)

Apply (L1' a)

MonadReader (NonEmpty a) (L1' a)

type Corep L1' = NonEmpty

type Rep (L1' a) = NonEmpty a

Semigroup Scans

data M1 a b

A semigroup reducer

Constructors

forall m . M1 (m -> b) (a -> m) (m -> m -> m)

Instances

Arrow M1

ArrowChoice M1

Corepresentable M1

Profunctor M1

Choice M1

Closed M1

Strong M1

Costrong M1

Scan M1

AsRM1 M1

Category * M1

Cosieve M1 FreeSemigroup

Semigroupoid * M1

Monad (M1 a)

Functor (M1 a)

MonadFix (M1 a)

Applicative (M1 a)

Distributive (M1 a)

Representable (M1 a)

MonadZip (M1 a)

Pointed (M1 a)

Apply (M1 a)

MonadReader (FreeSemigroup a) (M1 a)

type Corep M1 = FreeSemigroup

type Rep (M1 a) = FreeSemigroup a

Right Scans

data R1 a b

A reversed Mealy machine

Constructors

forall c . R1 (c -> b) (a -> c -> c) (a -> c)

Instances

Arrow R1

ArrowChoice R1

Corepresentable R1

Profunctor R1

Choice R1

Closed R1

Strong R1

Costrong R1

Scan R1

AsRM1 R1

Category * R1

Cosieve R1 NonEmpty

Semigroupoid * R1

Monad (R1 a)

Functor (R1 a)

MonadFix (R1 a)

Applicative (R1 a)

Distributive (R1 a)

Representable (R1 a)

MonadZip (R1 a)

Pointed (R1 a)

Apply (R1 a)

MonadReader (NonEmpty a) (R1 a)

type Corep R1 = NonEmpty

type Rep (R1 a) = NonEmpty a

Foldings

Left Foldings

data L a b

A Moore Machine

Constructors

forall r . L (r -> b) (r -> a -> r) r

Instances

Corepresentable L

Profunctor L

Choice L

Closed L

Costrong L

Folding L

efficient prefix, leaky postfix

Scan L

AsL' L

We can convert from a lazy left folding to a strict left folding.

AsL1' L

AsRM L

We can convert from a lazy left folding to a right or monoidal fold

AsRM1 L

Cosieve L []

Monad (L a)

Functor (L a)

MonadFix (L a)

Applicative (L a)

Distributive (L a)

Representable (L a)

MonadZip (L a)

Comonad (L a)

ComonadApply (L a)

Apply (L a)

Bind (L a)

Extend (L a)

MonadReader [a] (L a)

type Corep L = []

type Rep (L a) = [a]

data L' a b

A strict left fold / strict Moore machine

Constructors

forall r . L' (r -> b) (r -> a -> r) r

Instances

Corepresentable L'

Profunctor L'

Choice L'

Closed L'

Costrong L'

Folding L'

efficient prefix, leaky postfix

Scan L'

AsL' L'

We can convert a lazy fold to itself

AsL1' L'

AsRM L'

We can convert from a strict left folding to a right or monoidal fold

AsRM1 L'

Cosieve L' []

Monad (L' a)

Functor (L' a)

MonadFix (L' a)

Applicative (L' a)

Distributive (L' a)

Representable (L' a)

MonadZip (L' a)

Comonad (L' a)

ComonadApply (L' a)

Apply (L' a)

Bind (L' a)

Extend (L' a)

MonadReader [a] (L' a)

type Corep L' = []

type Rep (L' a) = [a]

Monoidal Foldings

data M a b

A foldMap caught in amber. a.k.a. a monoidal reducer

Constructors

forall m . M (m -> b) (a -> m) (m -> m -> m) m

Instances

Corepresentable M

Profunctor M

Choice M

Closed M

Costrong M

Folding M

efficient prefix, efficient postfix

Scan M

AsRM M

We can convert from a monoidal fold to a lazy right fold

AsRM1 M

Cosieve M FreeMonoid

Monad (M a)

Functor (M a)

MonadFix (M a)

Applicative (M a)

Distributive (M a)

Representable (M a)

MonadZip (M a)

Comonad (M a)

ComonadApply (M a)

Apply (M a)

Bind (M a)

Extend (M a)

MonadReader (FreeMonoid a) (M a)

type Corep M = FreeMonoid

type Rep (M a) = FreeMonoid a

Right Foldings

data R a b

right folds / a reversed Moore machine

Constructors

forall r . R (r -> b) (a -> r -> r) r

Instances

Corepresentable R

Profunctor R

Choice R

Closed R

Costrong R

Folding R

leaky prefix, efficient postfix

Scan R

AsRM R

We can convert from a lazy right fold to a monoidal fold

AsRM1 R

Cosieve R []

Monad (R a)

Functor (R a)

MonadFix (R a)

Applicative (R a)

Distributive (R a)

Representable (R a)

MonadZip (R a)

Comonad (R a)

ComonadApply (R a)

Apply (R a)

Bind (R a)

Extend (R a)

MonadReader [a] (R a)

type Corep R = []

type Rep (R a) = [a]

Homomorphisms

Scan Homomorphisms

We define f to be a scan homomorphism between p and q when:

f :: forall a b. p a b -> q a b

run1 xs (f φ)        ≡ run1 xs φ
prefix1 xs (f φ)     ≡ f (prefix1 xs φ)
postfix1 (f φ) xs    ≡ f (postfix1 φ xs)
dimap l r (f φ)      ≡ f (dimap l r φ)
pure a               ≡ f (pure a)
f φ <*> f ψ          ≡ f (φ <*> ψ)
return a             ≡ f (return a)
f φ >>= f . k        ≡ f (φ >>= k)
interspersing a (f φ) ≡ f (interspersing a φ)

Furthermore,

left' (f φ) and f (left' φ) should agree whenever either answer is Right

right' (f φ) and f (right' φ) should agree whenever either answer is Left

class AsRM1 p where

Minimal complete definition

Nothing

Methods

asM1 :: p a b -> M1 a b

asM1 is a scan homomorphism to a semigroup reducer

asR1 :: p a b -> R1 a b

asM1 is a scan homomorphism to a right scan

Instances

AsRM1 L

AsRM1 L'

AsRM1 L1

AsRM1 L1'

AsRM1 M

AsRM1 M1

AsRM1 R

AsRM1 R1

class AsRM1 p => AsL1' p where

Minimal complete definition

Nothing

Methods

asL1' :: p a b -> L1' a b

Scan homomorphism to a strict Mealy machine

Instances

AsL1' L

AsL1' L'

AsL1' L1

AsL1' L1'

Folding Homomorphisms

We define f to be a folding homomorphism between p and q when f is a scan homomorphism and additionally we can satisfy:

run xs (f φ)         ≡ run xs φ
runOf l xs (f φ)     ≡ runOf l xs φ
prefix xs (f φ)      ≡ f (prefix xs φ)
prefixOf l xs (f φ)  ≡ f (prefixOf l xs φ)
postfix (f φ) xs     ≡ f (postfix φ xs)
postfixOf l (f φ) xs ≡ f (postfixOf l φ xs)
extract (f φ)        ≡ extract φ
filtering p (f φ)     ≡ f (filtering p φ)

Note: A law including extend is explicitly excluded. To work consistenly across foldings, use prefix and postfix instead.

class AsRM1 p => AsRM p where

Minimal complete definition

Nothing

Methods

asM :: p a b -> M a b

asM is a folding homomorphism to a monoidal folding

run xs (asM φ)         ≡ run xs φ
prefix xs (asM φ)      ≡ asM (prefix xs φ)
prefixOf l xs (asM φ)  ≡ asM (prefixOf l xs φ)
postfix (asM φ) xs     ≡ asM (postfix φ xs)
postfixOf l (asM φ) xs ≡ asM (postfixOf l φ xs)
left' (asM φ)          ≡ asM (left' φ)
right' (asM φ)         ≡ asM (right' φ)
dimap l r (asM φ)      ≡ asM (dimap l r φ)
extract (asM φ)        ≡ extract φ
pure a                  ≡ asM (pure a)
asM φ <*> asM ψ        ≡ asM (φ <*> ψ)
return a                ≡ asM (return a)
asM φ >>= asM . k      ≡ asM (φ >>= k)
filtering p (asM φ)     ≡ asM (filtering p φ)
interspersing a (asM φ) ≡ asM (interspersing a φ)

asR :: p a b -> R a b

asR is a folding homomorphism to a right folding

run xs (asR φ)         ≡ run xs φ
prefix xs (asR φ)      ≡ asR (prefix xs φ)
prefixOf l xs (asR φ)  ≡ asR (prefixOf l xs φ)
postfix (asR φ) xs     ≡ asR (postfix φ xs)
postfixOf l (asR φ) xs ≡ asR (postfixOf l φ xs)
left' (asR φ)          ≡ asR (left' φ)
right' (asR φ)         ≡ asR (right' φ)
dimap l r (asR φ)      ≡ asR (dimap l r φ)
extract (asR φ)        ≡ extract φ
pure a                  ≡ asR (pure a)
asR φ <*> asR ψ        ≡ asR (φ <*> ψ)
return a                ≡ asR (return a)
asR φ >>= asR . k      ≡ asR (φ >>= k)
filtering p (asR φ)     ≡ asR (filtering p φ)
interspersing a (asR φ) ≡ asR (interspersing a φ)

Instances

AsRM L

We can convert from a lazy left folding to a right or monoidal fold

AsRM L'

We can convert from a strict left folding to a right or monoidal fold

AsRM M

We can convert from a monoidal fold to a lazy right fold

AsRM R

We can convert from a lazy right fold to a monoidal fold

class (AsRM p, AsL1' p) => AsL' p where

Methods

asL' :: p a b -> L' a b

asL' is a folding homomorphism to a strict left folding

run xs (asL' φ)         ≡ run xs φ
prefix xs (asL' φ)      ≡ asL' (prefix xs φ)
prefixOf l xs (asL' φ)  ≡ asL' (prefixOf l xs φ)
postfix (asL' φ) xs     ≡ asL' (postfix φ xs)
postfixOf l (asL' φ) xs ≡ asL' (postfixOf l φ xs)
left' (asL' φ)          ≡ asL' (left' φ)
right' (asL' φ)         ≡ asL' (right' φ)
dimap l r (asL' φ)      ≡ asL' (dimap l r φ)
extract (asL' φ)        ≡ extract φ
pure a                   ≡ asL' (pure a)
asL' φ <*> asL' ψ       ≡ asL' (φ <*> ψ)
return a                 ≡ asL' (return a)
asL' φ >>= asL' . k     ≡ asL' (φ >>= k)
filtering p (asL' φ)     ≡ asL' (filtering p φ)
interspersing a (asL' φ) ≡ asL' (interspersing a φ)

Instances

AsL' L

We can convert from a lazy left folding to a strict left folding.

AsL' L'

We can convert a lazy fold to itself