如何重构 Haskell 列表 Monad 代码?

Question

我最近发现了与Control.Monad模块(此处定义(相关的guard函数，它似乎是解决常见编程挑战的完美函数：八皇后问题。我想出了这个解决方案：

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表示法而不是直接使用绑定运算符也可能是一个错误。

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

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 (reverse placed)。