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

Question

我刚开始学习编写 Haskell 代码，如果这是一个愚蠢的问题，我深表歉意。我试图通过使用 [] 来重做八皇后问题。单子(monad)。这是代码，

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

那么我如何在这里实现我想要做的呢？

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 中它是 a "goal"在初始解中添加 8 个皇后。我们使用 g通过给它一个最初为空的解决方案， [ [] ] >>= g .
(这使用了一个略高于基本级别的操作符 "fish"1 即 left-to-right Kleisli composition operator >=> ，这样定义

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

即 >=>是一元函数的组合运算符. )
给你的表情 in the comments by Sassa NF , foldl (>>=) [[]] $ replicate 8 addqueen , 使用基本的 monadic bind operator >>= ，但只能作为一个整体工作。
1 http://haskellrescue.blogspot.com/2011/03/cooking-delicious-fish.html