[Haskell-cafe] list monad and controlling the backtracking

Henk-Jan van Tuyl hjgtuyl at chello.nl
Fri Nov 24 16:14:47 EST 2006



The idea of backtracking is, that you try all options because you can't  
tell/calulate in advance which parameters lead to a solution; if you have  
some idea about where and how to limit your search, you may save a lot of  
time. In your example, you can limit your search by replacing the lines:
>      a <- lift $ mlist aList
>      b <- lift $ mlist bList
with:
>      a <- lift $ mlist $ take 4 aList
>      b <- lift $ mlist $ take 4 bList

In some cases you could use the "filter" function:
>      a <- lift $ mlist $ filter (< 5) aList
>      b <- lift $ mlist $ filter (< 5) bList

Or "takeWhile":
>      a <- lift $ mlist $ takeWhile (< 5) aList
>      b <- lift $ mlist $ takeWhile (< 5) bList

Etc.


Met vriendelijke groet,
Henk-Jan van Tuyl


--

On Thu, 23 Nov 2006 22:25:23 +0100, isto <isto.aho at dnainternet.net> 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?
>
> This would give a nice way to build branch & bounding algorithms,
> even though it does not take much more lines to do it in some other way.
>
> br, Isto
>
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe



-- 
http://Van.Tuyl.eu/
--

Using Opera's revolutionary e-mail client:
https://secure.bmtmicro.com/opera/buy-opera.html?AID=789433



More information about the Haskell-Cafe mailing list