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

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

newtype IterT (m :: Type -> Type) a = IterT {
- runIterT :: m (Either a (IterT m a))
}
type Iter = IterT Identity
iter :: Either a (Iter a) -> Iter a
runIter :: Iter a -> Either a (Iter a)
delay :: forall (f :: Type -> Type) m a. (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 :: forall (m :: Type -> Type) a. Monad m => Iter a -> IterT m a
cutoff :: forall (m :: Type -> Type) a. Monad m => Integer -> IterT m a -> IterT m (Maybe a)
never :: forall (f :: Type -> Type) m a. (Monad f, MonadFree f m) => m a
untilJust :: Monad m => m (Maybe a) -> IterT m a
interleave :: forall (m :: Type -> Type) a. Monad m => [IterT m a] -> IterT m [a]
interleave_ :: forall (m :: Type -> Type) a. 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 :: Type -> Type) (m :: Type -> Type) | 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

newtype IterT (m :: Type -> Type) 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

Instances details

MonadTrans IterT Source #
Instance details Defined in Control.Monad.Trans.Iter Methods lift :: Monad m => m a -> IterT m a #
Monad m => MonadFree Identity (IterT m) Source #
Instance details Defined in Control.Monad.Trans.Iter Methods wrap :: Identity (IterT m a) -> IterT m a Source #
MonadError e m => MonadError e (IterT m) Source #
Instance details Defined in Control.Monad.Trans.Iter Methods throwError :: e -> IterT m a # catchError :: IterT m a -> (e -> IterT m a) -> IterT m a #
MonadReader e m => MonadReader e (IterT m) Source #
Instance details Defined in Control.Monad.Trans.Iter Methods ask :: IterT m e # local :: (e -> e) -> IterT m a -> IterT m a # reader :: (e -> a) -> IterT m a #
MonadState s m => MonadState s (IterT m) Source #
Instance details Defined in Control.Monad.Trans.Iter Methods get :: IterT m s # put :: s -> IterT m () # state :: (s -> (a, s)) -> IterT m a #
MonadWriter w m => MonadWriter w (IterT m) Source #
Instance details Defined in Control.Monad.Trans.Iter Methods writer :: (a, w) -> IterT m a # tell :: w -> IterT m () # listen :: IterT m a -> IterT m (a, w) # pass :: IterT m (a, w -> w) -> IterT m a #
Monad m => MonadFail (IterT m) Source #
Instance details Defined in Control.Monad.Trans.Iter Methods fail :: String -> IterT m a #
MonadFix m => MonadFix (IterT m) Source #
Instance details Defined in Control.Monad.Trans.Iter Methods mfix :: (a -> IterT m a) -> IterT m a #
MonadIO m => MonadIO (IterT m) Source #
Instance details Defined in Control.Monad.Trans.Iter Methods liftIO :: IO a -> IterT m a #
Foldable m => Foldable (IterT m) Source #
Instance details Defined in Control.Monad.Trans.Iter Methods fold :: Monoid m0 => IterT m m0 -> m0 # foldMap :: Monoid m0 => (a -> m0) -> IterT m a -> m0 # foldMap' :: Monoid m0 => (a -> m0) -> IterT m a -> m0 # foldr :: (a -> b -> b) -> b -> IterT m a -> b # foldr' :: (a -> b -> b) -> b -> IterT m a -> b # foldl :: (b -> a -> b) -> b -> IterT m a -> b # foldl' :: (b -> a -> b) -> b -> IterT m a -> b # foldr1 :: (a -> a -> a) -> IterT m a -> a # foldl1 :: (a -> a -> a) -> IterT m a -> a # toList :: IterT m a -> [a] # null :: IterT m a -> Bool # length :: IterT m a -> Int # elem :: Eq a => a -> IterT m a -> Bool # maximum :: Ord a => IterT m a -> a # minimum :: Ord a => IterT m a -> a # sum :: Num a => IterT m a -> a # product :: Num a => IterT m a -> a #
Foldable1 m => Foldable1 (IterT m) Source #
Instance details Defined in Control.Monad.Trans.Iter Methods fold1 :: Semigroup m0 => IterT m m0 -> m0 # foldMap1 :: Semigroup m0 => (a -> m0) -> IterT m a -> m0 # foldMap1' :: Semigroup m0 => (a -> m0) -> IterT m a -> m0 # toNonEmpty :: IterT m a -> NonEmpty a # maximum :: Ord a => IterT m a -> a # minimum :: Ord a => IterT m a -> a # head :: IterT m a -> a # last :: IterT m a -> a # foldrMap1 :: (a -> b) -> (a -> b -> b) -> IterT m a -> b # foldlMap1' :: (a -> b) -> (b -> a -> b) -> IterT m a -> b # foldlMap1 :: (a -> b) -> (b -> a -> b) -> IterT m a -> b # foldrMap1' :: (a -> b) -> (a -> b -> b) -> IterT m a -> b #
Eq1 m => Eq1 (IterT m) Source #
Instance details Defined in Control.Monad.Trans.Iter Methods liftEq :: (a -> b -> Bool) -> IterT m a -> IterT m b -> Bool #
Ord1 m => Ord1 (IterT m) Source #
Instance details Defined in Control.Monad.Trans.Iter Methods liftCompare :: (a -> b -> Ordering) -> IterT m a -> IterT m b -> Ordering #
Read1 m => Read1 (IterT m) Source #
Instance details Defined in Control.Monad.Trans.Iter Methods liftReadsPrec :: (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (IterT m a) # liftReadList :: (Int -> ReadS a) -> ReadS [a] -> ReadS [IterT m a] # liftReadPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec (IterT m a) # liftReadListPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec [IterT m a] #
Show1 m => Show1 (IterT m) Source #
Instance details Defined in Control.Monad.Trans.Iter Methods liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> IterT m a -> ShowS # liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [IterT m a] -> ShowS #
(Monad m, Traversable m) => Traversable (IterT m) Source #
Instance details Defined in Control.Monad.Trans.Iter Methods traverse :: Applicative f => (a -> f b) -> IterT m a -> f (IterT m b) # sequenceA :: Applicative f => IterT m (f a) -> f (IterT m a) # mapM :: Monad m0 => (a -> m0 b) -> IterT m a -> m0 (IterT m b) # sequence :: Monad m0 => IterT m (m0 a) -> m0 (IterT m a) #
Monad m => Alternative (IterT m) Source #
Instance details Defined in Control.Monad.Trans.Iter Methods empty :: IterT m a # (<\|>) :: IterT m a -> IterT m a -> IterT m a # some :: IterT m a -> IterT m [a] # many :: IterT m a -> IterT m [a] #
Monad m => Applicative (IterT m) Source #
Instance details Defined in Control.Monad.Trans.Iter Methods pure :: a -> IterT m a # (<>) :: IterT m (a -> b) -> IterT m a -> IterT m b # liftA2 :: (a -> b -> c) -> IterT m a -> IterT m b -> IterT m c # (>) :: IterT m a -> IterT m b -> IterT m b # (<*) :: IterT m a -> IterT m b -> IterT m a #
Monad m => Functor (IterT m) Source #
Instance details Defined in Control.Monad.Trans.Iter Methods fmap :: (a -> b) -> IterT m a -> IterT m b # (<$) :: a -> IterT m b -> IterT m a #
Monad m => Monad (IterT m) Source #
Instance details Defined in Control.Monad.Trans.Iter Methods (>>=) :: IterT m a -> (a -> IterT m b) -> IterT m b # (>>) :: IterT m a -> IterT m b -> IterT m b # return :: a -> IterT m a #
Monad m => MonadPlus (IterT m) Source #	Capretta's `race` combinator. Satisfies left catch.
Instance details Defined in Control.Monad.Trans.Iter Methods mzero :: IterT m a # mplus :: IterT m a -> IterT m a -> IterT m a #
MonadCatch m => MonadCatch (IterT m) Source #
Instance details Defined in Control.Monad.Trans.Iter Methods catch :: (HasCallStack, Exception e) => IterT m a -> (e -> IterT m a) -> IterT m a #
MonadThrow m => MonadThrow (IterT m) Source #
Instance details Defined in Control.Monad.Trans.Iter Methods throwM :: (HasCallStack, Exception e) => e -> IterT m a #
MonadCont m => MonadCont (IterT m) Source #
Instance details Defined in Control.Monad.Trans.Iter Methods callCC :: ((a -> IterT m b) -> IterT m a) -> IterT m a #
Monad m => Apply (IterT m) Source #
Instance details Defined in Control.Monad.Trans.Iter Methods (<.>) :: IterT m (a -> b) -> IterT m a -> IterT m b # (.>) :: IterT m a -> IterT m b -> IterT m b # (<.) :: IterT m a -> IterT m b -> IterT m a # liftF2 :: (a -> b -> c) -> IterT m a -> IterT m b -> IterT m c #
Monad m => Bind (IterT m) Source #
Instance details Defined in Control.Monad.Trans.Iter Methods (>>-) :: IterT m a -> (a -> IterT m b) -> IterT m b # join :: IterT m (IterT m a) -> IterT m a #
(Monad m, Traversable1 m) => Traversable1 (IterT m) Source #
Instance details Defined in Control.Monad.Trans.Iter Methods traverse1 :: Apply f => (a -> f b) -> IterT m a -> f (IterT m b) # sequence1 :: Apply f => IterT m (f b) -> f (IterT m b) #
(Typeable m, Data (m (Either a (IterT m a))), Data a) => Data (IterT m a) Source #
Instance details 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) # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (IterT m a) # toConstr :: IterT m a -> Constr # dataTypeOf :: IterT m a -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (IterT m a)) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (IterT m a)) # gmapT :: (forall b. Data b => b -> b) -> IterT m a -> IterT m a # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> IterT m a -> r # gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> IterT m a -> r # gmapQ :: (forall d. Data d => d -> u) -> IterT m a -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> IterT m a -> u # gmapM :: Monad m0 => (forall d. Data d => d -> m0 d) -> IterT m a -> m0 (IterT m a) # gmapMp :: MonadPlus m0 => (forall d. Data d => d -> m0 d) -> IterT m a -> m0 (IterT m a) # gmapMo :: MonadPlus m0 => (forall d. Data d => d -> m0 d) -> IterT m a -> m0 (IterT m a) #
(Monad m, Semigroup a, Monoid a) => Monoid (IterT m a) Source #
Instance details Defined in Control.Monad.Trans.Iter Methods mempty :: IterT m a # mappend :: IterT m a -> IterT m a -> IterT m a # mconcat :: [IterT m a] -> IterT m a #
(Monad m, Semigroup a) => Semigroup (IterT m a) Source #
Instance details Defined in Control.Monad.Trans.Iter Methods (<>) :: IterT m a -> IterT m a -> IterT m a # sconcat :: NonEmpty (IterT m a) -> IterT m a # stimes :: Integral b => b -> IterT m a -> IterT m a #
(Read1 m, Read a) => Read (IterT m a) Source #
Instance details Defined in Control.Monad.Trans.Iter Methods readsPrec :: Int -> ReadS (IterT m a) # readList :: ReadS [IterT m a] # readPrec :: ReadPrec (IterT m a) # readListPrec :: ReadPrec [IterT m a] #
(Show1 m, Show a) => Show (IterT m a) Source #
Instance details Defined in Control.Monad.Trans.Iter Methods showsPrec :: Int -> IterT m a -> ShowS # show :: IterT m a -> String # showList :: [IterT m a] -> ShowS #
(Eq1 m, Eq a) => Eq (IterT m a) Source #
Instance details Defined in Control.Monad.Trans.Iter Methods (==) :: IterT m a -> IterT m a -> Bool # (/=) :: IterT m a -> IterT m a -> Bool #
(Ord1 m, Ord a) => Ord (IterT m a) Source #
Instance details Defined in Control.Monad.Trans.Iter Methods compare :: IterT m a -> IterT m a -> Ordering # (<) :: IterT m a -> IterT m a -> Bool # (<=) :: IterT m a -> IterT m a -> Bool # (>) :: IterT m a -> IterT m a -> Bool # (>=) :: IterT m a -> IterT m a -> Bool # max :: IterT m a -> IterT m a -> IterT m a # min :: IterT m a -> IterT m a -> IterT m a #

