haskell - relation between monadic filter and fold

Question

Many higher-order functions can be defined in term of the fold function. For example, here is the relation between filter and foldl in Haskell.

myFilter p [] = []
myFilter p l = foldl (\y x -> if (p x) then (x:y) else y) [] (reverse l)

Is there a similar relation between their monadic versions filterM and foldM ? How can I write filterM in term of foldM ?

I tried hard to find a monadic equivalent to \y x -> if (p x) then (x:y) else y to plug into foldM without success.

Answer 1

就像在 DM 的回答中一样，只有没有reverse. 让类型指导您：

import Control.Monad
{-
foldM   :: (Monad m) => (b -> a -> m b) -> b -> [a] -> m b
filterM :: (Monad m) => (a -> m Bool)        -> [a] -> m [a]
-}

filtM :: (Monad m) => (a -> m Bool) -> [a] -> m [a]
filtM p xs = foldM f id xs >>= (return . ($ [])) 
  where 
    f acc x = do t <- p x 
                 if t then return (acc.(x:)) else return acc

Answer 2

不确定它有什么意义（因为它有那个奇怪reverse的），但至少它的类型检查得很好：

myFilterM :: Monad m => (a -> m Bool) -> [a] -> m [a]
myFilterM p l = foldM f [] (reverse l)
 where
  f y x = do
    p1 <- p x
    return $ if p1 then (x:y) else y