Monads and effects

Individual monads capture specific computational effects, e.g.:

• optional results
• error handling
• alternative choice (non-determinism)
• state
• I/O

What if we need to combine effects of several monads together?

An example: state and IO

• Define a monad combining state and IO
• E.g. for the shallow embedding of the Turtle DSEL

forward :: Double -> Turtle ()
forward dist = Turtle $ do
  s <- get                 -- get current state
  ...
  lift $ drawInWindow ...  -- perform I/O 
  put s { ... }            -- update state 

Basic API

newtype StateIO s a -- abstract

instance Monad (StateIO s)
-- also Functor, Applicative
-- accessing state 
get :: StateIO s s
put :: s -> StateIO s ()
-- lifting an I/O operation
lift :: IO a -> StateIO s a
-- run from some initial state
runStateIO :: StateIO s a -> s -> IO (s,a)

Implementation

Recall

State s a $\simeq$ s -> (s, a)

Hence

StateIO s a $\simeq$ s -> IO (s, a)

StateIO s a is a function that:

• take the starting state
• returns an IO action that gives the final state and result

Note that both IO and result may depend on the state.

Implementation (cont.)

newtype StateIO s a
   = StateIO { runStateIO :: s -> IO (s, a) }

The Monad instance is straight-forward:

instance Monad (StateIO s) where
  return x = StateIO (\s -> return (s, x))
  m >>= k  = StateIO (\s -> do
         (s',x) <- runStateIO m s
         runStateIO (k x) s')

Also instances for Functor and Applicative (omitted).

Implementation (cont.)

State operations

get :: StateIO s s
get = StateIO (\s -> return (s,s))

put :: s -> StateIO s ()
put s = StateIO (\_ -> return (s,()))

Lifting IO actions

lift :: IO a -> StateIO s a
lift m = StateIO (\s -> do x<-m; return (s,x))

Generalization: Monad Transformers

A monad transformer takes an underlying monad and gives a new monad with some “extra” effect on-top of the original ones.

Monads and Transformers

Stacking transformers

MaybeT IO a

combines optional results with input/output.

StateT Int IO a

combines state with input/output (same as StateIO Int)

StateT Int Maybe a

combines state with optional results

MaybeT (State Int) a

combines optional results with state

NB: the stacking order matters!

The Identity monad

newtype Identity a
      = Identity {runIdentity :: a}

instance Monad Identity where
    return = Identity
    Identity x >>= k
            = Identity (runIdentity $ k x)

• Identity a is isomorphic to a
• No extra computational effects
• Behaves as a “neutral element” for transformers

Base monads as transformers

The basic monads can be seen as transformers stacked on to the identity monad.

Examples:

Maybe a

is equivalent to MaybeT Identity a

State s a

is equivalent to StateT s Identity a

MaybeT

Maybe transformer

newtype MaybeT m a 
      = MaybeT { runMaybeT :: m (Maybe a) }

• MaybeT m adds optional failure to some monad m
• If m is a monad then MaybeT m is also a monad
• Running an MaybeT m computation gives back an m computation producing an optional result

runMaybeT :: MaybeT m a -> m (Maybe a)

Example: account validation (1)

newAccount :: IO (Maybe (String,String))
newAccount = do
  uid <- getLine
  if validUser uid then do
    pwd <- getLine
    if validPassword s 
        then return (Just (uid, pwd))
        else return Nothing
    else return Nothing

validUser :: String -> Bool
...
validPassword :: String -> Bool
...

Account validation (2)

Using MaybeT to combine optional results with IO.

newAccount :: MaybeT IO (String,String)
newAccount = do
  uid <- lift getLine
  guard (validUser uid) -- from MonadPlus 
  pwd <- lift getLine
  guard (validPassword pwd)
  return (uid,pwd)

NB: use lift to run an action from the underlying monad (IO).

MaybeT Monad instance

MaybeT m is a monad whenever m is a monad.

instance Monad m => Monad (MaybeT m) where
   return  = MaybeT . return . Just
   p >>= k = MaybeT $
             do mv <- runMaybeT p
                case mv of
                  Nothing -> return Nothing
                  Just v  -> runMaybeT (k v)

Apart from wrapping and unwrapping the underlying monad, the operations behave the same as in the Maybe instance.

MaybeT MonadPlus instance

MaybeT m is a monad with a plus whenever m is a monad.

instance Monad m => MonadPlus (MaybeT m) where
   mzero = MaybeT (return Nothing)
   mplus p q = MaybeT $ do
        v <- runMaybeT p
        case v of
            Nothing -> runMaybeT q
            Just _  -> return v

Again this is the same as the Maybe instance with extra wrapping/unwrapping for monad m.

Lifting

class MonadTrans t where
    lift :: (Monad m) => m a -> t m a

Lifting can applied in any monad transformer using the type class MonadTrans:

• t is the monad transformer (e.g. MaybeT)
• m is the underlying monad (e.g. IO)

Lifting for MaybeT

The instance for MaybeT simply has to run the m-action and wrap the result in a Just.

instance MonadTrans MaybeT where
  lift m = MaybeT (m >>= \v -> return (Just v))

ExceptT

Error monad

Recall that the Either type can be used to represent computations that may return exceptions.

data Either a b = Left a | Right b

instance Monad (Either e) where
   return        = Right
   Left e  >>= k = Left e
   Right v >>= k = k v

• Left represents an error result (exception)
• Right represents a valid result
• e is the type of exceptions (e.g. String)

Error transformer

newtype ExceptT e m a
      = ExceptT {runExceptT :: m (Either e a)}

• ExceptT e m adds exceptions of type e to m computations
• When we run an ExceptT computation we get back an Either value wrapped in the underlying monad

runExceptT :: ExceptT e m a -> m (Either e a)

Throwing errors

We can throw an error in an ExceptT computation using throwError.

throwError :: MonadError e m => e -> m a

This is overloaded for any MonadError — so it works with both ExceptT transformers and Either.

StateT

State transformer

Recall the type of state monad:

newtype State s a = State (s -> (a,s))

The type for state transformer:

newtype StateT s m a = StateT (s -> m (a,s))

State monad recap

newtype State s a = State (s -> (a,s))

instance Monad (State s) where
   ...

-- read the state 
get :: State s s
get = State $ \s -> (s,s)

-- write the state
put :: s -> State s ()
put s = State $ \_ -> ((),s))

State monad generalized

The state operations in Control.Monad.State are overloaded using a type class:

get :: MonadState s m => m s
put :: MonadState s m => s -> m ()
modify :: MonadState s m => (s -> s) -> m ()

This allows using these operations on either State or StateT.

ReaderT and WriterT

Reader and Writer

• Reader allows reading from an environment
• Writer allows appending to some output
• They behave like restricted forms of the state monad

newtype Reader e a

newtype Writer w a

ask :: Reader e e  -- fetch current environment

tell :: w -> Writer w ()      -- append output

Reader monad

newtype Reader e a
      = Reader { runReader :: e -> a }

instance Monad (Reader e) where
   return x = Reader $ \e -> x
   Reader f >>= k = Reader $ \e ->
        runReader (k (f e)) e

Behaves like read-only state: the environment e is passed by >>= unmodified

Reader specific operations

-- ask the value of the enviroment
ask :: Reader e e
ask = Reader id

-- modify the value of the environment locally 
local :: (e -> e) -> Reader e a -> Reader e a
local f m = Reader $ \e -> runReader m (f e)

• ask gives the value in the environment
• local runs a sub-computation with a locally modified environment

Writer monad

newtype Writer w a
      = Writer { runWriter :: (a, w) }

• Pair a result value a with some output w
• Parametrized over the type of the output
• The type of outputs w should be a monoid (examples: String, [a])

Writer monad instance

newtype Writer w a
      = Writer { runWriter :: (a, w) }

instance Monoid w => Monad (Writer w) where
   return x = Writer (x, mempty)
   Writer (a, w) >>= k 
            = let (b, w') = runWriter (k a)
              in Writer (b, w `mappend` w')

• return gives the empty output
• >>= concatenates the output of sub-computations

Writer specific functions

tell : w -> Writer w ()
tell w = Writer ((), w) 

Reader and Writer transformers

newtype ReaderT e m a =
        ReaderT {runReaderT :: e -> m a}

newtype WriterT w m a =
        WriterT {runWriterT :: m (a, w)}

• Add Reader or Writer effects to monad m
• Monad instance is analogous to non-transformer ones
• The monad-specific functions are overloaded using type classes, e.g.

ask :: MonadReader e m => m e
tell :: MonadWriter w m => w -> m ()