haskell - `filterM` 用于容器，例如 `Data.Map.Map` 或 `Data.Set.Set`

Question

简而言之:您将如何过滤 Map 的元素？ , 或 Set在单子(monad)上
Haskell中的谓词？

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

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) 如果谓词本质上不是一元的，而是例如是一个比较
在 State 中声明单子(monad);那么我们可以使用 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 的内部结构的实现权还要好。 .代码和数据可用 here .

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