一元過濾器和摺疊之間的關係

Question

許多高階函數可以根據fold函數定義。例如，下面是Haskell中filter和foldl之間的關係。

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

有自己的單子版本filterM和foldM之間的相似關係？ foldM我怎麼寫filterM？

我很努力地找到一個相當於\y x -> if (p x) then (x:y) else y的monadic來插入foldM而沒有成功。

Answer 1

像D.M.的答案，只是沒了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