Haskell List Monad State Dependance

Question

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

(Моя проблема заключается в заполнении nxm доски судами и водой. Я получаю суммы рядов и количеств, каждая часть корабля имеет свою ценность etd его не важно сейчас).

Я хочу охранять как можно раньше, чтобы сделать алгоритм эффективным, заключается в том, что возможность вставки корабля зависит от того, что мне дано/что я вставил в перемещение previus, позволяет назвать это состояние платы, и я понятия не имею как передать его Потому что я не могу генерировать новое состояние от одной только платы)

Мои Algoritm является: 1. Инициализировать Первый совет 2. сформировать Первая строка пытается применять все возможные вставки (я могу вставить овец verticaly так я необходимо помнить о том, чтобы вставить другие части овец в нижние ряды) 3. Решите проблему для небольшой доски (ofc после генерации каждые 2 строки, я все проверю)

Но я не знаю, как я могу передавать новые состояния, потому что, насколько я читал о State Monad, он генерирует новое состояние только из старого состояния, и это невозможно для меня, я бы хотел создать новое состояние при выполнении операций по значению).

Прошу прощения за мою ненависть к Haskell, но после нескольких лет программирования на императивных языках, вынужденных сражаться с этими Монадами, чтобы делать то, что на других языках, которые я мог написать почти мгновенно, заставляет меня сходить с ума. (ну другие вещи в Haskell хороши для меня, и некоторые из них на самом деле довольно приятные).

Answer 1

Комбинируйте StateT со списком monad, чтобы получить ваше поведение.

Вот простой пример использования индетерминизма из списка монады сохраняя историю предыдущих выборов сделали:

import Control.Monad 
import Control.Monad.Trans.Class 
import Control.Monad.Trans.State 

fill :: StateT [Int] [] [Int] 
fill = do 
    history <- get 
    if (length history == 3) 
     then return history 
     else do 
      choice <- lift [0, 1, 2] 
      guard (choice `notElem` history) 
      put (choice:history) 
      fill 

fill поддерживает отдельную историю для каждого пути, который он пробует. Если он заполняет доску, он возвращается успешно, но если текущий выбор перекрывается с предыдущим выбором, он отказывается от этого решения и пытается использовать другой путь.

Вы запускаете его с помощью evalStateT, снабжая первоначальную пустую историю:

>>> evalStateT fill [] 
[[2,1,0],[1,2,0],[2,0,1],[0,2,1],[1,0,2],[0,1,2]] 

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