这些 mondaic 函数之间有什么区别？

Question

所以我有这两个功能：

filterM _ [] = []
filterM p (x:xs) = do
                  n <- p x
                  ys <- filterM p xs
                  return (if n then x:ys else x:xs)

和

filterM _ [] = return []
filterM p (x:xs) = do
                  n <- p x
                  ys <- filterM p xs
                  return (if n then x:ys else x:xs)

针对以下输入产生这些结果：filterM (\x -> [True,False]) [0..3]

[]

或

[[0,1,2,3],[0,1,2,3],[0,1,2,3],[0,1,2,3],[0,1,2,3],[0,1,2,3],[0,1,2,3],[0,1,2,3],[0,1,2,3],[0,1,2,3],[0,1,2,3],[0,1,2,3],[0,1,2,3],[0,1,2,3],[0,1,2,3],[0,1,2,3]]

为什么 return 对执行的影响如此之大？

Answer 1

让我们看一个简单的例子，我们调用：

filterM (const [True, False]) [0]

我们预计这将 return [[0], [0]]。如果我们看一下第一个实现，我们会发现这将导致：

filterM (const [True, False]) (0:[]) = do
    n <- [True, False]
    ys <- <b>filterM (const [True, False]) []</b>
    return (if n then 0:ys else 0:[])

如果我们采用第一个实现，filterM (const [True, False]) [] 将导致 []。所以这意味着它看起来像：

-- first implementation
filterM (const [True, False]) (0:[]) = do
    n <- [True, False]
    ys <- <b>[]</b>
    return (if n then 0:ys else 0:[])

因为 instance Monad [], the >>= is implemented as:

instance Monad [] where
    return x = [x]
    xs >>= f = [y | x <- xs, y <- f x]

这意味着如果 xs 为空，那么结果也将为空。

在第二个实现中，return [] 将导致 [[]]，因此 单例列表 其中单个元素是一个空列表。在那种情况下，它看起来像：

-- second implementation
filterM (const [True, False]) (0:[]) = do
    n <- [True, False]
    ys <- <b>[[]]</b>
    return (if n then 0:ys else 0:[])

这意味着我们枚举列表，ys 将取值 []，因此它会产生一个列表 [[0], [0]].

通常情况下，过滤器不会在这两种情况下添加 x，此外，您可能希望产生 x:ys 和 ys；不是 x:ys 和 x:xs。因此，正确的实现是：

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

这些 mondaic 函数之间有什么区别？

What is the difference between these mondaic functions?

monads

haskell