为什么使用“<-”会导致正确计算幂集？

Question

所以我的书给出了如下计算幂集的代码：

filterM :: Monad m => (a -> m Bool) -> [a] -> m [a]
filterM p [] = return []
filterM p (x:xs) = do b <- p x
                      ys <- filterM p xs
                      return (if b then x:ys else ys)

filterM (\x -> [True,False]) [1,2,3]

result: [[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]

我只是不知道 p（[True,False]）的结果如何在 return (if b then x:ys else ys)

中可用

凭直觉，我猜测此 filterM 以返回所有可能排列的方式应用列表 b。即 x:ys 和 ys。但我只是没看到它发生在哪里。

我好像误会了 <- 是作业。它被翻译成对 (>>=) （绑定）的调用。但我不明白这将如何导致 b.

的多个实例

Answer 1

我的错误是将 <- 解释为直接分配。这是错误的。 b <- p x 由 >>= 运算符处理，其中：

Essentially, each <- is generating a set of values which is passed on into the remainder of the monadic computation.

因此，b 不是 [True,False]，而是在剩余计算的每次迭代中用 True 和 False 实例化。产生有效的 if True then x:ys else ys 和 if False then x:ys else ys。

Answer 2

我看到你已经回答了你自己的问题，但我认为添加一些关于 do-notation 其他部分的实现的信息可能会很有趣。所以：

x <- m; e 是 m >>= \x -> e;
e; e'（; 是换行符）是 e >> e';
let x = ...; e 就是这样：let x = ... in do e;

因此你的程序的递归分支实际上是这样的：

filterM p (x:xs) = p x >>= \b ->
                   filterM p xs >>= \ys ->
                   return (if b then x:ys else ys)

尽管我的回答看起来像是一个完整的列表，但它肯定不是。例如，如果启用 RecursiveDo，您将获得一个新的语法糖层：众所周知的 mfix 函数位于 rec 关键字和 mdo 符号的基础上。我敢肯定还有其他例子 spring 我一时想不起来。

为什么使用“<-”会导致正确计算幂集？

Why is this usage of "<-" resulting in a correct computation of a powerset?

monads

haskell