[Haskell-cafe] Monad with limited backtracking

[Strake]

On 12/07/2012, Darryn Reid <djreid at aapt.net.au> wrote:
> I have formulated a monad to provide
> limited backtracking for implementing a rewrite system. The success case
> works fine, but my intention is that on failure the result should contain the list
> of input symbols consumed up to the failure, and it is this part that I would
> like some advice about. Code follows:
> -------------------------------------------------------------------------------
> import Control.Monad
> import Debug.Trace
>
> newtype Rewrite a b = Rewrite { run :: Input a -> Result a b }
>
> data Input a = Input [a]

Why this type? to define other instances?

> data Result a b = Fail [a] | Ok b [a]
>                   deriving (Eq, Show)
>
> instance (Show a) => Monad (Rewrite a) where
>    return y = Rewrite $ \(Input xs) -> Ok y xs
>    p >>= f  = Rewrite $ \inp ->
>                  case run p inp of
>                    Fail xs -> trace ("1.xs=" ++ show xs) $
>                               Fail xs
>                    Ok y xs -> case run (f y) (Input xs) of
>                                 Fail xs' -> trace ("2.xs=" ++ show xs) $
>                                             Fail xs
>                                 okay -> okay
>
> instance (Show a) => MonadPlus (Rewrite a) where
>    mzero = Rewrite $ \inp -> Fail []
>    p `mplus` q = Rewrite $ \inp -> case run p inp of
>                                      Fail _ -> run q inp
>                                      okay   -> okay
> (>>=?) ::(Show a) => Rewrite a b -> (b -> Bool) -> Rewrite a b
> p >>=? f = p >>= \y -> guard (f y) >> return y
>
> next :: Rewrite a a
> next = Rewrite $ \(Input xs) -> case xs of
>                                   []      -> Fail []
>                                   (x:xs') -> Ok x xs'

So where are the prior matched symbols? They must be kept somewhere.
Result seems to keep symbols that may be matched in future, not that
have been matched in past. Actually, both must be kept somewhere.

> exactly :: (Show a, Eq a) => [a] -> Rewrite a [a]
> exactly = mapM $ \i -> next >>=? (==i)
> -------------------------------------------------------------------------------
> For example, using ghci:
>     *Main> run (exactly [1,2]) (Input [1,2,3,4])
>     Ok [1,2] [3,4]
> which is what I intend. However, while the thing correctly reports failure,
> I
> cannot get it to return the list of symbols up to the point of failure:
>     *Main> run (exactly [1,2,3]) (Input [1,2,7,4])
>     1.xs=[]
>     2.xs=[4]
>     1.xs=[4]
>     1.xs=[4]
>     2.xs=[7,4]
>     1.xs=[7,4]
>     2.xs=[2,7,4]
>     Fail [2,7,4]      *I would like Fail [1,2] here instead*
>
> I thank you in advance for any guidance you might offer.
>
> Dr Darryn J Reid.

This works as bidden: http://hpaste.org/71332

BackTrack> :t unBT
unBT :: BackTrack a b -> [a] -> Either [a] ([a], b, [a])
BackTrack> unBT (exactly [1,2]) [1,2,3,4]
Right ([1,2],[1,2],[3,4])
BackTrack> unBT (exactly [1,2,3]) [1,2,7,4]
Left [1,2]

Cheers,
Strake