haskell - 如何将列表一元函数转换为广度优先搜索？

Question

我刚刚克服了弄清楚如何使用 List monad 进行不确定性计算的困难。不过，我相信我的算法将受益于广度优先搜索，而不是从 List monad 中获得的深度优先搜索。

这是显示我的算法有趣部分的摘录。它是逻辑谜题 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

基本上，它应用了一些基本的确定性规则来看看是否可以解决问题。如果没有，它会尝试在不同的地方放置灯光。如果一盏灯在递归解决后使谜题变得不一致，它会在该灯所在的位置放置一个排除标记并继续进行。如果它在放置灯光时找到解决方案，则会将其添加到解决方案列表中。

这工作正常，但速度很慢，因为通常有一个明显的选择来推测哪个坐标，这将很快导致不一致的谜题，并让你只用一个(或两个)级别的搜索来放置一个 x，但是如果直到搜索进行到一半时它才会选择该坐标，然后它最终会首先咀嚼一堆无趣的东西。因此广度优先搜索思想。

我在谷歌上搜索了诸如“广度优先非决定论单子(monad)”之类的内容，得到了一些对我来说很难理解的结果，例如:

• Control.Monad.Omega对于我所需要的东西来说，这似乎有点矫枉过正，因为它似乎可以防止无限发散的决定论，而我的情况并非如此，而且我并不完全理解它。

• Control.Monad.WeightedSearch Control.Monad.Omega 的文档建议在将其用作 Monad 时使用它，但我认为权重对于我的需求来说也有点过分了。我可能只有 2 个权重，一个用于有解决方案的事物，另一个用于没有解决方案的事物。

• Control.Monad.Level我不相信这能达到我想要的效果，因为只有树的叶子才有值(value)。

• Data.Tree我认为这可能是我想要使用的，但我不确定如何转换我的 List 单子(monad)代码来使用它，尽管我觉得有一种漂亮的方法。

我的下一个问题将是关于如何并行化它:)

Answer 1

我相信"Backtracking, Interleaving, and Terminating Monad Transformers" (Functional Pearl) by Kiselyov, Shan and Friedman概述了解决方案。

免责声明:我不是这项工作的专家!

基本上，你必须使用不同的 monad。由于 ListT monad 转换器执行深度优先，因此他们提出了一个新的 monad 转换器 LogicT ，它执行广度优先。 (如果您对 monad 转换器不感兴趣，您只需将转换器应用于 Id 即可获取常规 monad)。

首先，他们认识到其他方法的缺陷:

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.

然后，他们提出了一个基于 LogicT monad 转换器和 msplit 函数的解决方案。尽管代码链接已损坏，但我在 Hoogle 中搜索了 LogicT 并找到了 this .

我希望阅读本文能够为您提供该主题的良好背景知识，并帮助您了解如何使用您已经找到的项目。

如果您发现本文有用，请不要忘记查看其引用文献以及引用它的其他论文!