Insipred by Monadic Conctraint Programming by Tom Schrijvers et. al., I wrapped up some thoughts on the difference between monadic and queue-based tree search.

I started a program to explore their connections (to get the Haskell file, simply strip off the .html suffix). There is a challenge! I you master it, send me your solution and I’ll publish it here.

Comments can be placed on reddit.

Note: You need to install SmallCheck in order to run the above code.

Update

Tom Schrijvers has sent me solutions to the challenge that are now documented in the above program.

When comparing queue-based and monadic search it turns out that simulating one with the other is sometimes easy (dfs, bfs) but may be tricky in other cases. There does not seem to be an easy way (i.e., one that is obviously correct) of simulating the interleaving monad with a queue, and there also is no obvious monad that simulates the alternating queue. It would be nice to have a general scheme how to express one with the other.

When using a monad as strategy, one can give a custom implementation of bind, which is fixed in the queue-based approach of mcp (the Tree type is the monad and fixes the implementation of bind). I could mimic this approach by using a Tree monad and a queue-based search on the result. My main motivation of not fixing the monad is to be able to use the Stream monad by Oleg Kiselyov. It is the most efficient implementation of complete search that I know of (without using a depth- or similar limit). Its efficiency crucially relies on the implementation of bind.