% Monads with Non-Deterministically Updateable State
% Sebastian Fischer (sebf@informatik.uni-kiel.de)
We define type classes and instances for monads that
non-deterministically update state.
>
>
> module Control.Monad.Update (
>
> MonadUpdate(..), Update(..),
>
> ) where
>
> import Control.Monad.State
>
> class MonadPlus m => MonadUpdate s m
> where
> update :: (forall m' . MonadPlus m' => s -> m' s) -> m ()
A monad that supports non-deterministic state updates is an instance
of the class `MonadUpdate` that defines an operation to incorporate a
monadic update-action into monadic computations.
> instance MonadPlus m => MonadUpdate s (StateT s m)
> where
> update upd = get >>= upd >>= put
An instance of `MonadPlus` that threads a state can update that state
non-deterministically.
> class (MonadPlus m, MonadPlus m') => Update s m m'
> where
> updateState :: m a -> StateT s m' a
We also define an interface for monads that perform associated updates
in a state that is threaded through a (possibly, but not necessarily
different) monad.
We use the state monad transformer `StateT` to thread the constraint
store through the monad that returns the results.
> instance MonadPlus m => Update s (StateT s m) m
> where
> updateState = id
Again, a state threading monad gives rise to a natural instance, where
results are returned in the base monad.
State monads are a natural choice for a monad that updates state, but
they have a drawback: monadic values are functions that are reexecuted
for each shared occurrence of a monadic sub computation.