foldl-1.4.9: Composable, streaming, and efficient left folds

Safe HaskellNone
LanguageHaskell2010

Control.Scanl

Contents

Description

This module provides efficient and streaming left map-with-accumulator that you can combine using Applicative style.

Import this module qualified to avoid clashing with the Prelude:

>>> import qualified Control.Scanl as SL

Use scan to apply a Fold to a list (or other Traversable structures) from left to right, and scanr to do so from right to left.

Note that the Scan type does not supersede the Fold type nor does the Fold type supersede the Scan type. Each type has a unique advantage.

For example, Scans can be chained end-to-end:

(>>>) :: Scan a b -> Scan b c -> Scan a c

In other words, Scan is an instance of the Category typeclass.

Folds cannot be chained end-to-end

Vice versa, Folds can produce a result even when fed no input:

extract :: Fold a b -> b

In other words, Fold is an instance of the Comonad typeclass.

A Scans cannot produce any output until provided with at least one input.

Synopsis

Scan Types

data Scan a b Source #

Efficient representation of a left map-with-accumulator that preserves the scan's step function and initial accumulator.

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

A 'Scan a b' processes elements of type a replacing each with a value of type b.

Constructors

Scan (a -> State x b) x

Scan step initial

Instances
Arrow Scan Source # 
Instance details

Defined in Control.Scanl

Methods

arr :: (b -> c) -> Scan b c #

first :: Scan b c -> Scan (b, d) (c, d) #

second :: Scan b c -> Scan (d, b) (d, c) #

(***) :: Scan b c -> Scan b' c' -> Scan (b, b') (c, c') #

(&&&) :: Scan b c -> Scan b c' -> Scan b (c, c') #

Profunctor Scan Source # 
Instance details

Defined in Control.Scanl

Methods

dimap :: (a -> b) -> (c -> d) -> Scan b c -> Scan a d #

lmap :: (a -> b) -> Scan b c -> Scan a c #

rmap :: (b -> c) -> Scan a b -> Scan a c #

