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

許多高階函數可以根據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而沒有成功。

來源

2013-07-27 stackman

是'myFilter p [] = []'冗餘嗎？ –

@ДМИТРИЙМАЛИКОВ - 是的，絕對。 – stackman

請注意，'foldl'是這裏的「錯誤」摺疊，'foldr'是「正確的」摺疊。例如，'myFilter'對於無限列表是'_ | _'，而原始'filter'不是（很好，因爲謂詞對於至少一個元素是成立的）。 –

像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

來源

2013-07-27 23:56:32

不知道它有任何意義（因爲它有一個奇怪的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

來源

2013-07-27 23:35:55

感謝您的回答。代碼中的執行順序存在一個小問題，不知道爲什麼。這是一個簡單的測試。 filterM（const [True，False]）[1,2] => [[1,2]，[1]，[2]，[]]。 myFilterM（const [True，False]）[1,2] => [[1,2]，[2]，[1]，[]] – stackman

這是因爲'reverse'。 –

啊！現在我明白了。我不必翻轉'l'，而是必須'myMilterM'的'liftM reverse'來獲得標準的執行順序。現在一切都很清楚。 – stackman

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

回答

相關問題