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
Monad
instance, the result of a computation can be fed into the next. -
Parallel:
Using the
MonadPlus
instance, 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
):
cutoff
0 _ ≡return
Nothing
cutoff
(n+1).
return
≡return
.
Just
cutoff
(n+1).
lift
≡lift
.
liftM
Just
cutoff
(n+1).
delay
≡delay
.cutoff
ncutoff
nnever
≡iterate
delay
(return
Nothing
)!!
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
(untilJust
genId) :: 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
(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
smashes the lists flat.
join
[[a]]
On the other hand, consider:
data Tree a = Bin (Tree a) (Tree a) | Tip a
instanceMonad
Tree 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:
instanceMonadFree
Pair 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