我知道这个问题已经有答案并且大约4年了，但是为了未来可能会遇到这个问题的人着想，我想补充一些额外的信息。具体来说，我想试着回答以下两个问题:
- 如何将返回单个值的多个Select组合以创建返回值序列的单个Select?
- 当解决方案路径注定失败时，是否有可能提前返回?
链接Selects
Select在transformers库中被实现为一个单子变换器（monad transformer），但我们还是先看看如何只为Select实现>>=：
(>>=) :: Select r a -> (a -> Select r b) -> Select r b
Select g >>= f = Select $ \k ->
let choose x = runSelect (f x) k
in choose $ g (k . choose)
我们首先定义一个新的
Select，它接收类型为
a -> r的输入参数
k（回忆一下，
Select包装了类型为
(a -> r) -> a的函数）。您可以将
k视为一个函数，它返回给定
a的类型为
r的“分数”，这个分数可以用来确定
Select函数应该返回哪个
a。
在我们的新
Select内部，我们定义了一个名为
choose的函数。此函数将一些
x传递给函数
f，它是单子绑定的
（monadic binding）部分
a -> m b：它将
m a计算的结果转换为新的计算
m b。因此，
f将使用
x返回一个新的
Select，然后
choose会使用我们的得分函数
k运行它。您可以将
choose视为一个函数，它询问“如果我选择
x并将其向下传递，最终结果会是什么？”
在第二行中，我们返回了
choose $ g (k . choose)。函数
k . choose是
choose和我们最初的得分函数
k的组合：它接收一个值，计算选择该值的下游结果，并返回该下游结果的得分。换句话说，我们创建了一种“预知”得分函数：它不返回给定值的得分，而是返回我们选择该值后将获得的最终结果的得分。通过将我们的“预知”得分函数传递给
g（我们要绑定到的原始
Select），我们能够选择导致我们正在寻找的最终结果的中间值。一旦我们有了中间值，我们只需将其传回
choose并返回结果即可。
这就是我们如何能够将单个值的
Select连接在一起并传入作用于值数组的得分函数的方法：每个
Select都对选择值的假设最终结果进行评分，而不一定是值本身。应用实例遵循相同的策略，唯一的区别是如何计算下游的
Select（它不是将候选值传递到
a -> m b函数中，而是将候选函数映射到第二个
Select上。）
提前返回
那么，我们如何在提前返回的情况下使用
Select？我们需要一种方法来在构造
Select的代码范围内访问得分函数。一种方法是在另一个
Select内部构造每个
Select，就像这样：
sequenceSelect :: Eq a => [a] -> Select Bool [a]
sequenceSelect [] = return []
sequenceSelect domain@(x:xs) = select $ \k ->
if k [] then runSelect s k else []
where
s = do
choice <- elementSelect (x:|xs)
fmap (choice:) $ sequenceSelect (filter (/= choice) domain)
这样可以让我们测试正在进行的序列，并在失败时短路递归。(我们可以通过调用k []来测试该序列，因为评分函数包括我们递归排列的所有前缀。)
以下是整个解决方案：
import Data.List
import Data.List.NonEmpty (NonEmpty(..))
import Control.Monad.Trans.Select
validBoard :: [Int] -> Bool
validBoard qs = all verify (tails qs)
where
verify [] = True
verify (x:xs) = and $ zipWith (\i y -> x /= y && abs (x - y) /= i) [1..] xs
nqueens :: Int -> [Int]
nqueens boardSize = runSelect (sequenceSelect [1..boardSize]) validBoard
sequenceSelect :: Eq a => [a] -> Select Bool [a]
sequenceSelect [] = return []
sequenceSelect domain@(x:xs) = select $ \k ->
if k [] then runSelect s k else []
where
s = do
choice <- elementSelect (x:|xs)
fmap (choice:) $ sequenceSelect (filter (/= choice) domain)
elementSelect :: NonEmpty a -> Select Bool a
elementSelect domain = select $ \p -> epsilon p domain
epsilon :: (a -> Bool) -> NonEmpty a -> a
epsilon _ (x:|[]) = x
epsilon p (x:|y:ys) = if p x then x else epsilon p (y:|ys)
简而言之：我们通过递归构建一个选择器，在使用元素时从域中移除它们，并在域被耗尽或我们走错路线时终止递归。
另一个补充是基于希尔伯特的epsilon运算符的epsilon函数。对于大小为N的域，它最多会检查N-1个项目...这可能听起来不像是巨大的节省，但正如您从上面的解释中所知道的那样，p通常会启动整个计算的其余部分，因此最好尽可能减少谓词调用。
关于sequenceSelect的好处在于它的通用性：它可以用于创建任何Select Bool [a]，其中：
我们在有限的不同元素域内进行搜索
我们想要创建一个包含每个元素恰好一次的序列（即该域的排列）
我们想要测试局部序列并在其未能满足谓词时放弃它们
希望这有助于澄清问题！
附注：这是一个Observable笔记本的链接，在其中我使用Javascript实现了Select单子和n皇后求解器的演示：https://observablehq.com/@mattdiamond/the-select-monad
Select单子类型吗？我的理解是，Select尝试证明可能解决方案的存在（作为证明的见证）。Select的典型示例是 SAT 求解器。你可能可以通过在列表单子类型上使用SelectT强制执行某些操作，但我更确信你真正需要使用Select单子类型。 - AlecSelect在回溯搜索中很好用，而n皇后问题是这种类型的原型问题，所以我认为它是monad的一个很好的使用案例。 - danidiazSelect单子，而是这个项目：queenslogic 使用Logic单子通过回溯法解决 N 皇后问题。 - Dave Compton