`filterM`用于容器,如`Data.Map.Map`或`Data.Set.Set`

Question

简而言之:如何在Haskell中过滤a Map或者Setmonadic谓词的元素？

我可以想到两种可能的方法:

a)往返列表并且filterM(可能效率不高):

filterMapM1 :: (Monad m, Ord k) => (v -> m Bool) -> M.Map k v -> m (M.Map k v)
filterMapM1 f m = liftM M.fromList $ filterM (f.snd) $ M.toList m

b)如果谓词不是固有的monadic,而是例如与Statemonad中的状态进行比较; 然后我们可以使用Data.Map.filter(非常特殊的情况):

filterMapM2 :: (Monad m, Ord k) => (v -> v -> Bool) -> M.Map k v -> StateT v m (M.Map k v)
filterMapM2 f m = do
    s <- get
    return $ M.filter (f s) m

有一个更好的方法吗？

---

这是一个用于演示的示例程序.

import Control.Applicative
import Control.Monad
import Control.Monad.State
import qualified Data.Map as M

-- | filterM for M.Map. (Round trip through a list and filterM)
filterMapM1 :: (Monad m, Ord k) => (v -> m Bool) -> M.Map k v -> m (M.Map k v)
filterMapM1 f m = liftM M.fromList $ filterM (f.snd) $ M.toList m

-- | filterM for M.Map. (Uses M.filter to filter on comparison to state)
filterMapM2 :: (Monad m, Ord k) => (v -> v -> Bool) -> M.Map k v -> StateT v m (M.Map k v)
filterMapM2 f m = do
    s <- get
    return $ M.filter (f s) m

-- | Inherently monadic predicate: Result depends on user-input.
askUser :: Int -> IO Bool
askUser n = do
    liftIO $ putStrLn $ "Do you like the number " ++ show n ++ "?"
    liftIO $ (=="yes") <$> getLine

main :: IO ()
main = do
    let m = M.fromList $ take 6 $ zip ['a'..] [1..]
    -- Use inherently monadic predicate
    print =<< filterMapM1 askUser m
    -- Compare to state
    (`evalStateT` 4) $ do
        filt2 <- filterMapM2 (/=) m
        liftIO $ print filt2

---

更新:我在不同的实现之间做了一个基准测试filterMapM.事实证明,通过列表的往返实际上非常好.令人惊讶的是,它确实比在内部结构上实现更好Map.代码和数据可在此处获得.

Answer 1

这两种方法具有截然不同的语义和对效率的影响。

当您往返列表时，您允许过滤受到所有先前比较的影响，因此最终结果可能会受到访问元素的顺序的影响。然而，在第二种情况下，过滤是纯函数，因此无论以什么顺序进行比较，答案都是相同的。

例如，回答问题的用户可能希望保持偶数和奇数的数量大致相同，因此用户是否喜欢特定数字将取决于之前已经呈现的所有数字。

另一方面，这里是代码M.filter：

-- | /O(n)/. Filter all elements that satisfy the predicate.
filter :: (a -> Bool) -> Set a -> Set a
filter _ Tip = Tip
filter p (Bin _ x l r)
    | p x       = link x (filter p l) (filter p r)
    | otherwise = merge (filter p l) (filter p r)

重要的是要注意代码的形状 - 生成的树结构很大程度上受到原始树结构的影响。也许只需要少量的重新平衡。这可能比使用从零知识重建树更有效M.fromList。

结果是，在这种filterM1情况下，您应该关心进行比较的顺序。也许M.toList给出了一个可以接受的顺序，或者也许你想要reverse . M.toList，或者......

在第二种情况下，您不需要关心，因此您可以让其M.filter完成所有工作并利用其数据结构知识。

更新：我刚刚注意到M.toAscList和M.fromAscList功能，所以也许这个版本的filterMapM1效率稍微高一些：

filterMapM1 f m = liftM M.fromAscList $ filterM (f.snd) $ M.toAscList m