Control.Scanl

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 Scan 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 Scan cannot produce any output until provided with at least one input.

Scan Types

data Scan a b

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

forall x. Scan (a -> State x b) x

Scan step initial

Instances

Arrow Scan

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

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

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

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

Category Scan

Defined in Control.Scanl

Methods

id :: forall (a :: k). Scan a a

(.) :: forall (b :: k) (c :: k) (a :: k). Scan b c -> Scan a b -> Scan a c

Applicative (Scan a)

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

Functor (Scan a)

Defined in Control.Scanl

Methods

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

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

Monoid b => Monoid (Scan a b)

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

Semigroup b => Semigroup (Scan a b)

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

Floating b => Floating (Scan a b)

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

Num b => Num (Scan a b)

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

Fractional b => Fractional (Scan a b)

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

data ScanM m a b

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

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

ScanM step initial extract

Instances

Monad m => Category (ScanM m :: Type -> Type -> Type)

Defined in Control.Scanl

Methods

id :: forall (a :: k). ScanM m a a

(.) :: forall (b :: k) (c :: k) (a :: k). ScanM m b c -> ScanM m a b -> ScanM m a c

Monad m => Arrow (ScanM m)

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)

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

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

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

Applicative m => Applicative (ScanM m a)

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

Functor m => Functor (ScanM m a)

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

(Monad m, Monoid b) => Monoid (ScanM m a b)

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

(Monad m, Semigroup b) => Semigroup (ScanM m a b)

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, Floating b) => Floating (ScanM m a b)

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, Num b) => Num (ScanM m a b)

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, Fractional b) => Fractional (ScanM m a b)

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

Scanning

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

Apply a strict left Scan to a Traversable container

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

Like scan but monadic

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

Like scan but start scanning from the right

prescan :: Fold a b -> Scan a b

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

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

Upgrade a scan to accept the Scan type

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

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

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

Upgrade a more traditional monadic scan to accept the ScanM type

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

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

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

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

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

(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

(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