Safe Haskell	None
Language	Haskell2010

Control.Scanl

Contents

Scan Types
Scanning
Utilities

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

data Scan a b = Scan (a -> State x b) x
data ScanM m a b = ScanM (a -> StateT x m b) (m x)
scan :: Traversable t => Scan a b -> t a -> t b
scanM :: (Traversable t, Monad m) => ScanM m a b -> t a -> m (t b)
scanr :: Traversable t => Scan a b -> t a -> t b
prescan :: Fold a b -> Scan a b
postscan :: Fold a b -> Scan a b
purely :: (forall x. (a -> State x b) -> x -> r) -> Scan a b -> r
purely_ :: (forall x. (x -> a -> (x, b)) -> x -> r) -> Scan a b -> r
impurely :: (forall x. (a -> StateT x m b) -> m x -> r) -> ScanM m a b -> r
impurely_ :: Monad m => (forall x. (x -> a -> m (x, b)) -> m x -> r) -> ScanM m a b -> r
generalize :: Monad m => Scan a b -> ScanM m a b
simplify :: ScanM Identity a b -> Scan a b
hoists :: (forall x. m x -> n x) -> ScanM m a b -> ScanM n a b
arrM :: Monad m => (b -> m c) -> ScanM m b c
premap :: (a -> b) -> Scan b r -> Scan a r
premapM :: Monad m => (a -> m b) -> ScanM m b r -> ScanM m a r

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