Problem with backtracking monad transformer

[Andrew J Bromage]

G'day all.

On Thu, Jan 30, 2003 at 01:55:50PM -0000, Guest, Simon wrote:

> I'm trying to make a backtracking state monad using Ralf Hinze's
> backtracking monad transformer.  My problem is that it won't backtrack
> very far.
> 
> Suppose I try ( a >> b ) `mplus` c.
> 
> If b fails, it should try c, but it doesn't rewind past a.

I added this to your source file:

testBACKTR :: (Monad m) => BACKTR m Int
testBACKTR
    = ( return 1 >> M.mzero ) `M.mplus` (return 2)

main :: IO ()
main = putStrLn (show (observe testBACKTR :: Maybe Int))

The result is "Just 2", so I don't think there's anything wrong with
your implementation of BACKTR.  I've compared it with my own
well-tested implementation and it seems identical modulo renamings.

In case you want to compare:

	http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/hfl/hfl/mtl/

I didn't follow the rest of the code, so I suspect the problem is
elsewhere.  One place to look is here:

> -- backtracking state monad
> --
> type NDSM st a = BACKTR (SM st) a

You may have meant to stack the monad transformers in a different
order.

Cheers,
Andrew Bromage