| Copyright | (C) 2009-2013 Edward Kmett |
|---|---|
| License | BSD-style (see the file LICENSE) |
| Maintainer | Edward Kmett <ekmett@gmail.com> |
| Stability | experimental |
| Portability | non-portable |
| Safe Haskell | None |
| Language | Haskell98 |
Data.Fold
Contents
Description
Synopsis
- class Choice p => Scan p where
- class Scan p => Folding p where
- beneath :: Profunctor p => Optic p Identity s t a b -> p a b -> p s t
- data L1 a b = L1 (c -> b) (c -> a -> c) (a -> c)
- data L1' a b = L1' (c -> b) (c -> a -> c) (a -> c)
- data M1 a b = M1 (m -> b) (a -> m) (m -> m -> m)
- data R1 a b = R1 (c -> b) (a -> c -> c) (a -> c)
- data L a b = L (r -> b) (r -> a -> r) r
- data L' a b = L' (r -> b) (r -> a -> r) r
- data M a b = M (m -> b) (a -> m) (m -> m -> m) m
- data R a b = R (r -> b) (a -> r -> r) r
- class AsRM1 p where
- class AsRM1 p => AsL1' p where
- class AsRM1 p => AsRM p where
- class (AsRM p, AsL1' p) => AsL' p where
Scaners and Foldings
class Choice p => Scan p where #
Minimal complete definition
Methods
prefix1 :: a -> p a b -> p a b #
prefix1 :: Folding p => a -> p a b -> p a b #
postfix1 :: p a b -> a -> p a b #
postfix1 :: Folding p => p a b -> a -> p a b #
Apply a Folding to a single element of input
run1 :: Folding p => a -> p a b -> b #
Apply a Folding to a single element of input
interspersing :: a -> p a b -> p a b #
class Scan p => Folding p where #
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 (+) 06
Instances
| Folding L # | |
| Folding L' # | |
Defined in Data.Fold.L' | |
| Folding M # | |
| Folding R # | |
Combinators
beneath :: Profunctor p => Optic p Identity s t a b -> p a b -> p s t #
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 (+) 0Left 6
>>>run [Left 1, Right 2, Right 3] $ beneath _Left $ R id (+) 0Right 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
A Mealy Machine
Constructors
| L1 (c -> b) (c -> a -> c) (a -> c) |
Instances
| Arrow L1 # | |
| ArrowChoice L1 # | |
| Profunctor L1 # | |
| Corepresentable L1 # | |
| Choice L1 # | |
| Closed L1 # | |
Defined in Data.Fold.L1 | |
| Strong L1 # | |
| Costrong L1 # | |
| Scan L1 # | |
| AsL1' L1 # | |
| AsRM1 L1 # | |
| Cosieve L1 NonEmpty # | |
Defined in Data.Fold.L1 | |
| Monad (L1 a) # | |
| Functor (L1 a) # | |
| MonadFix (L1 a) # | |
Defined in Data.Fold.L1 | |
| Applicative (L1 a) # | |
| Distributive (L1 a) # | |
| Representable (L1 a) # | |
| MonadZip (L1 a) # | |
| Apply (L1 a) # | |
| Pointed (L1 a) # | |
Defined in Data.Fold.L1 | |
| Category L1 # | |
| Semigroupoid L1 # | |
| MonadReader (NonEmpty a) (L1 a) # | |
| type Corep L1 # | |
Defined in Data.Fold.L1 | |
| type Rep (L1 a) # | |
Defined in Data.Fold.L1 | |
A strict Mealy Machine
Constructors
| L1' (c -> b) (c -> a -> c) (a -> c) |
Instances
| Arrow L1' # | |
| ArrowChoice L1' # | |
| Profunctor L1' # | |
| Corepresentable L1' # | |
| Choice L1' # | |
| Closed L1' # | |
Defined in Data.Fold.L1' | |
| Strong L1' # | |
| Costrong L1' # | |
| Scan L1' # | |
| AsL1' L1' # | |
| AsRM1 L1' # | |
| Cosieve L1' NonEmpty # | |
Defined in Data.Fold.L1' | |
| Monad (L1' a) # | |
| Functor (L1' a) # | |
| MonadFix (L1' a) # | |
Defined in Data.Fold.L1' | |
| Applicative (L1' a) # | |
| Distributive (L1' a) # | |
| Representable (L1' a) # | |
| Apply (L1' a) # | |
| Pointed (L1' a) # | |
Defined in Data.Fold.L1' | |
| Category L1' # | |
| Semigroupoid L1' # | |
| MonadReader (NonEmpty a) (L1' a) # | |
| type Corep L1' # | |
Defined in Data.Fold.L1' | |
| type Rep (L1' a) # | |
Defined in Data.Fold.L1' | |
Semigroup Scans
A semigroup reducer
Constructors
| M1 (m -> b) (a -> m) (m -> m -> m) |
Instances
| Arrow M1 # | |
| ArrowChoice M1 # | |
| Profunctor M1 # | |
| Corepresentable M1 # | |
| Choice M1 # | |
| Closed M1 # | |
Defined in Data.Fold.M1 | |
| Strong M1 # | |
| Costrong M1 # | |
| Scan M1 # | |
| AsRM1 M1 # | |
| Cosieve M1 FreeSemigroup # | |
Defined in Data.Fold.M1 Methods cosieve :: M1 a b -> FreeSemigroup a -> b # | |
| Monad (M1 a) # | |
| Functor (M1 a) # | |
| MonadFix (M1 a) # | |
Defined in Data.Fold.M1 | |
| Applicative (M1 a) # | |
| Distributive (M1 a) # | |
| Representable (M1 a) # | |
| MonadZip (M1 a) # | |
| Apply (M1 a) # | |
| Pointed (M1 a) # | |
Defined in Data.Fold.M1 | |
| Category M1 # | |
| Semigroupoid M1 # | |
| MonadReader (FreeSemigroup a) (M1 a) # | |
Defined in Data.Fold.M1 Methods ask :: M1 a (FreeSemigroup a) # local :: (FreeSemigroup a -> FreeSemigroup a) -> M1 a a0 -> M1 a a0 # reader :: (FreeSemigroup a -> a0) -> M1 a a0 # | |
| type Corep M1 # | |
Defined in Data.Fold.M1 | |
| type Rep (M1 a) # | |
Defined in Data.Fold.M1 | |
Right Scans
A reversed Mealy machine
Constructors
| R1 (c -> b) (a -> c -> c) (a -> c) |
Instances
| Arrow R1 # | |
| ArrowChoice R1 # | |
| Profunctor R1 # | |
| Corepresentable R1 # | |
| Choice R1 # | |
| Closed R1 # | |
Defined in Data.Fold.R1 | |
| Strong R1 # | |
| Costrong R1 # | |
| Scan R1 # | |
| AsRM1 R1 # | |
| Cosieve R1 NonEmpty # | |
Defined in Data.Fold.R1 | |
| Monad (R1 a) # | |
| Functor (R1 a) # | |
| MonadFix (R1 a) # | |
Defined in Data.Fold.R1 | |
| Applicative (R1 a) # | |
| Distributive (R1 a) # | |
| Representable (R1 a) # | |
| MonadZip (R1 a) # | |
| Apply (R1 a) # | |
| Pointed (R1 a) # | |
Defined in Data.Fold.R1 | |
| Category R1 # | |
| Semigroupoid R1 # | |
| MonadReader (NonEmpty a) (R1 a) # | |
| type Corep R1 # | |
Defined in Data.Fold.R1 | |
| type Rep (R1 a) # | |
Defined in Data.Fold.R1 | |
Foldings
Left Foldings
A Moore Machine
Constructors
| L (r -> b) (r -> a -> r) r |
Instances
| Profunctor L # | |
| Corepresentable L # | |
| Choice L # | |
| Closed L # | |
Defined in Data.Fold.L | |
| Costrong L # | |
| Folding L # | |
| 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 [] # |
|
Defined in Data.Fold.L | |
| Monad (L a) # | |
| Functor (L a) # | |
| MonadFix (L a) # | |
Defined in Data.Fold.L | |
| 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 # | |
Defined in Data.Fold.L | |
| type Rep (L a) # | |
Defined in Data.Fold.L | |
A strict left fold / strict Moore machine
Constructors
| L' (r -> b) (r -> a -> r) r |
Instances
| Profunctor L' # | |
| Corepresentable L' # | |
| Choice L' # | |
| Closed L' # | |
Defined in Data.Fold.L' | |
| Costrong L' # | |
| Folding L' # | |
Defined in Data.Fold.L' | |
| 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' [] # | |
Defined in Data.Fold.L' | |
| Monad (L' a) # | |
| Functor (L' a) # | |
| MonadFix (L' a) # | |
Defined in Data.Fold.L' | |
| 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' # | |
Defined in Data.Fold.L' | |
| type Rep (L' a) # | |
Defined in Data.Fold.L' | |
Monoidal Foldings
A foldMap caught in amber. a.k.a. a monoidal reducer
Constructors
| M (m -> b) (a -> m) (m -> m -> m) m |
Instances
| Profunctor M # | |
| Corepresentable M # | |
| Choice M # | |
| Closed M # | |
Defined in Data.Fold.M | |
| Costrong M # | |
| Folding M # | |
| Scan M # | |
| AsRM M # | We can convert from a monoidal fold to a lazy right fold |
| AsRM1 M # | |
| Cosieve M FreeMonoid # | |
Defined in Data.Fold.M Methods cosieve :: M a b -> FreeMonoid a -> b # | |
| Monad (M a) # | |
| Functor (M a) # | |
| MonadFix (M a) # | |
Defined in Data.Fold.M | |
| 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) # | |
Defined in Data.Fold.M Methods ask :: M a (FreeMonoid a) # local :: (FreeMonoid a -> FreeMonoid a) -> M a a0 -> M a a0 # reader :: (FreeMonoid a -> a0) -> M a a0 # | |
| type Corep M # | |
Defined in Data.Fold.M | |
| type Rep (M a) # | |
Defined in Data.Fold.M | |
Right Foldings
right folds / a reversed Moore machine
Constructors
| R (r -> b) (a -> r -> r) r |
Instances
| Profunctor R # | |
| Corepresentable R # | |
| Choice R # | |
| Closed R # | |
Defined in Data.Fold.R | |
| Costrong R # | |
| Folding R # | |
| Scan R # | |
| AsRM R # | We can convert from a lazy right fold to a monoidal fold |
| AsRM1 R # | |
| Cosieve R [] # | |
Defined in Data.Fold.R | |
| Monad (R a) # | |
| Functor (R a) # | |
| MonadFix (R a) # | |
Defined in Data.Fold.R | |
| 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 # | |
Defined in Data.Fold.R | |
| type Rep (R a) # | |
Defined in Data.Fold.R | |
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
run1xs (f φ) ≡run1xs φprefix1xs (f φ) ≡ f (prefix1xs φ)postfix1(f φ) xs ≡ f (postfix1φ xs)dimapl r (f φ) ≡ f (dimapl r φ)purea ≡ f (purea) f φ<*>f ψ ≡ f (φ<*>ψ)returna ≡ f (returna) f φ>>=f . k ≡ f (φ>>=k)interspersinga (f φ) ≡ f (interspersinga φ)
Furthermore,
left' (f φ)f ( should agree whenever either answer is left' φ)Right
right' (f φ)f ( should agree whenever either answer is right' φ)Left
Methods
asM1 is a scan homomorphism to a semigroup reducer
asM1 is a scan homomorphism to a right scan
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:
runxs (f φ) ≡runxs φrunOfl xs (f φ) ≡runOfl xs φprefixxs (f φ) ≡ f (prefixxs φ)prefixOfl xs (f φ) ≡ f (prefixOfl xs φ)postfix(f φ) xs ≡ f (postfixφ xs)postfixOfl (f φ) xs ≡ f (postfixOfl φ xs)extract(f φ) ≡extractφfilteringp (f φ) ≡ f (filteringp φ)
Note: A law including extend is explicitly excluded. To work consistenly
across foldings, use prefix and postfix instead.
class AsRM1 p => AsRM p where #
Methods
asM is a folding homomorphism to a monoidal folding
runxs (asMφ) ≡runxs φprefixxs (asMφ) ≡asM(prefixxs φ)prefixOfl xs (asMφ) ≡asM(prefixOfl xs φ)postfix(asMφ) xs ≡asM(postfixφ xs)postfixOfl (asMφ) xs ≡asM(postfixOfl φ xs)left'(asMφ) ≡asM(left'φ)right'(asMφ) ≡asM(right'φ)dimapl r (asMφ) ≡asM(dimapl r φ)extract(asMφ) ≡extractφpurea ≡asM(purea)asMφ<*>asMψ ≡asM(φ<*>ψ)returna ≡asM(returna)asMφ>>=asM. k ≡asM(φ>>=k)filteringp (asMφ) ≡asM(filteringp φ)interspersinga (asMφ) ≡asM(interspersinga φ)
asR is a folding homomorphism to a right folding
runxs (asRφ) ≡runxs φprefixxs (asRφ) ≡asR(prefixxs φ)prefixOfl xs (asRφ) ≡asR(prefixOfl xs φ)postfix(asRφ) xs ≡asR(postfixφ xs)postfixOfl (asRφ) xs ≡asR(postfixOfl φ xs)left'(asRφ) ≡asR(left'φ)right'(asRφ) ≡asR(right'φ)dimapl r (asRφ) ≡asR(dimapl r φ)extract(asRφ) ≡extractφpurea ≡asR(purea)asRφ<*>asRψ ≡asR(φ<*>ψ)returna ≡asR(returna)asRφ>>=asR. k ≡asR(φ>>=k)filteringp (asRφ) ≡asR(filteringp φ)interspersinga (asRφ) ≡asR(interspersinga φ)
class (AsRM p, AsL1' p) => AsL' p where #
Minimal complete definition
Methods
asL' is a folding homomorphism to a strict left folding
runxs (asL'φ) ≡runxs φprefixxs (asL'φ) ≡asL'(prefixxs φ)prefixOfl xs (asL'φ) ≡asL'(prefixOfl xs φ)postfix(asL'φ) xs ≡asL'(postfixφ xs)postfixOfl (asL'φ) xs ≡asL'(postfixOfl φ xs)left'(asL'φ) ≡asL'(left'φ)right'(asL'φ) ≡asL'(right'φ)dimapl r (asL'φ) ≡asL'(dimapl r φ)extract(asL'φ) ≡extractφpurea ≡asL'(purea)asL'φ<*>asL'ψ ≡asL'(φ<*>ψ)returna ≡asL'(returna)asL'φ>>=asL'. k ≡asL'(φ>>=k)filteringp (asL'φ) ≡asL'(filteringp φ)interspersinga (asL'φ) ≡asL'(interspersinga φ)