Continuo da qui, copio qui.

**Trasformatore di monadi**

Often we want to “piggyback” monads on top of each other. For instance, there might be a case where you need access to both `IO`

operations through the `IO`

monad and state functions through some state monad. In order to accomplish this, we introduce a `MonadTrans`

class, which essentially “lifts” the operations of one monad into another. You can think of this as stacking monads on top of each other. This class has a simple method: `lift`

. The class declaration for `MonadTrans`

is:

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

The idea here is that t is the outer monad and that m lives inside of it. In order to execute a command of type `Monad m => m a`

, we first lift it into the transformer.

The simplest example of a transformer (and arguably the most useful) is the state transformer monad, which is a state monad wrapped around an arbitrary monad. Before, we defined a state monad as:

`newtype State state a = State (state -> (state, a))`

Now, instead of using a function of type `state -> (state, a)`

as the monad, we assume there’s some other monad `m`

and make the internal action into something of type `state -> m (state, a)`

. This gives rise to the following definition for a state transformer:

**newtype StateT state m a =
StateT (state -> m (state, a))**

For instance, we can think of `m`

as `IO`

. In this case, our state transformer monad is able to execute actions in the `IO`

monad. First, we make this an instance of `MonadTrans`

:

**instance MonadTrans (StateT state) where
lift m = StateT (\s -> do a <- m
return (s,a))**

Here, lifting a function from the realm of `m`

to the realm of `StateT`

state simply involves keeping the state (the `s`

value) constant and executing the action.

Of course, we also need to make `StateT`

a monad, itself. This is relatively straightforward, provided that `m`

is already a monad:

