如何重构 Haskell list Monad 代码？

Question

我最近发现了与 Control.Monad 模块关联的 guard 函数（定义 here) and it seemed to be a perfect function to solve a common programming challenge: the eight queens problem。我想出了这个解决方案：

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。该代码似乎非常重复，表明可以使用递归单子函数，但这会从范围中删除找到的单元格。使用 do-notation 而不是直接绑定运算符也可能是错误的。

忽略我使用的算法的性能和适用性以及我的编码风格，例如在顶级命名空间中声明辅助函数。

Answer 1

您可以在保留已放置皇后列表的同时进行递归：

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 皇后的顺序与您的代码相反。如果您需要该顺序，请改用 return (reverse placed)。）

如何重构 Haskell list Monad 代码？

How do I refactor Haskell list Monad code?

monads

refactoring

haskell