Control.Monad.Trans.Iter

The monad supporting iteration based over a base monad m.

IterT ~ FreeT Identity

Plain iterative computations.

Builds an iterative computation from one first step.

prop> runIter . iter == id

Executes the first step of an iterative computation

prop> iter . runIter == id

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.

prop> runIter (delay ma) == Right ma

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

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

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.

A computation that never terminates

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

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.

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.

retract is the left inverse of lift

retract . lift = id

Tear down a Free Monad using iteration.

Like fold with monadic result.

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.