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 :)</div