Portability	MPTCs, fundeps
Stability	provisional
Maintainer	Edward Kmett <ekmett@gmail.com>
Safe Haskell	None

Control.Monad.Trans.Iter

Contents

The iterative monad transformer
Capretta's iterative monad
Combinators
Consuming iterative monads
IterT ~ FreeT Identity
Examples

Description

Based on Capretta's Iterative Monad Transformer

Unlike Free, this is a true monad transformer.

Synopsis

Documentation

Functions in Haskell are meant to be pure. For example, if an expression has type Int, there should exist a value of the type such that the expression can be replaced by that value in any context without changing the meaning of the program.

Some computations may perform side effects (unsafePerformIO), throw an exception (using error); or not terminate (let infinity = 1 + infinity in infinity).

While the IO monad encapsulates side-effects, and the Either monad encapsulates errors, the Iter monad encapsulates non-termination. The IterT transformer generalizes non-termination to any monadic computation.

The iterative monad transformer

newtype IterT m a Source

The monad supporting iteration based over a base monad m.

 IterT ~ FreeT Identity

Constructors

IterT
Fields runIterT :: m (Either a (IterT m a))

Instances

MonadTrans IterT
MonadError e m => MonadError e (IterT m)
MonadReader e m => MonadReader e (IterT m)
MonadState s m => MonadState s (IterT m)
MonadWriter w m => MonadWriter w (IterT m)
Monad m => MonadFree Identity (IterT m)
Monad m => Monad (IterT m)
Monad m => Functor (IterT m)
Typeable1 m => Typeable1 (IterT m)
MonadFix m => MonadFix (IterT m)
MonadPlus m => MonadPlus (IterT m)
Monad m => Applicative (IterT m)
Foldable m => Foldable (IterT m)
(Monad m, Traversable m) => Traversable (IterT m)
MonadPlus m => Alternative (IterT m)
MonadIO m => MonadIO (IterT m)
MonadCont m => MonadCont (IterT m)
(Functor m, Eq1 m) => Eq1 (IterT m)
(Functor m, Ord1 m) => Ord1 (IterT m)
(Functor m, Show1 m) => Show1 (IterT m)
(Functor m, Read1 m) => Read1 (IterT m)
(Monad m, Traversable1 m) => Traversable1 (IterT m)
Foldable1 m => Foldable1 (IterT m)
Monad m => Apply (IterT m)
Monad m => Bind (IterT m)
Eq (m (Either a (IterT m a))) => Eq (IterT m a)
(Typeable1 m, Typeable a, Data (m (Either a (IterT m a))), Data a) => Data (IterT m a)
Ord (m (Either a (IterT m a))) => Ord (IterT m a)
Read (m (Either a (IterT m a))) => Read (IterT m a)
Show (m (Either a (IterT m a))) => Show (IterT m a)
(Monad m, Monoid a) => Monoid (IterT m a)

Capretta's iterative monad

type Iter = IterT Identity Source

Plain iterative computations.

iter :: Either a (Iter a) -> Iter aSource

Builds an iterative computation from one first step.

runIter . iter == id

runIter :: Iter a -> Either a (Iter a)Source

Executes the first step of an iterative computation

iter . runIter == id

Combinators

delay :: (Monad f, MonadFree f m) => m a -> m aSource

Adds an extra layer to a free monad value.

In particular, for the iterative monad Iter, this makes the computation require one more step, without changing its final result.

runIter (delay ma) == Right ma

hoistIterT :: Monad n => (forall a. m a -> n a) -> IterT m b -> IterT n bSource

Lift a monad homomorphism from m to n into a Monad homomorphism from IterT m to IterT n.

liftIter :: Monad m => Iter a -> IterT m aSource

Lifts a plain, non-terminating computation into a richer environment. liftIter is a Monad homomorphism.

cutoff :: Monad m => Integer -> IterT m a -> IterT m (Maybe a)Source

Cuts off an iterative computation after a given number of steps. If the number of steps is 0 or less, no computation nor monadic effects will take place.

