Haskell – 188 – monadi – 9

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.

👽

Posta un commento o usa questo indirizzo per il trackback.

Trackback

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo di WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione /  Modifica )

Google photo

Stai commentando usando il tuo account Google. Chiudi sessione /  Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione /  Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione /  Modifica )

Connessione a %s...

Questo sito utilizza Akismet per ridurre lo spam. Scopri come vengono elaborati i dati derivati dai commenti.

%d blogger hanno fatto clic su Mi Piace per questo: