Sunday, March 25, 2012

A fail-back monad

MFlow can express a complete Web navigation within a simple procedure, just like a console program. The problem of this model is the back button. There is nothing like the back button in console applications.  The user can not decide to go back in a console application. but in a Web application, the user can do it.

Since I want to go back to the code of the previous user interactions, not just to the previous statement, I need a monad transformer which permits the creation of ckeckpoints form which the computation can be resumed when the received result does not match with the output expected from the last form that was sent to the user. If the user go back, what the application receives is an output corresponding to a past interaction. Then I do not receive what I expect. I need a way to go back in my code acordingly upto the user interaction step that match the output.

Since my interaction is basically similar to a console application, this example below would be a simple console translation for my problem. liftRepeat will label the checkpoint from which I want to go back and repeat the code when fail is invoked.

1
2
3
4
5
6
7
8
9
test= runBackT $ do
       lift $ print "will not return back here"
        liftBackPoint $ print "will return here"
        n2  <- lift $ getLine
        lift $ print "second input"
        n3  <- lift $  getLine
        if n3 == "back"
                   then  fail ""
                   else lift $ print  $ n2++n3

Whenever the second input is "back" The procedure will go back to where liftBackPoint is. Otherwise, it will return the concatenation of the two inputs.

Here below is the failback monad transformer.  (I will not call it "backtracking" since this term has a tradition in non-deterministic logic programming). 

The monad instance is similar to what would be an identity monad transformer  as long as NoRepeat is used. But when GoBack found, the monad roll back until a BackPoint is found and the computation start again from it. 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
data FailBack a = BackPoint a | NoBack a | GoBack  
newtype BackT m a = BackT { runBackT :: m (FailBack a ) }


instance Monad m => Monad (BackT  m) where
    fail   _ = BackT $ return GoBack
    return x = BackT . return $ NoBack x
    x >>= f  = BackT $ loop
     where
     loop = do
        v <- runBackT x
        case v of
            NoBack y  ->; runBackT (f y)
            BackPoint y  ->; do
                 z <- runBackT (f y)
                 case z of
                  GoBack  ->; loop
                  other ->; return other
            GoBack -> return  GoBack


backPointReturn x= BackT . return $ BackPoint x
liftBackPoint f= BackT $ f >>= \x -> return $ BackPoint x
backPointHere :: Monad m => BackT m ()
backPointHere = backPointReturn ()



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
instance (MonadIO m, MonadState s m) =>; MonadIO (BackT  m) where
  liftIO f= BackT $ liftIO  f >>= \ x -> return $ NoBack x

instance (Monad m,Functor m) => Functor (BackT m) where
  fmap f g= BackT $ do
     mr <- runBackT g
     case mr of
      BackPoint x  -> return . BackPoint $ f x
      NoBack x     -> return . NoBack $ f x
      GoBack       -> return   GoBack

instance MonadTrans BackT where
  lift f= BackT $ f >>= \x ->  return $ NoBack x

instance MonadState s m => MonadState s (BackT m) where
   get= lift get
   put= lift . put




These are the instances that I need to lift the computations to the failback monad.

I suspect that this monad has more applications. For example it can be used to generalize exceptions for any monad

See this short mail list discussion where Oleg shows some alternatives:

http://haskell.1045720.n5.nabble.com/Fail-back-monad-td5599230.html

An important advantage of this monad is that it is tail recursive, unlike other alternatives, and captures all the semantic of the problem and the solution in a single monad, instead of a combination of monads.