The step where the final value is produced also counts towards the limit.

Some examples (n ≥ 0):

 cutoff 0     _        ≡ return Nothing
 cutoff (n+1) . return ≡ return . Just
 cutoff (n+1) . lift   ≡ lift . liftM Just
 cutoff (n+1) . delay  ≡ delay . cutoff n
 cutoff n     never    ≡ iterate delay (return Nothing) !! n

Calling retract . cutoff n is always terminating, provided each of the steps in the iteration is terminating.

never :: (Monad f, MonadFree f m) => m aSource

A computation that never terminates

interleave :: Monad m => [IterT m a] -> IterT m [a]Source

Interleaves the steps of a finite list of iterative computations, and collects their results.

The resulting computation has as many steps as the longest computation in the list.

interleave_ :: Monad m => [IterT m a] -> IterT m ()Source

Interleaves the steps of a finite list of computations, and discards their results.

The resulting computation has as many steps as the longest computation in the list.

Equivalent to void . interleave.

Consuming iterative monads

retract :: Monad m => IterT m a -> m aSource

retract is the left inverse of lift

 retract . lift = id

fold :: Monad m => (m a -> a) -> IterT m a -> aSource

Tear down a Free Monad using iteration.

foldM :: (Monad m, Monad n) => (m (n a) -> n a) -> IterT m a -> n aSource

Like fold with monadic result.

IterT ~ FreeT Identity

class Monad m => MonadFree f m | m -> f whereSource

Monads provide substitution (fmap) and renormalization (join):

m >>= f = join (fmap f m)

A free Monad is one that does no work during the normalization step beyond simply grafting the two monadic values together.

[] is not a free Monad (in this sense) because join [[a]] smashes the lists flat.

On the other hand, consider:

 data Tree a = Bin (Tree a) (Tree a) | Tip a

 instance Monad Tree where
   return = Tip
   Tip a >>= f = f a
   Bin l r >>= f = Bin (l >>= f) (r >>= f)

This Monad is the free Monad of Pair:

 data Pair a = Pair a a

And we could make an instance of MonadFree for it directly:

 instance MonadFree Pair Tree where
    wrap (Pair l r) = Bin l r

Or we could choose to program with Free Pair instead of Tree and thereby avoid having to define our own Monad instance.

Moreover, Control.Monad.Free.Church provides a MonadFree instance that can improve the asymptotic complexity of code that constructs free monads by effectively reassociating the use of (>>=). You may also want to take a look at the kan-extensions package (http://hackage.haskell.org/package/kan-extensions).

See Free for a more formal definition of the free Monad for a Functor.

Methods

wrap :: f (m a) -> m aSource

Add a layer.

 wrap (fmap f x) ≡ wrap (fmap return x) >>= f

Instances

(Functor f, MonadFree f m) => MonadFree f (ListT m)
(Functor f, MonadFree f m) => MonadFree f (IdentityT m)
(Functor f, MonadFree f m) => MonadFree f (MaybeT m)
Functor f => MonadFree f (Free f)
Functor f => MonadFree f (F f)
Monad m => MonadFree Identity (IterT m)
(Functor f, MonadFree f m, Error e) => MonadFree f (ErrorT e m)
(Functor f, MonadFree f m, Monoid w) => MonadFree f (WriterT w m)
(Functor f, MonadFree f m, Monoid w) => MonadFree f (WriterT w m)
(Functor f, MonadFree f m) => MonadFree f (ContT r m)
(Functor f, MonadFree f m) => MonadFree f (StateT s m)
(Functor f, MonadFree f m) => MonadFree f (StateT s m)
(Functor f, MonadFree f m) => MonadFree f (ReaderT e m)
(Functor f, Monad m) => MonadFree f (FreeT f m)
Functor f => MonadFree f (FT f m)
(Functor f, MonadFree f m, Monoid w) => MonadFree f (RWST r w s m)
(Functor f, MonadFree f m, Monoid w) => MonadFree f (RWST r w s m)

Examples

Mandelbrot