| 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
Contents
Description
Based on Capretta's Iterative Monad Transformer
Unlike Free, this is a true monad transformer.
- 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
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
hoistIterT :: Monad n => (forall a. m a -> n a) -> IterT m b -> IterT n b Source
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 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 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 Free PairTree
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
Instances