Как преобразовать монадическую функцию списка в поиск в ширину?

Question

Я только что понял, как выяснить, как использовать монаду List для недетерминированных вычислений. Однако я полагаю, что мой алгоритм выиграл бы от поиска в ширину вместо поиска в глубину, получаемого из монады List.

Вот выдержка, показывающая интересную часть моего алгоритма. Это решатель для логической головоломки Акари.

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 только с одним (или двумя) уровнями поиска, но если это не так не выбирайте эту координату до тех пор, пока в середине поиска не произойдет, и она сначала будет жевать кучу неинтересных вещей. Таким образом, идея поиска в ширину.

Я погуглил такие вещи, как "первая монета недетерманизма", и получил несколько результатов, которые мне трудно понять, например:

• Control.Monad.Omega Это кажется излишним для того, что мне нужно, потому что кажется, что оно защищает от бесконечно расходящегося детерминизма, что не так для меня, и я не совсем понимаю это.

• Control.Monad.WeightedSearch Документы для Control.Monad.Omega предлагают использовать это вместо того, чтобы использовать его в качестве монады, но я думаю, что взвешивание также немного излишним для моих нужд. Скорее всего, у меня было бы 2 веса, один для вещей с решениями и один для вещей, у которых нет решений.

• Control.Monad.Level Я не верю, что это будет работать для того, что я хочу, так как только листья дерева имеют значения.

• Я думаю, что это может быть то, что я хочу использовать, но я не уверен, как преобразовать мой монадический код List, чтобы использовать его, хотя я чувствую, что есть красивый способ.

Мой следующий вопрос будет о том, как распараллелить это:)

Answer 1

Я считаю, что "Возвращение, чередование и прекращение монадных трансформаторов" (функциональная жемчужина) Киселева, Шана и Фридмана обрисовывает в общих чертах решение.

Отказ от ответственности: я не эксперт в этой работе!

По сути, вы должны использовать другую монаду. Так как ListT Монадный трансформатор делает глубину, они придумали новый монадный трансформатор LogicT который делает ширину в первую очередь. (Если вас не интересуют монадные трансформаторы, вы можете просто применить трансформатор к Id чтобы вернуть обычную монаду).

Во-первых, они признают недостатки в других подходах:

простой поиск в глубину, выполняемый большинством реализаций MonadPlus, не является справедливым: недетерминированный выбор между двумя альтернативами пробует каждое решение из первой альтернативы перед любым решением из второй альтернативы. Когда первая альтернатива предлагает бесконечное количество решений, вторая альтернатива никогда не пробуется, что делает поиск неполным. На самом деле, как показывают наши примеры в Разделе 3, верный возврат помогает большему количеству логических программ завершиться.

[...]

Вторым недостатком во многих существующих монадах обратного следования является принятие среза Пролога, который смешивает отрицание с обрезкой. Теоретически, каждое из отрицания и сокращения независимо делает языки логического программирования более выразительными

[...]

Третий практический недостаток - часто забываемый интерфейс верхнего уровня: как запустить и взаимодействовать с вычислениями, которые могут возвращать бесконечное количество ответов? Наиболее распространенным решением является предоставление потока, который может потребляться или обрабатываться на верхнем уровне по желанию. Но в случае монадных преобразователей это решение работает только в том случае, если базовая монада не является строгой (например, монада ленивого списка на Haskell и LazyST). В случае, когда базовая монада строгая, оценка может расходиться, форсируя оценку всего потока, даже если мы хотим получить только один ответ.

Затем они представляют решение на основе LogicT монадный трансформатор и тому msplit функция. Хотя ссылка на код не работает, я искал в Google LogicT и нашел это.

Я надеюсь, что чтение этой статьи даст вам хорошее представление об этой теме и поможет понять, как использовать проекты, которые вы уже нашли.

Если вы находите эту статью полезной, не забудьте проверить ее ссылки и другие документы, в которых она цитируется!