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

Like in D.M.'s answer, only without the reverse. Let the types guide you:

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

Not sure that it has any sense (since it has that strange reverse), but at least it type checked well:

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