Как мне рефакторировать Haskell список кодов монад? - PullRequest
Новая
       5

Как мне рефакторировать Haskell список кодов монад?

0 голосов
/ 12 января 2020

Я недавно обнаружил функцию guard, связанную с модулем Control.Monad (определено здесь ), и она, казалось, была идеальной функцией для решения типичной задачи программирования: проблема восьми королев . Я пришел к такому решению: 

import Control.Monad (guard)

type Pair a = (a, a)

eight_queens :: [[Pair Int]]
eight_queens = do
  r1 <- tag 1 [1..8]
  guard $ all (friendly r1) []
  r2 <- tag 2 [1..8]
  guard $ all (friendly r2) [r1]
  r3 <- tag 3 [1..8]
  guard $ all (friendly r3) [r1, r2]
  r4 <- tag 4 [1..8]
  guard $ all (friendly r4) [r1, r2, r3]
  r5 <- tag 5 [1..8]
  guard $ all (friendly r5) [r1, r2, r3, r4]
  r6 <- tag 6 [1..8]
  guard $ all (friendly r6) [r1, r2, r3, r4, r5]
  r7 <- tag 7 [1..8]
  guard $ all (friendly r7) [r1, r2, r3, r4, r5, r6]
  r8 <- tag 8 [1..8]
  guard $ all (friendly r8) [r1, r2, r3, r4, r5, r6, r7]
  return [r1, r2, r3, r4, r5, r6, r7, r8]

tag :: Int -> [Int] -> [Pair Int]
tag n = zipWith (,) (repeat n)

friendly :: Pair Int -> Pair Int -> Bool
friendly cell@(r,c) cell'@(r',c')
  | r == r' = False
  | c == c' = False
  | diagonal cell cell' = False
  | otherwise = True

diagonal :: Pair Int -> Pair Int -> Bool
diagonal (r,c) (r',c') = abs (r - r') == abs (c - c')

main :: IO ()
main = print eight_queens

Код компилируется и выдает выходные данные, которые кажутся в основном правильными, но я пытаюсь выполнить рефакторинг для решения более общей проблемы n-queens с n, передаваемым как аргумент n_queens. Код кажется очень повторяющимся, предполагая, что можно использовать рекурсивную функцию monadi c, но это удалит найденные ячейки из области видимости. Это также может быть ошибкой при использовании прямой нотации, а не оператора связывания напрямую.

Игнорирование производительности и пригодности алгоритма, который я использовал, и моего стиля кодирования, такого как объявление вспомогательных функций в top- Пространство имен уровня.

1 Ответ

1 голос
/ 12 января 2020

Вы можете выполнять возврат, сохраняя при этом список уже размещенных ферзей: 

place :: Int -> [Pair Int] -> [[Pair Int]]
place 9 placed = return placed
place n placed = do
   r <- tag n [1..8]
   guard $ all (friendly r) placed
   place (n + 1) (r : placed)

eight_queens :: [[Pair Int]]
eight_queens = place 1 []

Первый параметр Int - это тег следующей фермы для размещения, второй параметр [Pair Int] - это список уже размещенных ферзей.

(Это вернет ферзей в обратном порядке по отношению к вашему коду. Если вам нужен этот порядок, используйте return (reverse placed).)

...