Capretta's iterative monad

type Iter = IterT Identity Source #

Plain iterative computations.

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 :: forall (f :: Type -> Type) m a. (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 #

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

liftIter :: forall (m :: Type -> Type) a. Monad m => Iter a -> IterT m a Source #

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

cutoff :: forall (m :: Type -> Type) a. 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 :: forall (f :: Type -> Type) m a. (Monad f, MonadFree f m) => m a Source #

A computation that never terminates

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 :: forall (m :: Type -> Type) a. 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_ :: forall (m :: Type -> Type) a. 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 a Source #

retract is the left inverse of lift

retract . lift = id

fold :: Monad m => (m a -> a) -> IterT m a -> a Source #

Tear down a Free Monad using iteration.

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 :: Type -> Type) (m :: Type -> Type) | 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 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.

Minimal complete definition

Nothing

Methods

wrap :: f (m a) -> m a Source #

Add a layer.

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

default wrap :: forall (t :: (Type -> Type) -> Type -> Type) (n :: Type -> Type) a. (m ~ t n, MonadTrans t, MonadFree f n, Functor f) => f (m a) -> m a Source #

Instances

Instances details

Monad m => MonadFree Identity (IterT m) Source #
Instance details Defined in Control.Monad.Trans.Iter Methods wrap :: Identity (IterT m a) -> IterT m a Source #
Functor f => MonadFree f (Free f) Source #
Instance details Defined in Control.Monad.Free Methods wrap :: f (Free f a) -> Free f a Source #
Applicative f => MonadFree f (Free f) Source #
Instance details Defined in Control.Monad.Free.Ap Methods wrap :: f (Free f a) -> Free f a Source #
Functor f => MonadFree f (F f) Source #
Instance details Defined in Control.Monad.Free.Church Methods wrap :: f (F f a) -> F f a Source #
(Functor f, MonadFree f m) => MonadFree f (MaybeT m) Source #
Instance details Defined in Control.Monad.Free.Class Methods wrap :: f (MaybeT m a) -> MaybeT m a Source #
(Functor f, Monad m) => MonadFree f (FreeT f m) Source #
Instance details Defined in Control.Monad.Trans.Free Methods wrap :: f (FreeT f m a) -> FreeT f m a Source #
(Applicative f, Monad m) => MonadFree f (FreeT f m) Source #
Instance details Defined in Control.Monad.Trans.Free.Ap Methods wrap :: f (FreeT f m a) -> FreeT f m a Source #
MonadFree f (FT f m) Source #
Instance details Defined in Control.Monad.Trans.Free.Church Methods wrap :: f (FT f m a) -> FT f m a Source #
(Functor f, MonadFree f m) => MonadFree f (ExceptT e m) Source #
Instance details Defined in Control.Monad.Free.Class Methods wrap :: f (ExceptT e m a) -> ExceptT e m a Source #
(Functor f, MonadFree f m) => MonadFree f (IdentityT m) Source #
Instance details Defined in Control.Monad.Free.Class Methods wrap :: f (IdentityT m a) -> IdentityT m a Source #
(Functor f, MonadFree f m) => MonadFree f (ReaderT e m) Source #
Instance details Defined in Control.Monad.Free.Class Methods wrap :: f (ReaderT e m a) -> ReaderT e m a Source #
(Functor f, MonadFree f m) => MonadFree f (StateT s m) Source #
Instance details Defined in Control.Monad.Free.Class Methods wrap :: f (StateT s m a) -> StateT s m a Source #
(Functor f, MonadFree f m) => MonadFree f (StateT s m) Source #
Instance details Defined in Control.Monad.Free.Class Methods wrap :: f (StateT s m a) -> StateT s m a Source #
(Functor f, MonadFree f m, Monoid w) => MonadFree f (WriterT w m) Source #
Instance details Defined in Control.Monad.Free.Class Methods wrap :: f (WriterT w m a) -> WriterT w m a Source #
(Functor f, MonadFree f m, Monoid w) => MonadFree f (WriterT w m) Source #
Instance details Defined in Control.Monad.Free.Class Methods wrap :: f (WriterT w m a) -> WriterT w m a Source #
(Functor f, MonadFree f m) => MonadFree f (ContT r m) Source #
Instance details Defined in Control.Monad.Free.Class Methods wrap :: f (ContT r m a) -> ContT r m a Source #
(Functor f, MonadFree f m, Monoid w) => MonadFree f (RWST r w s m) Source #
Instance details Defined in Control.Monad.Free.Class Methods wrap :: f (RWST r w s m a) -> RWST r w s m a Source #
(Functor f, MonadFree f m, Monoid w) => MonadFree f (RWST r w s m) Source #
Instance details Defined in Control.Monad.Free.Class Methods wrap :: f (RWST r w s m a) -> RWST r w s m a Source #

Documentation

The iterative monad transformer

Instances

Capretta's iterative monad

Combinators

Consuming iterative monads

IterT ~ FreeT Identity

Instances

Examples