如何将列表monadic函数转换为广度优先搜索？

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

基本上它应用一些基本的确定性规则来看看是否能解决它.如果没有,它会尝试将灯光放在不同的地方.如果光线在递归解决后使拼图不一致,则在光线所在的位置放置一个排除标记.如果在放置灯光时找到解决方案,则会将其添加到解决方案列表中.

这样做很好,但速度很慢,因为通常有一个明显的选择,哪个coord可以快速导致一个不一致的拼图,让你只用一(或两个)级别的搜索放置一个x,但如果它没有'在搜索到中途之前选择那个coord然后它会先咀嚼一堆无趣的东西.因此,广度优先搜索的想法.

我用谷歌搜索了"广泛的第一个非反感monad",我得到了一些难以理解的结果,如:

• Control.Monad.Omega对于我需要的东西来说这似乎有点过分,因为它似乎可以防止无限分歧的决定论,但对我来说并非如此,我并不完全理解它.

• Control.Monad.Weighted搜索Control.Monad.Omega 的文档建议在使用它作为Monad时使用它,但我认为加权对我的需求来说也有点矫枉过正.我可能只有2个权重,一个用于解决方案,一个用于没有解决方案的东西.

• Control.Monad.Level我不相信这会对我想要的东西起作用,因为只有树的叶子有值.

• Data.Tree我认为这可能是我想要使用的,但我不知道如何转换我的List monadic代码来使用它,虽然我觉得有一种美妙的方式.

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

Answer 1

我相信Kiselyov,Shan和Friedman的"回溯,交错和终止Monad变形金刚"(功能明珠)概述了一个解决方案.

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

基本上,你必须使用不同的monad.由于ListTmonad变压器具有深度优先性,因此他们想出了一种新的monad变压器LogicT,它实现了广度优先.(如果你对monad变换器不感兴趣,你可以只使用变换器来Id取回常规monad).

首先,他们认识到其他方法的不足之处:

大多数MonadPlus实现执行的直接深度优先搜索是不公平的:两个备选方案之间的非确定性选择在第二个备选方案的任何解决方案之前尝试来自第一个备选方案的每个解决方案.当第一个替代方案提供无限数量的解决方案时,从不尝试第二种替代方案,使搜索不完整.实际上,正如我们在第3节中的示例所示,公平的回溯有助于更多的逻辑程序终止.

[...]

许多现有的回溯单子的第二个缺点是采用了Prolog的切割,这使修剪与否定相混淆.从理论上讲,每个否定和修剪都使逻辑编程语言更具表现力

[...]

第三个实际缺陷是经常被遗忘的顶级界面:如何运行并与可能返回无数答案的计算进行交互？最常见的解决方案是提供可根据需要在顶层使用或处理的流.但是对于monad变换器,此解决方案仅在基本monad不严格时才有效(例如Haskell的惰性列表monad和LazyST).在基本monad严格的情况下,即使我们只想要一个答案,评估也可能通过强制评估整个流而发散.

然后,他们提出了基于LogicTmonad变压器和msplit功能的解决方案.虽然代码的链接已被破坏,但我搜索了Hoogle LogicT并找到了这个.

我希望阅读本文将为您提供本主题的良好背景,并帮助您了解如何使用您已找到的项目.

如果您发现本文有用,请不要忘记查看其参考文献和其他引用它的论文!