| Copyright | (C) 2013 Edward Kmett |
|---|---|
| License | BSD-style (see the file LICENSE) |
| Maintainer | Edward Kmett <ekmett@gmail.com> |
| Stability | provisional |
| Portability | MPTCs, fundeps |
| Safe Haskell | Safe |
| Language | Haskell2010 |
Control.Monad.Trans.Iter
Description
Based on Capretta's Iterative Monad Transformer
Unlike
Free
, this is a true monad transformer.
Synopsis
- newtype IterT m a = IterT { }
- type Iter = IterT Identity
- iter :: Either a ( Iter a) -> Iter a
- runIter :: Iter a -> Either a ( Iter a)
- delay :: ( Monad f, MonadFree f m) => m a -> m a
- hoistIterT :: Monad n => ( forall a. m a -> n a) -> IterT m b -> IterT n b
- liftIter :: Monad m => Iter a -> IterT m a
- cutoff :: Monad m => Integer -> IterT m a -> IterT m ( Maybe a)
- never :: ( Monad f, MonadFree f m) => m a
- untilJust :: Monad m => m ( Maybe a) -> IterT m a
- interleave :: Monad m => [ IterT m a] -> IterT m [a]
- interleave_ :: Monad m => [ IterT m a] -> IterT m ()
- retract :: Monad m => IterT m a -> m a
- fold :: Monad m => (m a -> a) -> IterT m a -> a
- foldM :: ( Monad m, Monad n) => (m (n a) -> n a) -> IterT m a -> n a
-
class
Monad
m =>
MonadFree
f m | m -> f
where
- wrap :: f (m a) -> m a
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.
Computations in
IterT
(or
Iter
) can be composed in two ways:
-
Sequential:
Using the
Monadinstance, the result of a computation can be fed into the next. -
Parallel:
Using the
MonadPlusinstance, several computations can be executed concurrently, and the first to finish will prevail. See also the cabbage example .
The iterative monad transformer
Instances
| MonadTrans IterT Source # | |
| MonadWriter w m => MonadWriter w ( IterT m) Source # | |
| MonadState s m => MonadState s ( IterT m) Source # | |
| MonadReader e m => MonadReader e ( IterT m) Source # | |
| MonadError e m => MonadError e ( IterT m) Source # | |
|
Defined in Control.Monad.Trans.Iter Methods throwError :: e -> IterT m a Source # catchError :: IterT m a -> (e -> IterT m a) -> IterT m a Source # |
|
| Monad m => MonadFree Identity ( IterT m) Source # | |
| Monad m => Monad ( IterT m) Source # | |
| Monad m => Functor ( IterT m) Source # | |
| MonadFix m => MonadFix ( IterT m) Source # | |
| Monad m => MonadFail ( IterT m) Source # | |
| Monad m => Applicative ( IterT m) Source # | |
|
Defined in Control.Monad.Trans.Iter |
|
| Foldable m => Foldable ( IterT m) Source # | |
|
Defined in Control.Monad.Trans.Iter Methods fold :: Monoid m0 => IterT m m0 -> m0 Source # foldMap :: Monoid m0 => (a -> m0) -> IterT m a -> m0 Source # foldMap' :: Monoid m0 => (a -> m0) -> IterT m a -> m0 Source # foldr :: (a -> b -> b) -> b -> IterT m a -> b Source # foldr' :: (a -> b -> b) -> b -> IterT m a -> b Source # foldl :: (b -> a -> b) -> b -> IterT m a -> b Source # foldl' :: (b -> a -> b) -> b -> IterT m a -> b Source # foldr1 :: (a -> a -> a) -> IterT m a -> a Source # foldl1 :: (a -> a -> a) -> IterT m a -> a Source # toList :: IterT m a -> [a] Source # null :: IterT m a -> Bool Source # length :: IterT m a -> Int Source # elem :: Eq a => a -> IterT m a -> Bool Source # maximum :: Ord a => IterT m a -> a Source # minimum :: Ord a => IterT m a -> a Source # |
|
| ( Monad m, Traversable m) => Traversable ( IterT m) Source # | |
|
Defined in Control.Monad.Trans.Iter |
|
| Eq1 m => Eq1 ( IterT m) Source # | |
| Ord1 m => Ord1 ( IterT m) Source # | |
|
Defined in Control.Monad.Trans.Iter |
|
| Read1 m => Read1 ( IterT m) Source # | |
|
Defined in Control.Monad.Trans.Iter Methods liftReadsPrec :: ( Int -> ReadS a) -> ReadS [a] -> Int -> ReadS ( IterT m a) Source # liftReadList :: ( Int -> ReadS a) -> ReadS [a] -> ReadS [ IterT m a] Source # liftReadPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec ( IterT m a) Source # liftReadListPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec [ IterT m a] Source # |
|
| Show1 m => Show1 ( IterT m) Source # | |
| MonadIO m => MonadIO ( IterT m) Source # | |
| Monad m => Alternative ( IterT m) Source # | |
| Monad m => MonadPlus ( IterT m) Source # |
Capretta's
|
| MonadThrow m => MonadThrow ( IterT m) Source # | |
| MonadCatch m => MonadCatch ( IterT m) Source # | |
| MonadCont m => MonadCont ( IterT m) Source # | |
| ( Monad m, Traversable1 m) => Traversable1 ( IterT m) Source # | |
| Monad m => Apply ( IterT m) Source # | |
| Monad m => Bind ( IterT m) Source # | |
| Foldable1 m => Foldable1 ( IterT m) Source # | |
| ( Eq1 m, Eq a) => Eq ( IterT m a) Source # | |
| ( Typeable m, Typeable a, Data (m ( Either a ( IterT m a))), Data a) => Data ( IterT m a) Source # | |
|
Defined in Control.Monad.Trans.Iter Methods gfoldl :: ( forall d b. Data d => c (d -> b) -> d -> c b) -> ( forall g. g -> c g) -> IterT m a -> c ( IterT m a) Source # gunfold :: ( forall b r. Data b => c (b -> r) -> c r) -> ( forall r. r -> c r) -> Constr -> c ( IterT m a) Source # toConstr :: IterT m a -> Constr Source # dataTypeOf :: IterT m a -> DataType Source # dataCast1 :: Typeable t => ( forall d. Data d => c (t d)) -> Maybe (c ( IterT m a)) Source # dataCast2 :: Typeable t => ( forall d e. ( Data d, Data e) => c (t d e)) -> Maybe (c ( IterT m a)) Source # gmapT :: ( forall b. Data b => b -> b) -> IterT m a -> IterT m a Source # gmapQl :: (r -> r' -> r) -> r -> ( forall d. Data d => d -> r') -> IterT m a -> r Source # gmapQr :: forall r r'. (r' -> r -> r) -> r -> ( forall d. Data d => d -> r') -> IterT m a -> r Source # gmapQ :: ( forall d. Data d => d -> u) -> IterT m a -> [u] Source # gmapQi :: Int -> ( forall d. Data d => d -> u) -> IterT m a -> u Source # gmapM :: Monad m0 => ( forall d. Data d => d -> m0 d) -> IterT m a -> m0 ( IterT m a) Source # gmapMp :: MonadPlus m0 => ( forall d. Data d => d -> m0 d) -> IterT m a -> m0 ( IterT m a) Source # gmapMo :: MonadPlus m0 => ( forall d. Data d => d -> m0 d) -> IterT m a -> m0 ( IterT m a) Source # |
|
| ( Ord1 m, Ord a) => Ord ( IterT m a) Source # | |
|
Defined in Control.Monad.Trans.Iter Methods compare :: IterT m a -> IterT m a -> Ordering Source # (<) :: IterT m a -> IterT m a -> Bool Source # (<=) :: IterT m a -> IterT m a -> Bool Source # (>) :: IterT m a -> IterT m a -> Bool Source # (>=) :: IterT m a -> IterT m a -> Bool Source # |
|
| ( Read1 m, Read a) => Read ( IterT m a) Source # | |
| ( Show1 m, Show a) => Show ( IterT m a) Source # | |
| ( Monad m, Semigroup a) => Semigroup ( IterT m a) Source # | |
| ( Monad m, Semigroup a, Monoid a) => Monoid ( IterT m a) Source # | |
Capretta's iterative monad
iter :: Either a ( Iter a) -> Iter a Source #
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 a Source #
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
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
):
cutoff0 _ ≡returnNothingcutoff(n+1).return≡return.Justcutoff(n+1).lift≡lift.liftMJustcutoff(n+1).delay≡delay.cutoffncutoffnnever≡iteratedelay(returnNothing)!!n
Calling
is always terminating, provided each of the
steps in the iteration is terminating.
retract
.
cutoff
n
untilJust :: Monad m => m ( Maybe a) -> IterT m a Source #
Repeatedly run a computation until it produces a
Just
value.
This can be useful when paired with a monad that has side effects.
For example, we may have
genId :: IO (Maybe Id)
that uses a random
number generator to allocate ids, but fails if it finds a collision.
We can repeatedly run this with
retract(untilJustgenId) :: IO Id
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
foldM :: ( Monad m, Monad n) => (m (n a) -> n a) -> IterT m a -> n a Source #
Like
fold
with monadic result.
IterT ~ FreeT Identity
class Monad m => MonadFree f m | m -> f where Source #
Monads provide substitution (
fmap
) and renormalization (
join
):
m>>=f =join(fmapf 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
smashes the lists flat.
join
[[a]]
On the other hand, consider:
data Tree a = Bin (Tree a) (Tree a) | Tip a
instanceMonadTree wherereturn= 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:
instanceMonadFreePair Tree wherewrap(Pair l r) = Bin l r
Or we could choose to program with
instead of
Free
Pair
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
.
Minimal complete definition
Nothing