[Haskell-cafe] Re: list monad and controlling the backtracking

[Benjamin Franksen]

isto wrote:

> Hi all,
> 
> Weekly news had a link to article
> "Local and global side effects with monad transformers"
> and the following is from there (minor modification done):
> 
> import Control.Monad.List
> import Control.Monad.State
> import Control.Monad.Writer
> 
> test5 :: StateT Integer (ListT (Writer [Char])) Integer
> 
> test5 = do
>      a <- lift $ mlist aList
>      b <- lift $ mlist bList
>      lift $ lift $ tell ("trying "++show a++" "++show b++"\n")
>      modify (+1)
>      guard $ a+b<5
>      return $ a+b
> 
> go5 = runWriter $ runListT $ runStateT test5 0
> 
> 
> If the aList = [1..5] as well as bList, then there will be 25 tryings.
> If aList and bList are [1..10000000], there will be a lot of tryings...
> 
> However, guard is saying that we are interested in only values
> whose sum is less than 5.
> 
> Is it possible to control easily in the above example that when we
> have tried out pairs (1,1), (1,2), (1,3), (1,4), that now we are
> ready to stop trying from the bList?  And then similarly when we
> finally arrive to a pair (4,1), that now we are ready to finish
> also with aList?

If I understood you correctly you seem to want a monad that offers something
akin to Prolog's cut. You might want to take a look at
http://okmij.org/ftp/Computation/monads.html#LogicT

Cheers
Ben