Блог

Если у нас есть доска 4×4 с символами (которые могут повторяться) и некоторым случайным словом, нам нужно найти, можно ли найти это слово на доске. Теперь эту проблему довольно легко решить, не используя никаких навороченных штучек. Но с точки зрения обучения, как можно решить эту проблему, когда нам нужно учитывать эти вещи:

• плата постоянна и не собирается меняться, поэтому, допустим, мы заинтересованы в использовании Reader для нее
• при поиске слова нам нужно сохранить набор посещенных плиток на доске, поэтому, допустим, мы заинтересованы в использовании State для этого

Первой идеей было использовать что-то вроде этого:

 findWord :: String -> Position -> ReaderT Board (State (S.Set Position)) -> Bool
  

входная строка — это оставшаяся часть слова, которое мы ищем

где Position (Int, Int) используется для определения того, где мы в данный момент находимся на доске (и устанавливает хранилища, какие позиции мы посетили во время этого пути поиска)

Плата просто хранит информацию о символах в каждой позиции, для простоты ее можно рассматривать как [[Char]]

возвращаемый Bool предназначен для использования в качестве конечного результата, чтобы сказать, содержит ли доска слово или нет

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

Теперь о реальной проблеме: если мы используем State для решения этой проблемы, как нам гарантировать, что функция вернется, как только слово найдено, и не продолжит поиск других путей? Например, если слово, которое мы ищем, «AAAAA», а доска — это просто 16 символов «A», то функция должна вернуться примерно через 5 итераций и не продолжить поиск по всем возможным путям (потому что количество успешных путей огромно)?

Я ищу несколько советов о том, как подойти к этой проблеме, используя одно ограничение, которое является обязательным: использование State monad. Ценна любая информация, будь то совет, псевдокод или даже рабочее решение. Спасибо.

Вместо возврата Bool могу ли я предложить использовать другую монаду в стеке transformer с явной возможностью сокращать вычисления, например Maybe :

 findWord :: String -> Position -> ReaderT Board (StateT (S.Set Position) Maybe) ()
  

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

Теперь вы можете использовать msum (из MonadPlus класса), который будет проверять каждый параметр в списке по очереди и (для стека на Maybe основе) останавливать первый подоперационный, который завершается успешно, или завершать весь, msum если ни один из них не выполняется. Например, что-то вроде

 msum $ map (findWord remainingString) listOfNeighboringPositions