如何使用replicateM解决八皇后问题？

Question

我刚开始学习编写Haskell代码，所以如果我提出了一个愚蠢的问题，请原谅。我正在尝试通过使用[]单子来重新解决八皇后问题。下面是代码：

import Control.Monad

addqueen :: [Int] -> [[Int]]
addqueen xs = [ x:xs | x <- [1,2..8], 
    not $ x `elem` xs 
        || (any (\ (index,q) -> abs (x-q) == index) $ zip [1..] xs) ]

当我尝试

[[]] >>= replicateM 8 addqueen

它无法工作，但会产生以下错误：

Couldn't match expected type `t0 -> t1' with actual type `[[a0]]'
The first argument of ($) takes one argument,
but its type `[[a0]]' has none
In the expression: [[]] >>= replicateM 8 $ addqueen
In an equation for `it': it = [[]] >>= replicateM 8 $ addqueen

那么我该如何实现我想要做的事情呢？

- user2812201

---

“[[]]>>= replicateM 8 addqueen”这段代码的预期效果不是很清楚。请注意，"[[]] >>= f" 等同于 "f []"。 - Sjoerd Visscher

如果我这样做"[[]]>>=addqueen >>=addqueen >>=addqueen >>=addqueen >>=addqueen >>=addqueen >>=addqueen >>=addqueen"，我可以得到结果，但是这真的很繁琐。我正在寻找一种“语法糖”来简化调用。 - user2812201

如果我没有错的话，这看起来像是 iterate (>>= addqueen) [[]] !! 8。 - Sjoerd Visscher

foldl (>>=) [[]] $ replicate 8 addqueen - Sassa NF

Answer 1

replicateM 在这里选择不当：

Prelude Control.Monad> :t replicateM
replicateM :: (Monad m) => Int -> m a -> m [a]

Prelude Control.Monad> :t addqueen
addqueen :: [Int] -> [[Int]]

这意味着在表达式replicateM 8 addqueen中，addqueen的类型与m a匹配，给出m a ~ ([Int] -> [[Int]])，即m ~ ((->) [Int])和a ~ [[Int]]。因此，replicateM 8 addqueen的类型为m [a] ~ ([Int] -> [[[Int]]])。这不是您预期的结果。

（如果出现类型错误"No instance for (Monad ((->) [Int]))"，请先尝试加载例如Control.Applicative，以引入instance Monad ((->) r)的定义。如果使用较旧版本的GHC，则会发生这种情况）。

请改为尝试以下操作：

Prelude> :m +Control.Monad

Prelude Control.Monad> :t (>=>)
(>=>) :: (Monad m) => (a -> m b) -> (b -> m c) -> a -> m c

Prelude Control.Monad> :t foldl1 (>=>) $ replicate 8 addqueen
foldl1 (>=>) $ replicate 8 addqueen :: [Int] -> [[Int]]

Prelude Control.Monad> :t [[]] >>= ( foldl1 (>=>) $ replicate 8 addqueen )
[[]] >>= ( foldl1 (>=>) $ replicate 8 addqueen ) :: [[Int]]

---

更新: 表达式g = foldl1 (>=>) $ replicate 8 addqueen本身是有含义的。用Prolog术语来说，它是在初始解决方案中添加8个皇后的“目标”。我们通过向其提供最初为空的解决方案[ [] ] >>= g来使用g。

(这使用了一个稍微高级一点的运算符"fish"¹，即从左到右的Kleisli组合运算符>=>，定义为：

(m >>= a) >>= b  ===  m >>= (a >=> b)

即 >=> 是单子函数的组合运算符。

给你的表达式foldl (>>=) [[]] $ replicate 8 addqueen是由Sassa NF在评论中提供的。它使用了基本的单子绑定运算符>>=，但只能作为一个整体工作。

¹ 参考：http://haskellrescue.blogspot.com/2011/03/cooking-delicious-fish.html

- Will Ness

Answer 2

你少了空格

addqueen xs = [x:xs|x<-[1,2..8], not $ x `elem` xs 
    || (any (\(index,q) -> abs (x-q) ==index) $ zip [1..] xs)]

其次，不要同时使用多个中缀函数

--this code is invalid:
[[]] >>= replicateM 8 $ addqueen -- read as [[]] >>= (replicateM 8 $) addqueen

原因是：infixl 1 >>=和infixr 0 $ 第三，如果您使用GHCi，请为“empty”数据编写签名。

>([[]] :: [[Int]])>>= replicateM 8 addqueen

您的代码有效

> [[]]>>= replicateM 8 addqueen
[[[1],[2],[3],[4],[5],[6],[7],[8]],[[1],[2],[3],[4],[5],[6],[7],[8]],[[1],[2],[3],[4],[5],[6],[7],[8]],[[1],[2],[3],[4],[5],[6],[7],[8]],[[1],[2],[3],[4],[5],[6],[7],[8]],[[1],[2],[3],[4],[5],[6],[7],[8]],[[1],[2],[3],[4],[5],[6],[7],[8]],[[1],[2],[3],[4],[5],[6],[7],[8]]]

- wit

---

我仍然无法让它正常工作。这是我得到的：没有(->[Int])的Monad实例。 源自对replicateM'的使用 可能的解决方法: 为(->[Int])添加一个实例声明 在(>>=)'的第二个参数中, 重复执行8个addqueen操作 在表达式中: ([[]] :: [[Int]]) >>= replicateM 8 addqueen 在`it'的方程中: it = ([[]] :: [[Int]]) >>= replicateM 8 addqueen - user2812201

replicateM 3 (1+) $ 4 ==> [5,5,5]。而不是 [5,6,7]。 - Will Ness

@user2812201 目前你缺少 instance Monad ((->) r)。但这是好事。尝试使用 Prelude> :m +Control.Applicative；代码将会工作，但它不会做你想要的事情，而是做其他事情。 - Will Ness

"[[]] >>= replicateM 8 $ addqueen" 实际上应该读作 "([[]] >>= replicateM 8) $ addqueen"，但这显然毫无意义。 - Will Ness