如何用bind(>>=)实现filter函数？现有实现报错求解答

首先，咱们得先明确List类型的>>=（bind）的行为和类型签名，这是你出错的核心原因。

1. List的>>=到底是什么？ #

对于Haskell的列表来说，>>=的类型签名是：

(>>=) :: [a] -> (a -> [b]) -> [b]

它的实际作用是：把列表里的每一个元素x，通过函数f映射成一个新的列表[b]，然后把所有这些小列表拼接起来（等价于concatMap f xs）。

简单说，传给>>=的函数必须是接受单个元素，返回一个列表的函数，而不是接受两个参数的函数。

2. 你的错误在哪里？ #

你写的lambda表达式：

\x xs -> if p x then x : f p xs else f p xs

这个函数接受两个参数（x和xs），类型是a -> [a] -> [a]，但>>=要求的是a -> [a]类型的函数。这就导致编译器报错：它预期你传入的函数返回[a]，但实际返回的是[a] -> [a]（一个函数），类型完全不匹配。

另外，这里的第二个参数xs其实是你误解了bind的逻辑——bind不需要你手动递归处理剩余列表，它会自动遍历原列表的每一个元素，你只需要告诉它每个元素应该转换成什么列表即可。

3. 正确的>>=实现方式 #

正确的思路是：对每个元素x，如果满足p x，就把它包装成单元素列表[x]（这样它会被保留在最终结果里）；如果不满足，就返回空列表[]（这样这个元素会被过滤掉）。然后用>>=把所有这些列表拼接起来，就得到了过滤后的结果。

代码如下：

f :: (a -> Bool) -> [a] -> [a]
f p xs = xs >>= (\x -> if p x then [x] else [])

或者更简洁的写法，借助Control.Monad里的guard函数：

import Control.Monad

f :: (a -> Bool) -> [a] -> [a]
f p xs = xs >>= \x -> guard (p x) >> return x

4. 和foldr实现的区别 #

你的foldr实现是完全正确的：

f p xs = foldr (\x xs -> if p x then x : f p xs else f p xs) [] xs

这里的lambda是\x acc -> ...，其中acc是foldr的累加器（也就是之前处理过的元素的结果），这是foldr的逻辑——递归地把元素加到累加器里。而bind的逻辑是逐个处理元素，生成小列表再拼接，两者的递归方式和参数逻辑完全不同，不能直接把foldr的lambda搬到bind里用。

内容的提问来源于stack exchange，提问作者V0lvox337