我想制作一个通用函数,可以折叠各种输入(请参阅使单个函数适用于列表、字节字符串和文本(可能还有其他类似的表示形式))。正如一个答案所建议的那样,ListLike就是为了这个。它的FoldableLL类为任何可折叠的东西定义了一个抽象。但是,我需要一个单子折叠。所以我需要foldM
用foldl
/来定义foldr
。
到目前为止,我的尝试失败了。我试图定义
foldM'' :: (Monad m, LL.FoldableLL full a) => (b -> a -> m b) -> b -> full -> m b
foldM'' f z = LL.foldl (\acc x -> acc >>= (`f` x)) (return z)
但它在大量输入时内存不足 - 它构建了一个大型未评估的计算树。例如,如果我将一个大文本文件传递给
main :: IO ()
main = getContents >>= foldM'' idx 0 >> return ()
where
-- print the current index if 'a' is found
idx !i 'a' = print i >> return (i + 1)
idx !i _ = return (i + 1)
它会耗尽所有内存并失败。
我有一种感觉,问题在于一元计算是以错误的顺序组成的——就像((... >>= ...) >>= ...)
不是,(... >>= (... >>= ...))
但到目前为止我还没有找到解决方法。
解决方法:由于ListLike
暴露mapM_
,我通过将累加器包装到状态单子中来构建 s foldM
:ListLike
modifyT :: (Monad m) => (s -> m s) -> StateT s m ()
modifyT f = get >>= \x -> lift (f x) >>= put
foldLLM :: (LL.ListLike full a, Monad m) => (b -> a -> m b) -> b -> full -> m b
foldLLM f z c = execStateT (LL.mapM_ (\x -> modifyT (\b -> f b x)) c) z
虽然这适用于大型数据集,但它不是很好。它并没有回答最初的问题,如果可以在只是FoldableLL
(没有mapM_
)的数据上定义它。