(#.) :: Coercible c b => q b c -> Scan a b -> Scan a c #

(.#) :: Coercible b a => Scan b c -> q a b -> Scan a c #

Functor (Scan a) Source # 
Instance details

Defined in Control.Scanl

Methods

fmap :: (a0 -> b) -> Scan a a0 -> Scan a b #

(<$) :: a0 -> Scan a b -> Scan a a0 #

Applicative (Scan a) Source # 
Instance details

Defined in Control.Scanl

Methods

pure :: a0 -> Scan a a0 #

(<*>) :: Scan a (a0 -> b) -> Scan a a0 -> Scan a b #

liftA2 :: (a0 -> b -> c) -> Scan a a0 -> Scan a b -> Scan a c #

(*>) :: Scan a a0 -> Scan a b -> Scan a b #

(<*) :: Scan a a0 -> Scan a b -> Scan a a0 #

Category Scan Source # 
Instance details

Defined in Control.Scanl

Methods

id :: Scan a a #

(.) :: Scan b c -> Scan a b -> Scan a c #

Floating b => Floating (Scan a b) Source # 
Instance details

Defined in Control.Scanl

Methods

pi :: Scan a b #

exp :: Scan a b -> Scan a b #

log :: Scan a b -> Scan a b #

sqrt :: Scan a b -> Scan a b #

(**) :: Scan a b -> Scan a b -> Scan a b #

logBase :: Scan a b -> Scan a b -> Scan a b #

sin :: Scan a b -> Scan a b #

cos :: Scan a b -> Scan a b #

tan :: Scan a b -> Scan a b #

asin :: Scan a b -> Scan a b #

acos :: Scan a b -> Scan a b #

atan :: Scan a b -> Scan a b #

sinh :: Scan a b -> Scan a b #

cosh :: Scan a b -> Scan a b #

tanh :: Scan a b -> Scan a b #

asinh :: Scan a b -> Scan a b #

acosh :: Scan a b -> Scan a b #

atanh :: Scan a b -> Scan a b #

log1p :: Scan a b -> Scan a b #

expm1 :: Scan a b -> Scan a b #

log1pexp :: Scan a b -> Scan a b #

log1mexp :: Scan a b -> Scan a b #

Fractional b => Fractional (Scan a b) Source # 
Instance details

Defined in Control.Scanl

Methods

(/) :: Scan a b -> Scan a b -> Scan a b #

recip :: Scan a b -> Scan a b #

fromRational :: Rational -> Scan a b #

Num b => Num (Scan a b) Source # 
Instance details

Defined in Control.Scanl

Methods

(+) :: Scan a b -> Scan a b -> Scan a b #

(-) :: Scan a b -> Scan a b -> Scan a b #

(*) :: Scan a b -> Scan a b -> Scan a b #

negate :: Scan a b -> Scan a b #

abs :: Scan a b -> Scan a b #

signum :: Scan a b -> Scan a b #

fromInteger :: Integer -> Scan a b #

Semigroup b => Semigroup (Scan a b) Source # 
Instance details

Defined in Control.Scanl

Methods

(<>) :: Scan a b -> Scan a b -> Scan a b #

sconcat :: NonEmpty (Scan a b) -> Scan a b #

stimes :: Integral b0 => b0 -> Scan a b -> Scan a b #

Monoid b => Monoid (Scan a b) Source # 
Instance details

Defined in Control.Scanl

Methods

mempty :: Scan a b #

mappend :: Scan a b -> Scan a b -> Scan a b #

mconcat :: [Scan a b] -> Scan a b #

data ScanM m a b Source #

Like Scan, but monadic.

A 'ScanM m a b' processes elements of type a and results in a monadic value of type m b.

Constructors

ScanM (a -> StateT x m b) (m x)

ScanM step initial extract

Instances
Monad m => Arrow (ScanM m) Source # 
Instance details

Defined in Control.Scanl

Methods

arr :: (b -> c) -> ScanM m b c #

first :: ScanM m b c -> ScanM m (b, d) (c, d) #

second :: ScanM m b c -> ScanM m (d, b) (d, c) #

(***) :: ScanM m b c -> ScanM m b' c' -> ScanM m (b, b') (c, c') #

(&&&) :: ScanM m b c -> ScanM m b c' -> ScanM m b (c, c') #

Functor m => Profunctor (ScanM m) Source # 
Instance details

Defined in Control.Scanl

Methods

dimap :: (a -> b) -> (c -> d) -> ScanM m b c -> ScanM m a d #

lmap :: (a -> b) -> ScanM m b c -> ScanM m a c #

rmap :: (b -> c) -> ScanM m a b -> ScanM m a c #

(#.) :: Coercible c b => q b c -> ScanM m a b -> ScanM m a c #

(.#) :: Coercible b a => ScanM m b c -> q a b -> ScanM m a c #

Monad m => Category (ScanM m :: Type -> Type -> Type) Source # 
Instance details

Defined in Control.Scanl

Methods

id :: ScanM m a a #

(.) :: ScanM m b c -> ScanM m a b -> ScanM m a c #

Functor m => Functor (ScanM m a) Source # 
Instance details

Defined in Control.Scanl

Methods

fmap :: (a0 -> b) -> ScanM m a a0 -> ScanM m a b #

(<$) :: a0 -> ScanM m a b -> ScanM m a a0 #

Applicative m => Applicative (ScanM m a) Source # 
Instance details

Defined in Control.Scanl

Methods

pure :: a0 -> ScanM m a a0 #

(<*>) :: ScanM m a (a0 -> b) -> ScanM m a a0 -> ScanM m a b #

liftA2 :: (a0 -> b -> c) -> ScanM m a a0 -> ScanM m a b -> ScanM m a c #

(*>) :: ScanM m a a0 -> ScanM m a b -> ScanM m a b #

(<*) :: ScanM m a a0 -> ScanM m a b -> ScanM m a a0 #

(Monad m, Floating b) => Floating (ScanM m a b) Source # 
Instance details

Defined in Control.Scanl

Methods

pi :: ScanM m a b #

exp :: ScanM m a b -> ScanM m a b #

log :: ScanM m a b -> ScanM m a b #

sqrt :: ScanM m a b -> ScanM m a b #

(**) :: ScanM m a b -> ScanM m a b -> ScanM m a b #

logBase :: ScanM m a b -> ScanM m a b -> ScanM m a b #

sin :: ScanM m a b -> ScanM m a b #

cos :: ScanM m a b -> ScanM m a b #

tan :: ScanM m a b -> ScanM m a b #

asin :: ScanM m a b -> ScanM m a b #

acos :: ScanM m a b -> ScanM m a b #

atan :: ScanM m a b -> ScanM m a b #

sinh :: ScanM m a b -> ScanM m a b #

cosh :: ScanM m a b -> ScanM m a b #

tanh :: ScanM m a b -> ScanM m a b #

asinh :: ScanM m a b -> ScanM m a b #

acosh :: ScanM m a b -> ScanM m a b #

atanh :: ScanM m a b -> ScanM m a b #

log1p :: ScanM m a b -> ScanM m a b #

expm1 :: ScanM m a b -> ScanM m a b #

log1pexp :: ScanM m a b -> ScanM m a b #

log1mexp :: ScanM m a b -> ScanM m a b #

(Monad m, Fractional b) => Fractional (ScanM m a b) Source # 
Instance details

Defined in Control.Scanl

Methods

(/) :: ScanM m a b -> ScanM m a b -> ScanM m a b #

recip :: ScanM m a b -> ScanM m a b #

fromRational :: Rational -> ScanM m a b #

(Monad m, Num b) => Num (ScanM m a b) Source # 
Instance details

Defined in Control.Scanl

Methods

(+) :: ScanM m a b -> ScanM m a b -> ScanM m a b #

(-) :: ScanM m a b -> ScanM m a b -> ScanM m a b #

(*) :: ScanM m a b -> ScanM m a b -> ScanM m a b #

negate :: ScanM m a b -> ScanM m a b #

abs :: ScanM m a b -> ScanM m a b #

signum :: ScanM m a b -> ScanM m a b #

fromInteger :: Integer -> ScanM m a b #

(Monad m, Semigroup b) => Semigroup (ScanM m a b) Source # 
Instance details

Defined in Control.Scanl

Methods

(<>) :: ScanM m a b -> ScanM m a b -> ScanM m a b #

sconcat :: NonEmpty (ScanM m a b) -> ScanM m a b #

stimes :: Integral b0 => b0 -> ScanM m a b -> ScanM m a b #

(Monad m, Monoid b) => Monoid (ScanM m a b) Source # 
Instance details

Defined in Control.Scanl

Methods

mempty :: ScanM m a b #

mappend :: ScanM m a b -> ScanM m a b -> ScanM m a b #

mconcat :: [ScanM m a b] -> ScanM m a b #

Scanning

scan :: Traversable t => Scan a b -> t a -> t b Source #

Apply a strict left Scan to a Traversable container

scanM :: (Traversable t, Monad m) => ScanM m a b -> t a -> m (t b) Source #

Like scan but monadic

scanr :: Traversable t => Scan a b -> t a -> t b Source #

Like scan but start scanning from the right

prescan :: Fold a b -> Scan a b Source #

Convert a Fold into a prescan

"Prescan" means that the last element of the scan is not included

postscan :: Fold a b -> Scan a b Source #

Convert a Fold into a postscan

"Postscan" means that the first element of the scan is not included

Utilities

 

purely :: (forall x. (a -> State x b) -> x -> r) -> Scan a b -> r Source #

Upgrade a scan to accept the Scan type

purely_ :: (forall x. (x -> a -> (x, b)) -> x -> r) -> Scan a b -> r Source #

Upgrade a more traditional scan to accept the Scan type

impurely :: (forall x. (a -> StateT x m b) -> m x -> r) -> ScanM m a b -> r Source #

Upgrade a monadic scan to accept the ScanM type

impurely_ :: Monad m => (forall x. (x -> a -> m (x, b)) -> m x -> r) -> ScanM m a b -> r Source #

Upgrade a more traditional monadic scan to accept the ScanM type

generalize :: Monad m => Scan a b -> ScanM m a b Source #

Generalize a Scan to a ScanM

generalize (pure r) = pure r

generalize (f <*> x) = generalize f <*> generalize x

simplify :: ScanM Identity a b -> Scan a b Source #

Simplify a pure ScanM to a Scan

simplify (pure r) = pure r

simplify (f <*> x) = simplify f <*> simplify x

hoists :: (forall x. m x -> n x) -> ScanM m a b -> ScanM n a b Source #

Shift a ScanM from one monad to another with a morphism such as lift or liftIO; the effect is the same as hoist.

arrM :: Monad m => (b -> m c) -> ScanM m b c Source #

premap :: (a -> b) -> Scan b r -> Scan a r Source #

(premap f scaner) returns a new Scan where f is applied at each step

scan (premap f scaner) list = scan scaner (map f list)
premap id = id

premap (f . g) = premap g . premap f
premap k (pure r) = pure r

premap k (f <*> x) = premap k f <*> premap k x

premapM :: Monad m => (a -> m b) -> ScanM m b r -> ScanM m a r Source #

(premapM f scaner) returns a new ScanM where f is applied to each input element

premapM return = id

premapM (f <=< g) = premap g . premap f
premapM k (pure r) = pure r

premapM k (f <*> x) = premapM k f <*> premapM k x