**instance Monad m => Monad (StateT state m) where
return a = StateT (\s -> return (s,a))
StateT m >>= k = StateT (\s -> do
(s', a) <- m s
let StateT m' = k a
m' s')
fail s = StateT (\_ -> fail s)**

The idea behind the definition of `return`

is that we keep the state constant and simply return the state a pair in the enclosed monad. Note that the use of `return`

in the definition of `return`

refers to the enclosed monad, not the state transformer.

In the definition of bind, we create a new `StateT`

that takes a state `s`

as an argument. First, it applies this state to the first action (`StateT m`

) and gets the new state and answer as a result. It then runs the `k`

action on this new state and gets a new transformer. It finally applies the new state to this transformer. This definition is nearly identical to the definition of bind for the standard (non-transformer) `State`

monad described in the section on State [qui].

The `fail`

function passes on the call to `fail`

in the enclosed monad, since state transformers don’t natively know how to deal with failure.

Of course, in order to actually use this monad, we need to provide function `getT`

, `putT`

and `evalStateT`

. These are analogous to `getState`

, `putState`

and `runStateM`

from the section on `State`

:

**getT :: Monad m => StateT s m s
getT = StateT (\s -> return (s, s))
putT :: Monad m => s -> StateT s m ()
putT s = StateT (\_ -> return (s, ()))
evalStateT :: Monad m => StateT s m a -> s -> m a
evalStateT (StateT m) state = do
(s', a) <- m state
return a**

These functions should be straightforward. Note, however, that the result of `evalStateT`

is actually a monadic action in the enclosed monad. This is typical of monad transformers: they don’t know how to actually run things in their enclosed monad (they only know how to lift actions). Thus, what you get out is a monadic action in the inside monad (in our case, `IO`

), which you then need to run yourself.

We can use state transformers to reimplement a version of our `mapTreeM`

function from the section on `State`

. The only change here is that when we get to a leaf, we print out the value of the leaf; when we get to a branch, we just print out “Branch.”

**mapTreeM action (Leaf a) = do
lift (putStrLn ("Leaf " ++ show a))
b <- action a
return (Leaf b)
mapTreeM action (Branch lhs rhs) = do
lift (putStrLn "Branch")
lhs' <- mapTreeM action lhs
rhs' <- mapTreeM action rhs
return (Branch lhs' rhs')**

The only difference between this function and the one from the section on State is the calls to lift (`putStrLn ...`

) as the first line. The lift tells us that we’re going to be executing a command in an enclosed monad. In this case, the enclosed monad is `IO`

, since the command lifted is `putStrLn`

.

The type of this function is relatively complex:

**mapTreeM :: (MonadTrans t, Monad (t IO), Show a) =>
(a -> t IO a1) -> Tree a -> t IO (Tree a1)**

Ignoring, for a second, the class constraints, this says that `mapTreeM`

takes an action and a tree and returns a tree. This just as before. In this, we require that t is a monad transformer (since we apply lift in it); we require that `t IO`

is a monad, since we use `putStrLn`

we know that the enclosed monad is `IO`

; finally, we require that `a`

is an instance of `show`

— this is simply because we use `show`

to show the value of leaves.

Now, we simply change `numberTree`

to use this version of `mapTreeM`

, and the new versions of `get`

and `put`

, and we end up with:

**numberTree tree = mapTreeM number tree
where number v = do
cur <- getT
putT (cur+1)
return (v,cur)**

Using this, we can run our monad (Nota: non sufficientemente chiaro per me che codice devo inserire):

`MTrans> `**evalStateT (numberTree testTree) 0**
Branch
Branch
Leaf 'a'
Branch
Leaf 'b'
Leaf 'c'
Branch
Leaf 'd'
Leaf 'e'
*MTrans> **it**
Branch (Branch (Leaf ('a',0))
(Branch (Leaf ('b',1)) (Leaf ('c',2))))
(Branch (Leaf ('d',3)) (Leaf ('e',4)))

One problem not specified in our discussion of `MonadPlus`

is that our search algorithm will fail to terminate on graphs with cycles. Consider:

**gr3 = Graph [(0, 'a'), (1, 'b'), (2, 'c'), (3, 'd')]
[(0,1,'l'), (1,0,'m'), (0,2,'n'),
(1,3,'o'), (2,3,'p')]**

In this graph, there is a back edge from node `b`

back to node `a`

. If we attempt to run `searchAll2`

, regardless of what monad we use, it will fail to terminate. Moreover, if we move this erroneous edge to the end of the list (and call this `gr4`

), the result of `searchAll2 gr4 0 3`

will contain an infinite number of paths: presumably we only want paths that don’t contain cycles.

In order to get around this problem, we need to introduce state. Namely, we need to keep track of which nodes we have visited, so that we don’t visit them again.

We can do this as follows:

**searchAll5 g@(Graph vl el) src dst
| src == dst = do
visited <- getT
putT (src:visited)
return [src]
| otherwise = do
visited <- getT
putT (src:visited)
if src `elem` visited
then mzero
else search' el
where
search' [] = mzero
search' ((u,v,_):es)
| src == u =
(do path <- searchAll5 g v dst
return (u:path)) `mplus`
search' es
| otherwise = search' es**

Here, we implicitly use a state transformer (see the calls to `getT`

and `putT`

) to keep track of visited states. We only continue to recurse, when we encounter a state we haven’t yet visited. Furthermore, when we recurse, we add the current state to our set of visited states.

Now, we can run the state transformer and get out only the correct paths, even on the cyclic graphs:

`MTrans> `**evalStateT (searchAll5 gr3 0 3) [] :: [[Int]]**
[[0,1,3],[0,2,3]]
MTrans> **evalStateT (searchAll5 gr4 0 3) [] :: [[Int]]**
[[0,1,3],[0,2,3]]

Here, the empty list provided as an argument to `evalStateT`

is the initial state (i.e., the initial visited list). In our case, it is empty.

We can also provide an `execStateT`

method that, instead of returning a result, returns the final state. This function looks like:

**execStateT :: Monad m => StateT s m a -> s -> m s
execStateT (StateT m) state = do
(s', a) <- m state
return s'**

This is not so useful in our case, as it will return exactly the reverse of `evalStateT`

(try it and find out!), but can be useful in general (if, for instance, we need to know how many numbers are used in `numberTree`

).

Oviamente mi sono perso 😡 Prossimamente gli esercizi.

👽