How do I convert a list monadic function to a breadth-first search?

Question

I just got over the hump of figuring out how to use the List monad to do nondeterministic computations. However I believe my algorithm would benefit from a breadth-first search instead of a depth-first one which you get from the List monad.

Here is an excerpt showing the interesting part of my algorithm. It is a solver for the logic puzzle Akari.

solve :: Game -> [Game]
solve game = do
        let ruleBasedSolverResult = applyRuleBasedSolversUntilSteady game
        guard $ consistant ruleBasedSolverResult
        if solved ruleBasedSolverResult
                then return ruleBasedSolverResult
                else speculate ruleBasedSolverResult

speculate :: Game -> [Game]
speculate game = do
        coord <- coords game
        guard $ lightableUnlit game coord
        let solutions = solve $ light game coord
        if null solutions
                then solve $ exclude game coord
                else solutions

Basically it applies some basic deterministic rules to see if that solves it. If not it tries putting lights in various places. If a light makes a puzzle inconsistent after recursing to solve it places an exclusion mark where the light was and proceeds. If it finds solutions while placing lights then it adds those to the list of solutions.

This works fine, but is slow because often there is an obvious choice for which coord to speculate on that will quickly result in an inconsistent puzzle and let you place an x with just one (or two) levels of search, but if it doesn't choose that coord until halfway through the search then it winds up chewing a bunch of uninteresting stuff first. Thus the breadth-first search idea.

I have googled things like "breadth first nondetermanism monad" and I get a few results that are difficult for me to understand, like:

• Control.Monad.Omega This seems like overkill for what I need because it seems to guard against infinitely diverging determinism which is not the case for me, and I don't completely understand it.

• Control.Monad.WeightedSearch the docs for Control.Monad.Omega suggest using this instead when using it as a Monad, but I think weighting is also a bit overkill for my needs. I would likely just have 2 weights, one for things with solutions and one for things that don't have solutions.

• Control.Monad.Level I don't believe this will work for what I want since only the leaves of the tree have values.

• Data.Tree I think this might be what I want to use, but I'm not sure how to convert my List monadic code to use it, though I feel like there's a beautiful way.

My next question will be about how to parallelize it :)

Answer 1

I believe that "Backtracking, Interleaving, and Terminating Monad Transformers" (Functional Pearl) by Kiselyov, Shan and Friedman outlines a solution.

Disclaimer: I am not an expert in this work!

Basically, you have to use a different monad. Since the ListT monad transformer does depth-first, they came up with a new monad transformer LogicT which does breadth-first. (If you're not interested in monad transformers, you can just apply a transformer to Id to get back a regular monad).

First, they recognize deficiencies in other approaches:

the straightforward depth-first search performed by most implementations of MonadPlus is not fair: a non-deterministic choice between two alternatives tries every solution from the first alternative before any solution from the second alternative. When the first alternative offers an infinite number of solutions, the second alternative is never tried, making the search incomplete. Indeed, as our examples in Section 3 show, fair backtracking helps more logic programs terminate.

[...]

The second deficiency in many existing backtracking monads is the adoption of Prolog’s cut, which confounds negation with pruning. Theoretically speaking, each of negation and pruning independently makes logic programming languages more expressive

[...]

The third practical deficiency is the often-forgotten top-level interface: how to run and interact with a computation that may return an infinite number of answers? The most common solution is to provide a stream that can be consumed or processed at the top- level as desired. But in the case of monad transformers, this solution only works if the base monad is non-strict (such as Haskell’s lazy list monad and LazyST). In the case where the base monad is strict, the evaluation may diverge by forcing the evaluation of the entire stream, even if we only desire one answer.

They then present a solution based on the LogicT monad transformer and the msplit function. Although the link to the code is broken, I searched Hoogle for LogicT and found this.

I hope that reading this paper will give you a good background in this topic and help you to understand how to use the projects that you already found.

If you find this paper useful, don't forget to check out its references and the other papers that cite it!